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

[stas]

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

Comments

[avva.livejournal.com]

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

[lamed.livejournal.com]

Любое нечетное число, начиная с некоторого достаточно большого, есть сумма трех простых чисел. Другими словами: среди натуральных чисел существует такое достаточно большое число, за которым всякое нечетное натуральное число является суммой трех простых чисел.

Эта теорема верна для нечетных чисел, больших е^e16,038, где е - основание натуральных логарифмов; е = 2,7182...

[stas]

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

[stas]

Это жесткая нижняя грань (т.е. измвестно число меньше этого, которое не может быть так представлено) или только наименьшее доказанное?

[burrru.livejournal.com]

Интересных нет. Понятно, что с точки зрения теории чисел несложно настрогать такие теоремы: любое число, большее SuperN, разложимо в сумму k чисел, обладающих свойством P.

С точки зрения теории групп, стоит снизить планку со ста до пятидесяти:
http://en.wikipedia.org/wiki/Monster_group

Но это все от лукавого. Для понимания этого мира вполне достаточно числа 248 :)
http://en.wikipedia.org/wiki/An_Exceptionally_Simple_Theory_of_Everything

[avva.livejournal.com]

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

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

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

[avva.livejournal.com]

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

[lamed.livejournal.com]

Наименьшее доказанное.

Строго говоря, уже не наименьшее. Как мне подсказывает Google, в 1989 г. эту оценку понизили до e^e11,503. Гипотеза же (слабая гипотеза Гольдбаха) предполагает, что это верно для всех нечетных чисел, больших 5, но доказать это пока невозможно.

[stas]

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

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

[gns-ua.livejournal.com]

> Для понимания этого мира вполне достаточно числа 248

можно ещё понизить планку. Достаточно 42 (http://ru.wikipedia.org/wiki/%D0%9E%D1%82%D0%B2%D0%B5%D1%82_%D0%BD%D0%B0_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D0%B9_%D0%B2%D0%BE%D0%BF%D1%80%D0%BE%D1%81_%D0%B6%D0%B8%D0%B7%D0%BD%D0%B8,_%D0%B2%D1%81%D0%B5%D0%BB%D0%B5%D0%BD%D0%BD%D0%BE%D0%B9_%D0%B8_%D0%B2%D1%81%D0%B5%D0%B3%D0%BE_%D1%82%D0%B0%D0%BA%D0%BE%D0%B3%D0%BE).

[alexcohn.livejournal.com]

Великая теорема Ферма не устраивает? Для Ронена год назад любое число больше двух было "очень много".

[ktotam.livejournal.com]

Graham's number (http://en.wikipedia.org/wiki/Graham's_number)

[stas]

Да, я тем временем его сам нашел. Хороший пример. Хотя на самом деле неизвестно, может настоящий ответ - вовсе 42, число Грэхэма, как я понимаю, только граница опять же.

[stas]

Ага :) Но с двух начинать неинтересно, понятно, что разных свойств у разных числе можно много найти. Вопрос в том, появляются ли "за горизонтом" какие-то новые свойства, которых отсюда "не видно".

[induke.livejournal.com]

Вот очень простая задача, ответ которой больше 10^17: http://www.math.wayne.edu/~petem/probweek/fall97/sol9.html

[rezkiy.livejournal.com]

приближение факториала. http://en.wikipedia.org/wiki/Stirling%27s_approximation

[stas]

Но формула Стирлинга - обычная асимптотическая формула, что в ней интересного с этой точки зрения?