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

[stas]

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

Comments

[avva.livejournal.com]

Например, утверждение "написав это количество единиц, машина Тьюринга с 10 состояниями уже точно никогда не остановится" верно для невероятно больших чисел (неизвестно, насколько больших). Если заменить 10 на 6, то числа, о которых идет речь, будут не меньше 1e1439.

[stas]

Очень интересно. Т.е., если идти дально по этому пути (т.е., предположим, кто-то сможет распространить это на 20 сотояний, 100, 1000 и т.д.), то можно предположить, что утверждение "никогда не остановится" заменяется на утверждение "напишет некорое (огромное, но конечное) число единиц"?

[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) единиц, она уже не остановится.

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

[avva.livejournal.com]

да, а называется это все the busy beaver problem.