пятый busy beaver
Из блога Скотта Ааронсона я узнал сегодня, что мы теперь точно знаем значение BB(5) - функции Busy Beaver на 5 состояниях. Это одновременно тривиальная и захватывающая новость. Это что-то, про что я не был уверен, что будет известно в течение моей жизни - хотя полагал вероятным.
Что такое Busy Beaver? Попробую вкратце объяснить.
В информатике есть понятие "машина Тьюринга". Это не настоящая физическая машина из транзисторов, а теоретическая модель. Представьте себе бесконечную ленту, состоящую из ячеек, в каждой из которых может быть записано '0' или '1' (в общем случае можно и больше разных символов, но достаточно двух). Изначально на ленте везде написано '0', и над одной из ячеек находится головка чтения-записи, которая может находиться в одном из нескольких состояний (представьте себе переключатель, который может быть в положении A,B,C или D - это пример 4 состояний). За один шаг головка машины смотрит, что написано на ячейке, над которой она сейчас находится, а потом справляется в "таблице переходов". В таблице написано, например: если ты в состоянии A и видишь 0, то перейди в состояние B, напиши 1, и сдвинься вправо. И так на любую комбинацию "состояние-что я вижу" есть рецепт: в какое состояние перейти, что написать, 0 или 1, и куда сдвинуться, влево или вправо. Потом машина делает следующий шаг по таким же правилам. И так далее, пока она не войдет в состояние, которое заранее считается "конечным", например D, и тогда она останавливается.
В принципе такая модель может выполнять все, что мы считаем "алгоритмом" и поручаем компьютерам. Внутри вашего компьютера (или телефона) есть процессор, который понимает только нули и единицы. И хотя он работает сразу с многими нулями/единицами одновременно, и выполняет сложные программы, все, что он делает, в принципе можно смоделировать как машину Тьюринга (с очень большим числом состояний). Такая машина может получать входные данные не с клавиатуры, а записанные заранее на ее ленте, и выдавать результат не на экране, а тоже на своей ленте. Ученые используют эту модель в основном для того, чтобы доказывать, какие задачи компьютер не может выполнить никогда даже в принципе, или какие алгоритмы принципиально намного быстрее или медленнее других.
В 1962 году венгерско-американский математик Тибор Радо задал следующий вопрос. Обычно для того, чтобы сделать что-нибудь "интересное" машиной Тьюринга, нужно много состояний. Состояния играют роль внутренней логики алгоритма, позволяют машине "помнить", где она находится внутри сложного алгоритма, что она уже выяснила, итд. Но давайте для любого N посмотрим на все возможные машины (т.е. разные таблицы перехода) из N состояний, и что они делают с пустой лентой (все нули). Одни программы быстро остановятся, войдя в состояние остановки; другие войдут в бесконечный цикл, или уйдут "в бесконечность" без цикла - например, будут писать 1, двигаясь все дальше и дальше по бесконечной ленте без возврата. Но есть какая-то машина, которая в конце концов остановится, но после наибольшего числа шагов по сравнению со всеми остальными из N состояний. Такая машина-чемпион называется Busy Beaver. Сколько шагов она сделает перед тем, как остановится, для данного N?
Для очень малого числа состояний, 1-2-3, легко перебрать все возможные машины и посмотреть, что они делают, слишком примитивными они являются. Для 4 состояний максимальное число шагов перед остановкой равно 107, и это доказали в 1983 году. Однако уже 5 состояний позволяют сделать хитрые машины, про которые нелегко понять, они делают что-то бесконечное, или все-таки остановятся рано или поздно. С 1990 года есть кандидат - машина, которая останавливается после 47 миллионов шагов - но чтобы доказать, что она чемпион, нужно перебрать все возможные машины из 5 состояний, а их 16 триллионов! Проблема в том, что нет универсального метода определить, остановится данная машина или нет (это как раз "проблема остановки", которую принципиально невозможно решить с помощью алгоритма). Можно либо запускать ее на симуляторе, желательно очень оптимизированном, делающим миллионы шагов в секунду, и ждать, пока она остановится, либо искать математическое доказательство того, что никогда не остановится - а его надо искать для каждого сложного случая отдельно. К началу 2000-х осталось только около 40 сложных случаев - машин, которые скорее всего никогда не останавливаются, но доказать это пока не могли. В принципе могло бы оказаться и так, что одна из них "моделирует" сложную математическую проблему. Скажем, есть машина из 23 состояний, которая останавливается только если неверна знаменитая гипотеза Гольдбаха, которую никто не может доказать уже несколько сотен лет. Но 5 состояний все же настолько мало, что такое казалось маловероятным. И вот, после нескольких лет усердной работы фанатов этой проблемы в последние годы, им удалось избавиться от всех сложных случаев, и доказать то, что все подозревали - что кандидат 1990 года и есть чемпион. Все технические подробности - на сайте bbchallenge.org!
Проблема Busy Beaver - странная, любопытная штука. С одной стороны, не очень ясно, зачем ей заниматься. Найти общую формулу или метод для любого N невозможно в принципе. Ответ для N=5 никакой конкретной пользы ни для чего не приносит. Ответ для N=6 скорее всего останется недоступен для человечества за все время его существования. Более того, то, как именно сформулирована задача (какое из нескольких определений простой машины Тьюринга используется, например) "все меняет" в смысле ответа и его доступности нашим усилиям, так что задача в любом случае довольно "искусственно" выглядит. И все равно есть что-то притягательное в ней для горстки программистов и математиков, которые продолжали активно работать над ней все эти годы.
Я это хорошо понимаю, потому что много лет назад внес свой крохотный вклад в этот сизифов труд. Тогда был свежий и многообещающий кандидат в ряды Busy Beaver из 6 состояний, который останавливался после 8 квадриллионов шагов (квадриллион это миллион миллиардов), но этот факт еще никто не подтвердил независимо от первооткрывателя этой машины (столько шагов невозможно было запустить "напрямую" симулятором, надо было придумать и написать специальную программу, которая использует логику этой конкретной машины). Я помню, что написал такую программу, подтвердил результат и послал первооткрывателю, но не мог вспомнить сегодня, когда это сделал, думал, что где-то в начале 2000-х. Но потом нашел упоминание, которое все еще лежит на сайте этого человека: "No 2 has been verified independently by Anatoly Vorobey
at 20 Sep 1997. He was the first to detect that the original number of steps were one too large (corrected above)."
Я уже 20 лет не пользуюсь этим мейлом. Я забыл, что поправил на 1 количество шагов этого кандидата. Сам кандидат три года спустя был заменен другим, гораздо более крутым по числу шагов, а потом снова и снова - тот кандидат, что есть сейчас, останавливается после невообразимо огромного числа шагов, это число не записать обычными цифрами, не хватит атомов во Вселенной. Но все равно приятно.
BB(5) = 47,176,870
Что такое Busy Beaver? Попробую вкратце объяснить.
В информатике есть понятие "машина Тьюринга". Это не настоящая физическая машина из транзисторов, а теоретическая модель. Представьте себе бесконечную ленту, состоящую из ячеек, в каждой из которых может быть записано '0' или '1' (в общем случае можно и больше разных символов, но достаточно двух). Изначально на ленте везде написано '0', и над одной из ячеек находится головка чтения-записи, которая может находиться в одном из нескольких состояний (представьте себе переключатель, который может быть в положении A,B,C или D - это пример 4 состояний). За один шаг головка машины смотрит, что написано на ячейке, над которой она сейчас находится, а потом справляется в "таблице переходов". В таблице написано, например: если ты в состоянии A и видишь 0, то перейди в состояние B, напиши 1, и сдвинься вправо. И так на любую комбинацию "состояние-что я вижу" есть рецепт: в какое состояние перейти, что написать, 0 или 1, и куда сдвинуться, влево или вправо. Потом машина делает следующий шаг по таким же правилам. И так далее, пока она не войдет в состояние, которое заранее считается "конечным", например D, и тогда она останавливается.
В принципе такая модель может выполнять все, что мы считаем "алгоритмом" и поручаем компьютерам. Внутри вашего компьютера (или телефона) есть процессор, который понимает только нули и единицы. И хотя он работает сразу с многими нулями/единицами одновременно, и выполняет сложные программы, все, что он делает, в принципе можно смоделировать как машину Тьюринга (с очень большим числом состояний). Такая машина может получать входные данные не с клавиатуры, а записанные заранее на ее ленте, и выдавать результат не на экране, а тоже на своей ленте. Ученые используют эту модель в основном для того, чтобы доказывать, какие задачи компьютер не может выполнить никогда даже в принципе, или какие алгоритмы принципиально намного быстрее или медленнее других.
В 1962 году венгерско-американский математик Тибор Радо задал следующий вопрос. Обычно для того, чтобы сделать что-нибудь "интересное" машиной Тьюринга, нужно много состояний. Состояния играют роль внутренней логики алгоритма, позволяют машине "помнить", где она находится внутри сложного алгоритма, что она уже выяснила, итд. Но давайте для любого N посмотрим на все возможные машины (т.е. разные таблицы перехода) из N состояний, и что они делают с пустой лентой (все нули). Одни программы быстро остановятся, войдя в состояние остановки; другие войдут в бесконечный цикл, или уйдут "в бесконечность" без цикла - например, будут писать 1, двигаясь все дальше и дальше по бесконечной ленте без возврата. Но есть какая-то машина, которая в конце концов остановится, но после наибольшего числа шагов по сравнению со всеми остальными из N состояний. Такая машина-чемпион называется Busy Beaver. Сколько шагов она сделает перед тем, как остановится, для данного N?
Для очень малого числа состояний, 1-2-3, легко перебрать все возможные машины и посмотреть, что они делают, слишком примитивными они являются. Для 4 состояний максимальное число шагов перед остановкой равно 107, и это доказали в 1983 году. Однако уже 5 состояний позволяют сделать хитрые машины, про которые нелегко понять, они делают что-то бесконечное, или все-таки остановятся рано или поздно. С 1990 года есть кандидат - машина, которая останавливается после 47 миллионов шагов - но чтобы доказать, что она чемпион, нужно перебрать все возможные машины из 5 состояний, а их 16 триллионов! Проблема в том, что нет универсального метода определить, остановится данная машина или нет (это как раз "проблема остановки", которую принципиально невозможно решить с помощью алгоритма). Можно либо запускать ее на симуляторе, желательно очень оптимизированном, делающим миллионы шагов в секунду, и ждать, пока она остановится, либо искать математическое доказательство того, что никогда не остановится - а его надо искать для каждого сложного случая отдельно. К началу 2000-х осталось только около 40 сложных случаев - машин, которые скорее всего никогда не останавливаются, но доказать это пока не могли. В принципе могло бы оказаться и так, что одна из них "моделирует" сложную математическую проблему. Скажем, есть машина из 23 состояний, которая останавливается только если неверна знаменитая гипотеза Гольдбаха, которую никто не может доказать уже несколько сотен лет. Но 5 состояний все же настолько мало, что такое казалось маловероятным. И вот, после нескольких лет усердной работы фанатов этой проблемы в последние годы, им удалось избавиться от всех сложных случаев, и доказать то, что все подозревали - что кандидат 1990 года и есть чемпион. Все технические подробности - на сайте bbchallenge.org!
Проблема Busy Beaver - странная, любопытная штука. С одной стороны, не очень ясно, зачем ей заниматься. Найти общую формулу или метод для любого N невозможно в принципе. Ответ для N=5 никакой конкретной пользы ни для чего не приносит. Ответ для N=6 скорее всего останется недоступен для человечества за все время его существования. Более того, то, как именно сформулирована задача (какое из нескольких определений простой машины Тьюринга используется, например) "все меняет" в смысле ответа и его доступности нашим усилиям, так что задача в любом случае довольно "искусственно" выглядит. И все равно есть что-то притягательное в ней для горстки программистов и математиков, которые продолжали активно работать над ней все эти годы.
Я это хорошо понимаю, потому что много лет назад внес свой крохотный вклад в этот сизифов труд. Тогда был свежий и многообещающий кандидат в ряды Busy Beaver из 6 состояний, который останавливался после 8 квадриллионов шагов (квадриллион это миллион миллиардов), но этот факт еще никто не подтвердил независимо от первооткрывателя этой машины (столько шагов невозможно было запустить "напрямую" симулятором, надо было придумать и написать специальную программу, которая использует логику этой конкретной машины). Я помню, что написал такую программу, подтвердил результат и послал первооткрывателю, но не мог вспомнить сегодня, когда это сделал, думал, что где-то в начале 2000-х. Но потом нашел упоминание, которое все еще лежит на сайте этого человека: "No 2 has been verified independently by Anatoly Vorobey
at 20 Sep 1997. He was the first to detect that the original number of steps were one too large (corrected above)."
Я уже 20 лет не пользуюсь этим мейлом. Я забыл, что поправил на 1 количество шагов этого кандидата. Сам кандидат три года спустя был заменен другим, гораздо более крутым по числу шагов, а потом снова и снова - тот кандидат, что есть сейчас, останавливается после невообразимо огромного числа шагов, это число не записать обычными цифрами, не хватит атомов во Вселенной. Но все равно приятно.
BB(5) = 47,176,870