Как самые медленные компьютерные программы проливают свет на фундаментальные ограничения математики

[middle]

BB(6) составляет по крайней мере 7,4 × 10^{36 534}, а не 7,4 × 1 036 534.

[v1000]

А почему «busy» это усердный? По смыслу скорее занятой или загруженный работой.

[KD637]

Усердный бобер — это устоявшийся перевод. Скорее всего, закрепился из-за того, что «усердный» передаёт смысл понятия точнее «занятого»: усердный занят с усердием, выжимает максимум. Кроме того, есть устоявшаяся фраза «усердный как бобер».

[Hardcoin]

Это означает, что расчёт BB(7,910) — это вычисление, ускользающее от аксиом теории множеств ZF.

На означает. Посчитав BB(7910), мы просто узнаем, сможем ли мы узнать противоречивость ZF. Но теорема Гёделя запрещает непротиворечивость и полноту одновременно. Просто непротиворечивость не запрещает. И узнать об этом не запрещает.

[Kohelet]

Фридман думает, что это число можно уменьшить еще больше: «Я думаю, может быть, правильный ответ — 50»

Почему 50? Должно быть 42.

[taujavarob]

Должно быть 42.

Верно.

[CrazyOpossum]

Не особо понятен смысл этого всего. Неясно, чем догадка Гольдбаха сложнее чем проверка, что алгоритм Гасарха превысит/не превысит BB(27), потому что я не вижу как доказывают значения конкретных BB. Пока что выглядит как тавтология: «BB(n) — максимальное число шагов останавливающихся алгоритмов сложности n === любая гипотеза сложности n верна, если брутфорс её противного не остановится быстрее чем за BB(n)».

[red75prim]

Кроме упомянутого в статье потенциала для нового взгляда на теорию чисел, ещё есть и философский аспект: если примитивная машина может проверить непротиворечивость теорий, то математический платонизм становится более… реальным, что-ли. Истинность математических идей независима от нас.

[CrazyOpossum]

К сожалению, машина Тьюринга не может получить значение BB(n) по той же проблеме остановки.

[red75prim]

Но она остановится. Или не остановится. И это не зависит от человеческих интерпретаций математики.

[DieselMachine]

Допустим удалось если не вычислить, то хотя бы оценить BB(27) сверху. Тогда можно узнать сколько чётных чисел проверит машина Тьюринга за это число шагов. Следовательно доказательство гипотезы Гольдбаха можно свести к проверке этих первых чётных чисел каким-либо способом. Так что ли получается?

[CrazyOpossum]

Получается-то так, но из статьи непонятно как вообще оценивали значения BB. Чисто механически они невычислимы, а то что для BB(27) не требуется реально доказать гипотезу Гольдбаха пока неочевидно.

[ardraeiss]

Загвоздка в том, что число BB(27) — настолько непостижимо огромное число, что даже записать его, а тем более запустить фальсифицирующую машину Гольдбаха на такое количество шагов не представляется физически возможным в нашей Вселенной.

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

[nin-jin]

Ну и тут нельзя не поделиться этим анализом, показывающим, что теоремы Гёделя и Тьюринга показывают лишь неполноценность бинарной логики, а не какие-то фундаментальные ограничения.

[sashagil]

KD637 в ваш перевод просочилась довольно забавная ошибка. В оригинале указано BB(2) = 6 и BB(3) = 21 (а не 107, как в вашем переводе) — и не указано BB(4), за этим знанием надо обратиться к статье 1983го года… Чтобы узнать, что BB(4) = 107! Так вот откуда взялось неверное значение BB(3)! :)

[u007]

Здесь какой-то подвох.

Тьюринг доказал, что нет универсального надёжного способа определить, завершится ли программа. Соответственно, для определения числа BB(27) придётся индивидуально рассмотреть все N^27 вариантов возможных программ и доказать конечность или бесконечность каждой. В том числе программы «Гольдбах». Так или не так?

Иными словами, для вычисления BB(27) нужно доказать гипотезу Гольдбаха…