Такие дела, я копирую текст Шона Таунсенда из фейсбука в свой типа блог.
Дело в том, что фейсбук давно стал ненадёжным местом для хранения текстов, особенно когда их публикует такой человек, как Шон. Его аккаунт уже блокировали. А поскольку это фейсбук, то и архив интернета не спасёт.
Поэтому вот тут я публикую копию поста, с указанием авторства и ссылкой на оригинал. Разрешения на репост я не спрашивал; предполагаю, что мои действия укладываются в рамки здравого смысла и fair use. Я разбил текст на абзацы для улучшения читаемости; надеюсь, этим я не испортил авторский замысел.
Хочу однажды (не сегодня) неторопливо поразмыслить над этим текстом.
Шон Таунсенд
вторник, 15 декабря 2020 года, 02:09
https://www.facebook.com/ruheight/posts/1092058617909162Я вобщем-то не собирался сегодня ничего писать о ментальных отходах Верховной Рады, а вспомнил о трудолюбивых бобрах (busy beaver), довольно занятная, скажу я вам вещица, хотя начать придётся издалека.
Я думаю, что даже те из вас, кто не очень-то связан с компьютерами, слышали о машине Тьюринга — воображаемая машина, которая ползает по бесконечной ленте влево и вправо, и за один ход может считать и записать один символ с ленты. Для простоты можно ограничиться нулями и единичками. С помощью такой машины можно решить любую задачу из тех, что вобще можно решить. Если задачу нельзя закодировать в виде МТ, то она — алгоритмически неразрешима, просто по определению, алгоритм — любая задача, которую можно решить с помощью МТ.
Важная задача, которую решить нельзя — остановится ли машина Тьюринга или будет работать вечно? В 1962 году Тибор Радо задал казалось бы простой вопрос. Из всех машин определенной «длины» (количество состояний), которые останавливаются, есть такая, которая работает дольше всех. И назвал её трудолюбивым бобром. Такая машина задаёт верхнюю границу времени работы любой программы. BB(2) = 6, BB(3) = 21, BB(4) = 107, BB(5) = 47176870 (но это не точно) дальше BB(7) никто не заглядывал, но воможно что BB(18) больше, чем число Грэма (самое безумное число, которое действительно появляется в математическом доказательстве).
Отвлечемся от бобров и перейдем к другим головоломкам. Есть такая штука, как гипотеза Гольдбаха. Звучит очень просто: любое четное число больше двух можно представить в виде суммы двух простых чисел. Доказать пока ни у кого не получилось. Перебирать можно вечно. Совпадения, сколь много бы их ни было ничего не доказывают. В 2013 году рекорд был 10^18, сейчас наверное больше, но это гораздо меньше бесконечности.
И тут снова появляются бобры. В 2015 году аноним запостил на гитхаб МТ из 27 состояний, которая останавливается, если гипотеза Гольдбаха не верна.
https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6
Программа просто перебирает варианты и останавливается на первом противоречии. И по определению, если эта программа работает конечное время, то она работает не дольше, чем бобер номер 27, который задает верхнюю границу сложности для «доказательства».
Для любого утверждения, которое можно опровергнуть за конечное время, найдется верхняя граница вычислений — BB(n), хотя само число BB(n) вычислить нельзя (иначе мы смогли бы решить проблему останова). С практической точки зрения вселенная рассыплется в труху гораздо раньше (но это невыразимо огромное число всё еще сильно меьше бесконечности). Занятная штука, чтобы размышлять за завтраком о сложности и пределах вычислимого. А не вот это вот всё зеленое законодровчество.
P.S.: и, конечно же, https://xkcd.com/1310/ :)