Knowledge Accumulator

Чему равен усердный бобр?

Продолжаем путешествие по автосалону Тьюринга. Как я уже говорил, представленные машины руководствуются предельно простой логикой, и сложность их поведения напрямую зависит от размера пространства состояний. Но даже небольшого числа хватает для выполнения чего-то разумного, например, вот эта машина умножает 2 бинарных числа, используя 13 состояний.

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

Это называется Halting Problem - по заданной программе машины Тьюринга и входным данным определить, остановится она или попадёт в бесконечный цикл. Было доказано, что отвечающего на это алгоритма в общем случае не может существовать. Пруф остаётся в качестве упражнения для читателя.

Рассмотрим все машины Тьюринга с N состояний, которые остановятся, если их запустить на ленте из нулей. Какая из них работает дольше всех? Максимальное количество шагов и называется функцией усердного бобра - Busy Beaver - BB(N)

Несмотря на кажущуюся пустяковость и смешное название, эта функция - практически final boss среди последовательностей. Она растёт очень, очень, ОЧЕНЬ быстро. Начинается она вменяемо - BB(2) = 6, BB(3) = 21, BB(4) = 107.

Ещё в 1990 году была найдена машина из 5 состояний, которая работает 47,176,870 шагов. Но здесь Тьюринг наносит нам лоу-кик - BB(N) невычислима. Так как невозможно определить, остановится ли произвольная машина Тьюринга, чтобы доказать значение BB(N), необходимо по отдельности доказать зацикливаемость всех машин, которые работают дольше BB(N). Одним из следствий этого является то, что BB(N) растёт быстрее всех функций, которые можно описать конечным алгоритмом.

Звучит, как абсолютно бесполезная на практике проблема, которую должны решать почётные доктора наук за государственные деньги, да? Как бы не так!

Многие исследователи-"любители" посчитали, что задача достаточно весёлая, чтобы самоорганизоваться ради её решения. В 2022 году был создан так называемый The Busy Beaver Challenge - центр притяжения фанатов данной проблемы. Они создали сайт, вики, дискорд и взялись за работу.

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

Конечно, для большинства из них это не является большой проблемой, но в семье не без уродов. Ещё в 2003 году Skelet опубликовал свой результат - доказательство на Паскале длиной в 6000 строк, которое работает для всех, кроме 43 особо непонятных машин. Их так и назвали - 43 машины Скелета.

Исследователи в дискорде разделились и начали расправляться с машинами Скелета. 13 из них они назвали спорадическими - их не удалось доказать общими методами. Для них в индивидуальном порядке конструировали доказательство их бесконечной работы. Чтобы вы понимали уровень сложности происходящего, приведу описание первой из них:

Skelet #1 - после по крайней мере 10^51 шагов, начинает бесконечно выдавать одинаковый паттерн каждые 8,468,569,863 шагов

Итак, спустя 2 года работы задача была полностью решена - подтверждено, что BB(5) = 47,176,870. В инструменте для формальных доказательств Coq был скомпилирован и выложен общий пруф этого утверждения, который для всех машин, работающих дольше BB(5) шагов, доказывает их зацикленность.

Что там дальше по списку, BB(6)? Да, вот вам машина, работающая 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 шагов. Впердё!

UPD. Оказалось, что неделю назад была найдена машина из 6 состояний, которая работает 10↑↑11010000 шагов - то есть 10 в 10 степени не 15 раз, а 10 миллионов. 6 состояний, Карл!

Чем же так заняты эти усердные бобры? Что можно делать так долго, оперируя всего в рамках 5 или 6 состояний? Разберём это в следующий раз, а также то, как это внезапно оказалось связано с одной из известных открытых проблем теории чисел.

@knowledge_accumulator

www.group-telegram.com/us/knowledge_accumulator.com/294

1.6K viewsedited  Jun 24 at 10:42

Чему равен усердный бобр?

Продолжаем путешествие по автосалону Тьюринга. Как я уже говорил, представленные машины руководствуются предельно простой логикой, и сложность их поведения напрямую зависит от размера пространства состояний. Но даже небольшого числа хватает для выполнения чего-то разумного, например, вот эта машина умножает 2 бинарных числа, используя 13 состояний.

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

Это называется Halting Problem - по заданной программе машины Тьюринга и входным данным определить, остановится она или попадёт в бесконечный цикл. Было доказано, что отвечающего на это алгоритма в общем случае не может существовать. Пруф остаётся в качестве упражнения для читателя.

Рассмотрим все машины Тьюринга с N состояний, которые остановятся, если их запустить на ленте из нулей. Какая из них работает дольше всех? Максимальное количество шагов и называется функцией усердного бобра - Busy Beaver - BB(N)

Несмотря на кажущуюся пустяковость и смешное название, эта функция - практически final boss среди последовательностей. Она растёт очень, очень, ОЧЕНЬ быстро. Начинается она вменяемо - BB(2) = 6, BB(3) = 21, BB(4) = 107.

Ещё в 1990 году была найдена машина из 5 состояний, которая работает 47,176,870 шагов. Но здесь Тьюринг наносит нам лоу-кик - BB(N) невычислима. Так как невозможно определить, остановится ли произвольная машина Тьюринга, чтобы доказать значение BB(N), необходимо по отдельности доказать зацикливаемость всех машин, которые работают дольше BB(N). Одним из следствий этого является то, что BB(N) растёт быстрее всех функций, которые можно описать конечным алгоритмом.

Звучит, как абсолютно бесполезная на практике проблема, которую должны решать почётные доктора наук за государственные деньги, да? Как бы не так!

Многие исследователи-"любители" посчитали, что задача достаточно весёлая, чтобы самоорганизоваться ради её решения. В 2022 году был создан так называемый The Busy Beaver Challenge - центр притяжения фанатов данной проблемы. Они создали сайт, вики, дискорд и взялись за работу.

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

Конечно, для большинства из них это не является большой проблемой, но в семье не без уродов. Ещё в 2003 году Skelet опубликовал свой результат - доказательство на Паскале длиной в 6000 строк, которое работает для всех, кроме 43 особо непонятных машин. Их так и назвали - 43 машины Скелета.

Исследователи в дискорде разделились и начали расправляться с машинами Скелета. 13 из них они назвали спорадическими - их не удалось доказать общими методами. Для них в индивидуальном порядке конструировали доказательство их бесконечной работы. Чтобы вы понимали уровень сложности происходящего, приведу описание первой из них:

Skelet #1 - после по крайней мере 10^51 шагов, начинает бесконечно выдавать одинаковый паттерн каждые 8,468,569,863 шагов

Итак, спустя 2 года работы задача была полностью решена - подтверждено, что BB(5) = 47,176,870. В инструменте для формальных доказательств Coq был скомпилирован и выложен общий пруф этого утверждения, который для всех машин, работающих дольше BB(5) шагов, доказывает их зацикленность.

Что там дальше по списку, BB(6)? Да, вот вам машина, работающая 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 шагов. Впердё!

UPD. Оказалось, что неделю назад была найдена машина из 6 состояний, которая работает 10↑↑11010000 шагов - то есть 10 в 10 степени не 15 раз, а 10 миллионов. 6 состояний, Карл!

Чем же так заняты эти усердные бобры? Что можно делать так долго, оперируя всего в рамках 5 или 6 состояний? Разберём это в следующий раз, а также то, как это внезапно оказалось связано с одной из известных открытых проблем теории чисел.

@knowledge_accumulator

BY Knowledge Accumulator