большие числа

[stas]

Интересно, а есть ли в математике какие-нибудь интересные (и понятные неспециалисту) теоремы, результаты и т.п., которые выполняются только для очень больших чисел? Т.е., скажем, было бы некоторое утверждение, которое для всех чисел меньше, скажем, 1e100 верно, а выше есть числа, для которых оно неверно (ну или наоборот)? Разумеется, я не говорю о тривиальных случаях типа утверждения "все числа меньше 1е100" и прочих, где граница прописана прямо. 

Comments

[avva.livejournal.com]

да, или "сделает некоторое кол-во шагов". Но и кол-во шагов и кол-во единиц зависят от числа состояний, поэтому не существует одного предела для всех машин.

Если мы рассмотрим все возможные машины с N состояниями, то некоторые из них никогда не остановятся (необязательно войдя в повторяющийся цикл - напр. машина, которая перебирает одно за другим все натуральные числа, выписывая их на ленте в десятичном представлении), а другие остановятся. Т.к. всех возможных машин с N состояниями конечное число, то есть максимум кол-ва единиц, которые пишут во время своей работы все останавливающиеся машины, обозначим его f(N). Значит, если машина с N состояниями написала больше f(N) единиц, она уже не остановится.

f(N) невозможно вычислить в общем случае (если бы мы могли его вычислить для любого N, то могли бы решить the halting problem), и даже для очень маленьких N его вычислить очень трудно. Известны значения для N<=4, и огромные нижние оценки для 5 и 6.

[stas]

Т.к. всех возможных машин с N состояниями конечное число, то есть максимум кол-ва единиц, которые пишут во время своей работы все останавливающиеся машины, обозначим его f(N). Значит, если машина с N состояниями написала больше f(N) единиц, она уже не остановится.

Да, логично. Я слышал об этой проблеме краем уха, но толком не читал, спасибо.