Занятой бобер

Чтобы узнать об анимационном фильме «Глупые симфонии» 1931 года, см. «Занятые бобры» . Информацию об онлайн-образовательной программе для детей см. в разделе «Занятые бобры» .

В теоретической информатике игра занятого бобра направлена ​​на поиск завершающей программы заданного размера, которая выдает максимально возможный результат. Поскольку легко придумать программу с бесконечным циклом, производящую бесконечный вывод или работающую бесконечное время, такие программы исключаются из игры. Иногда это также формулируют как поиск машины, которая работает дольше всех, но обе игры одинаково сложны.

Точнее, игра занятого бобра состоит из разработки останавливающейся машины Тьюринга с алфавитом {0,1}, которая записывает на ленту наибольшее количество единиц, используя только заданный набор состояний. Правила игры с двумя состояниями следующие:

1. машина должна иметь не более двух состояний помимо состояния остановки, и
2. лента изначально содержит только 0.

Игроку следует придумать таблицу переходов, стремящуюся к максимально длинному выходному сигналу в 1 с на ленте, при этом гарантируя, что машина в конечном итоге остановится.

занятой n-й бобер , BB- n или просто «занятый бобер» — это машина Тьюринга, которая выигрывает игру занятого бобра с n состояниями. То есть она достигает наибольшего числа единиц среди всех других возможных конкурирующих машин Тьюринга с n -состояниями. шагов . Например, машина Тьюринга BB-2 получает четыре единицы за шесть

Определить количество единиц или время работы n-го Busy Beaver невозможно . Это имеет значение для теории вычислимости , проблемы остановки и теории сложности . Эта концепция была впервые представлена ​​Тибором Радо в его статье 1962 года «О невычислимых функциях».

Игра

Игра n занятого бобра с состояниями (или BB -n игра ), представленная в статье Тибора Радо 1962 года, включает в себя класс машин Тьюринга , каждый член которых должен соответствовать следующим конструктивным спецификациям:

• Машина имеет n «рабочих» состояний плюс состояние «Останов», где n — целое положительное число, и одно из n состояний считается стартовым. (Обычно состояния обозначаются цифрами 1, 2, ..., n , причем состояние 1 является начальным состоянием, или A , B , C , ..., состояние A является начальным состоянием.)
• Машина использует одну двустороннюю бесконечную (или неограниченную) ленту.
• Алфавит ленты — {0, 1}, где 0 служит пустым символом.
• машины Функция перехода принимает два входа:

1. текущее состояние без остановки,
2. символ в текущей ячейке ленты,

и производит три вывода:

1. символ для записи поверх символа в текущей ячейке ленты (это может быть тот же символ, что и перезаписанный символ),
2. направление перемещения (влево или вправо; то есть сдвиг к ячейке ленты на одно место влево или вправо от текущей ячейки) и
3. состояние перехода (которое может быть состоянием остановки).

Таким образом, имеется (4 n + 4) ^{2 н} Машины Тьюринга с n состояниями соответствуют этому определению, поскольку общий вид формулы следующий: ( символы × направления × ( состояния + 1)) ^{( символы × состояния )} .

Функцию перехода можно рассматривать как конечную таблицу из 5 кортежей, каждый из которых имеет форму

(текущее состояние, текущий символ, символ для записи, направление сдвига, следующее состояние).

«Запуск» машины состоит из запуска в начальном состоянии, где текущей ячейкой ленты является любая ячейка пустой ленты (все 0), а затем итерации функции перехода до тех пор, пока не будет введено состояние «Остановка» (если вообще когда-либо). Если и только если машины машина в конце концов останавливается, то количество единиц, окончательно оставшихся на ленте, называется счетом .

Игра «Занятый бобр» с n состояниями (BB- n ) — это соревнование по поиску такой машины Тьюринга с n состояниями, которая имеет максимально возможный результат — наибольшее количество единиц на ленте после остановки. Машина, которая набирает максимально возможный балл среди всех машин Тьюринга с n -состояниями, называется занятым бобром с n -состояниями, а машина, результат которой является лишь самым высоким из достигнутых на данный момент результатов (возможно, не самым большим из возможных), называется чемпионом с n -состояниями. машина.

Учитывая эти правила, при любом переходе в состояние «Остановка» запись 1 всегда дает более высокий балл, чем запись 0. При переходе в состояние «Остановка» необходимо учитывать только одно направление, поскольку конечное положение ленты не влияет на оценку. Поэтому на практике количество рассматриваемых машин Тьюринга с n - состояниями можно сократить до (4 n + 1). ^{2 н} . раз Пространство поиска можно дополнительно сократить в ( n - 1) ! отметив, что окончательный результат не меняется при перестановке всех состояний, кроме «Старт» и «Остановка».

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

Связанные функции

Функция занятого бобра Σ

Функция занятого бобра количественно определяет максимальный балл, который может получить занятый бобр по заданному показателю. Это невычислимая функция . Кроме того, можно показать, что занятая функция бобра растет асимптотически быстрее, чем любая вычислимая функция.

Функция занятого бобра, $\Sigma :\mathbb {N} \to \mathbb {N}$, определяется так, что Σ( n ) представляет собой максимально достижимую оценку (максимальное количество единиц, наконец, на ленте) среди всех останавливающихся 2-символьных машин Тьюринга с n состояниями описанного выше типа при запуске на пустой ленте.

Ясно, что Σ является четко определенной функцией: для каждого n существует не более конечного числа с n машин Тьюринга состояниями, как указано выше, с точностью до изоморфизма, следовательно, не более конечного числа возможных времен работы.

Эта бесконечная последовательность Σ является функцией занятого бобра , и любая с n 2-символьная машина Тьюринга M состояниями , для которой σ ( M ) = Σ( n ) (т. е. которая достигает максимального значения), называется занятым бобром . Обратите внимание, что для каждого n существует не менее 4( n - 1)! n - состояние занятых бобров. (Для любого занятого бобра с n состояниями другое получается путем простого изменения направления сдвига при останавливающемся переходе, третье - путем равномерного изменения всех направлений сдвига, а четвертое - путем изменения направления остановки занятого бобра, в котором все заменены местами. Кроме того, перестановка всех состояний, кроме «Старт» и «Остановка», дает машину, которая набирает один и тот же балл. Теоретически может быть более одного типа перехода, ведущего к состоянию остановки, но на практике это было бы расточительно, поскольку существует только одна последовательность состояний. переходы, дающие искомый результат.)

Невычислимость

Статья Радо 1962 года доказала, что если $f:\mathbb {N} \to \mathbb {N}$ — любая вычислимая функция , то Σ( n ) > f ( n ) для всех достаточно больших n , и, следовательно, Σ не является вычислимой функцией.

Более того, это означает, что невозможно решить с помощью общего алгоритма , является ли произвольная машина Тьюринга занятым бобром. (Такой алгоритм не может существовать, потому что его существование позволило бы вычислить Σ, что является доказанной невозможностью. В частности, такой алгоритм можно использовать для построения другого алгоритма, который будет вычислять Σ следующим образом: для любого заданного n каждый из конечное число 2-символьных машин Тьюринга с n состояниями будет тестироваться до тех пор, пока не будет найден занятый бобер с n состояниями; затем эта занятая машина бобра будет смоделирована для определения ее оценки, которая по определению равна Σ( n ).)

Несмотря на то, что Σ( n ) является невычислимой функцией, существуют некоторые малые n , для которых можно получить ее значения и доказать, что они верны. Нетрудно показать, что Σ(0) = 0, Σ(1) = 1, Σ(2) = 4, и со все большей трудностью можно показать, что Σ(3) = 6 и Σ(4) = 13 (последовательность A028444 в OEIS ). Σ( n ) еще не была определена ни для одного случая n > 4, хотя нижние границы были установлены (см. раздел « Известные значения» ниже).

В 2016 году Адам Йедидиа и Скотт Ааронсон получили первую (явную) верхнюю оценку минимального n, для которого Σ( n ) недоказуемо в ZFC . Для этого они построили штат 7910. Машина Тьюринга, поведение которой не может быть доказано на основе обычных аксиом теории множеств ( теория множеств Цермело–Френкеля с аксиомой выбора ), при разумных гипотезах непротиворечивости ( стационарное свойство Рамсея ). Затем Стефан О'Рир сократил его до 1919 штатов, устранив зависимость от стационарной собственности Рэмси. а затем в 748 штатов. В июле 2023 года Рибель сократил его до 745 штатов.

Сложность и недоказуемость Σ

Вариант колмогоровской сложности определяется следующим образом: Сложность — это наименьшее количество состояний, необходимое для машины Тьюринга класса BB , числа n которая останавливается на одном блоке из n последовательных единиц на изначально пустой ленте. Соответствующий вариант теоремы Чайтина о неполноте утверждает, что в контексте данной аксиоматической системы для натуральных чисел существует число k такое, что ни одно конкретное число не может иметь сложность, превышающую k , и, следовательно, не существует конкретной верхней границы может быть доказано для Σ( k ) (последнее связано с тем, что «сложность n больше k » была бы доказана, если бы было доказано n > Σ( k ) . Как упоминалось в цитируемой ссылке, для любой аксиоматической системы «обычной математики» наименьшее значение k , для которого это верно, намного меньше 10⇈10 ; следовательно, в контексте обычной математики ни значение, ни верхняя граница Σ(10⇈10) не могут быть доказаны. ( Первая теорема Гёделя о неполноте иллюстрируется этим результатом: в аксиоматической системе обычной математики существует истинное, но недоказуемое предложение вида Σ(10⇈10) = n , и существует бесконечно много истинных, но недоказуемых предложений вида Σ(10⇈10) < n .)

Функция максимального смещения S

В дополнение к функции Σ Радо [1962] ввел еще одну экстремальную функцию для машин Тьюринга, функцию максимального сдвига , S определенную следующим образом:

• s ( M ) = количество сдвигов, которые делает перед остановкой, для любого M ∈ En _M ,
• S ( п ) знак равно Макс { s ( M ) | M ∈ En ₂ } = наибольшее число сдвигов, сделанных любой останавливающейся -символьной машиной Тьюринга с n состояниями.

Поскольку от этих машин Тьюринга требуется сдвиг при каждом переходе или «шаге» (включая любой переход в состояние остановки), функция максимальных сдвигов в то же время является функцией максимальных шагов.

Радо показал, что S невычислима по той же причине, по которой невычислима Σ: она растет быстрее, чем любая вычислимая функция. Он доказал это, просто заметив, что для каждого S n ( n ) ≥ Σ( n ). Каждый сдвиг может записать на ленту 0 или 1, тогда как Σ подсчитывает подмножество сдвигов, на которых записана 1, а именно те, которые не были перезаписаны к моменту остановки машины Тьюринга; следовательно, S растет по крайней мере так же быстро, как Σ, которая, как уже было доказано, растет быстрее, чем любая вычислимая функция.

Следующая связь между Σ и S была использована Лин и Радо [ Компьютерные исследования проблем машины Тьюринга , 1965] для доказательства того, что Σ(3) = 6: Для данного n , если S ( n ) известно, то все n -состояния Машины Тьюринга (в принципе) могут работать до S ( n ) шагов, после чего любая машина, которая еще не остановилась, никогда не остановится. В этот момент, наблюдая, какие машины остановились с наибольшим количеством единиц на ленте (т. е. занятые бобры), можно получить из их лент значение Σ( n ). Подход, использованный Лином и Радо для случая n = 3, заключался в предположении, что S (3) = 21, а затем в моделировании всех существенно разных автоматов с тремя состояниями за 21 шаг. Анализируя поведение машин, которые не остановились в течение 21 шага, им удалось показать, что ни одна из этих машин никогда не остановится, тем самым доказав гипотезу о том, что S (3) = 21, и определив, что Σ(3) = 6 по формуле только что описанную процедуру.

Неравенства, связывающие Σ и S, включают следующие (из [Ben-Amram, et al., 1996]), которые справедливы для всех n ≥ 1 :

${\begin{aligned}S(n)&\geq \Sigma (n)\\S(n)&\leq (2n-1)\Sigma (3n+3)\\S(n)&<\Sigma (3n+6);\end{aligned}}$

и асимптотически улучшенная оценка (из [Ben-Amram, Petersen, 2002]): существует константа c такая, что для всех n ≥ 2

$S(n)\leq \Sigma \left(n+\left\lceil {\frac {8n}{\log _{2}n}}\right\rceil +c\right).$

$S(n)$ имеет тенденцию быть близко к квадрату $\Sigma (n)$, и ведь многие машины дают $S(n)$ меньше, чем $\Sigma ^{2}(n)$.

Σ S

По состоянию на 2016 год значения функций для Σ( n ) и S ( n ) точно известны только для n < 5 .

Нынешний (по состоянию на 2023 год) занятый чемпион по бобрам в 5 штатах производит 4098 единиц, используя 47 176 870 шагов (открыт Хайнером Марксеном и Юргеном Бунтроком в 1989 году), но остается много машин с нерегулярным поведением, которые, как полагают, никогда не останавливаются. , но не доказано, что они работают бесконечно. В разных источниках указывается разное количество таких несогласных. Скелет перечисляет 42 или 43 непроверенных машины.

На данный момент рекордный чемпион шести штатов производит более 10⇈15 (найден Павлом Кропицем в 2022 году). Как отмечалось выше, это двухсимвольные машины Тьюринга.

Милтон Грин в своей статье 1964 года «Нижняя граница сигма-функции Радо для двоичных машин Тьюринга» построил набор машин Тьюринга, демонстрирующих, что

$\Sigma (2k)>3\uparrow ^{k-2}3>A(k-2,k-2)\qquad {\text{for }}k\geq 2,$

где ↑ — обозначение Кнута, направленное вверх , а A — функция Аккермана .

Таким образом

$\Sigma (10)>3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow 3^{3^{3}}=3^{3^{3^{.^{.^{.^{3}}}}}}$

(с 3 ^{3 3} = 7 625 597 484 987 членов в экспоненциальной башне), и

$\Sigma (12)>3\uparrow \uparrow \uparrow \uparrow 3=g_{1},$

где число g ₁ — это огромное начальное значение в последовательности, определяющей число Грэма .

В 1964 году Милтон Грин разработал нижнюю оценку функции Busy Beaver, которая была опубликована в материалах симпозиума IEEE 1964 года по теории коммутационных цепей и логическому проектированию. Хайнер Марксен и Юрген Бунтрок описали это как «нетривиальную (не примитивно рекурсивную) нижнюю границу». Эту нижнюю границу можно вычислить, но она слишком сложна, чтобы ее можно было выразить в виде одного выражения в терминах n . Когда n = 8, метод дает

Σ(8) ≥ 3 × (7 × 3 ⁹² - 1) / 2 ≈ 8.248×10 ⁴⁴ .

Из текущих нижних границ можно вывести следующее:

$\Sigma (2k+1)>3\uparrow ^{k-2}31>A(k-2,k-2)\qquad {\text{for }}k\geq 2,$

Напротив, лучшая текущая (по состоянию на 2023 год) нижняя граница Σ(6) составляет 10⇈15, что больше нижней границы, заданной формулой Грина, 3 ³ = 27 (что очень мало по сравнению с этим). На самом деле она намного больше нижней границы: 3⇈3 = 3 ^{3 3} = 7 625 597 484 987 , что является первой нижней границей Грина для Σ(8), а также намного превышает вторую нижнюю границу: 3×(7×3 ⁹² −1)/2.

Доказательство невычислимости S ( n ) и Σ( n )

Предположим, что S ( n ) — вычислимая функция, и пусть EvalS обозначает TM, оценивающую S ( n ). Учитывая ленту с n 1, она создаст S ( n ) 1 на ленте, а затем остановится. Пусть Clean обозначает машину Тьюринга, очищающую последовательность единиц, изначально записанную на ленте. Пусть Double обозначает функцию вычисления машины Тьюринга n + n . Учитывая ленту с n 1, она создаст 2 n на ленте 1, а затем остановится. Создадим композицию Double | ЭвалС | Очистите и пусть n ₀ — количество состояний этой машины. Пусть Create_n ₀ обозначает машину Тьюринга, создающую n ₀ 1 на изначально пустой ленте. Эту машину можно сконструировать тривиальным образом так, чтобы она имела n ₀ состояний (состояние i записывает 1, перемещает головку вправо и переключается в состояние i + 1, за исключением состояния n ₀ , которое останавливается). Обозначим через N сумму n ₀ + n ₀ .

Обозначим через BadS композицию Create_n ₀ | Двойной | ЭвалС | Чистый . Обратите внимание, что эта машина имеет N состояний. Начиная с изначально пустой ленты, он сначала создает последовательность из n ₀ 1, а затем удваивает ее, создавая последовательность из N 1. Затем BadS создаст на ленте S ( N )1 и, наконец, очистит все единицы, а затем остановится. Но фаза очистки будет продолжаться не менее S ( N ) шагов, поэтому время работы BadS строго больше S ( N ), что противоречит определению функции S ( n ).

Невычислимость Σ( n ) может быть доказана аналогичным образом. В приведенном выше доказательстве необходимо заменить машину EvalS на EvalΣ и Clean на Increment — простой TM, ищущий на ленте первый 0 и заменяющий его 1.

Невычислимость S ( n ) также может быть установлена ​​с помощью проблемы остановки пустой ленты. Проблема остановки пустой ленты — это проблема решения для любой машины Тьюринга, остановится она или нет при запуске на пустой ленте. Проблема остановки пустой ленты эквивалентна стандартной проблеме остановки и поэтому также невычислима. Если бы S ( n ) было вычислимо, то мы могли бы решить проблему остановки пустой ленты, просто запустив любую данную машину Тьюринга с n состояниями для S ( n ) шагов; если оно до сих пор не остановилось, то никогда не остановится. Итак, поскольку проблема остановки пустой ленты невычислима, отсюда следует, что S ( n ) также должно быть невычислимым.

Обобщения

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

1. Σ( n , m ): наибольшее количество ненулевых символов, которые можно напечатать машиной с n- состоянием и m -символом, запущенной на изначально пустой ленте перед остановкой, и
2. S ( n , m ): наибольшее количество шагов, выполненных машиной с n -состоянием и m -символом, начатой ​​на изначально пустой ленте перед остановкой.

Например, самая долго работающая трехсимвольная машина с тремя состояниями, найденная на данный момент, делает 119 112 334 170 342 540 шагов, прежде чем остановиться. Самая продолжительная машина с 6 состояниями и 2 символами, имеющая дополнительное свойство переворачивать значение ленты на каждом шаге, выдает 6147 единиц после 47 339 970 шагов. Итак, для класса Обратной машины Тьюринга (RTM) S _РТМ (6) ≥ 47 339 970 и Σ _РТМ (6) ≥ 6 147 .

Функцию занятого бобра можно дополнительно обобщить, распространив ее на более чем одно измерение.

Аналогичным образом мы могли бы определить аналог функции Σ для регистровых машин как наибольшее число, которое может присутствовать в любом регистре при остановке для заданного количества инструкций.

Точные значения и нижние границы

В следующей таблице перечислены точные значения и некоторые известные нижние оценки для S ( n , m ) и Σ( n , m ) для обобщенных задач занятого бобра. Примечание: записи отмечены знаком "?" ограничены снизу максимумом всех записей слева и сверху. Эти машины либо не исследовались, либо впоследствии были заменены машинами меньшего размера.

Значения S( n , m )
н м	2-государственный	3-государственный	4-штатный	5-штат	6-штат
2-символ	6	21	107	≥ 47 176 870	> 10⇈15
3-символ	38	≥ 119 112 334 170 342 540	> 1,0 × 10 14 072	?	?
4-символ	≥ 3 932 964	> (2↑ 15 5)+14	?	?	?
5-символ	> 1,9 × 10 704	?	?	?	?
6-символ	> 10⇈10⇈10 10 115	?	?	?	?
Значения Σ( n , m )
н м	2-государственный	3-государственный	4-штатный	5-штат	6-штат
2-символ	4	6	13	≥ 4098	> 10⇈15
3-символ	9	≥ 374 676 383	> 1,3 × 10 7036	?	?
4-символ	≥ 2050	≥ (2↑ 15 5)+14	?	?	?
5-символ	> 1,7 × 10 352	?	?	?	?
6-символ	> 10⇈10⇈10 10 115	?	?	?	?

Тьюринга

Максимальное время остановки и состояния из p -case, 2-state, 2-color NDTM

п	шаги	государства
1	2	2
2	4	4
3	6	7
4	7	11
5	8	15
6	7	18
7	6	18

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

Приложения

Помимо создания довольно сложной математической игры , функции занятого бобра предлагают совершенно новый подход к решению чисто математических задач. Многие открытые проблемы математики теоретически, но не на практике, могут быть решены систематическим способом, учитывая значение S ( n ) для достаточно большого n .

Рассмотрим любую гипотезу , которую можно опровергнуть с помощью контрпримера среди счетного числа случаев (например, гипотезу Гольдбаха ). Напишите компьютерную программу, которая последовательно проверяет эту гипотезу на предмет увеличения значений. В случае гипотезы Гольдбаха мы последовательно рассматривали бы каждое четное число ≥ 4 ​​и проверяли, является ли оно суммой двух простых чисел. Предположим, что эта программа моделируется на машине Тьюринга с n состояниями. Если он находит контрпример (четное число ≥ 4, которое не является суммой двух простых чисел в нашем примере), он останавливается и указывает на это. Однако если гипотеза верна, то наша программа никогда не остановится. (Эта программа останавливается, только если находит контрпример.)

Теперь эта программа моделируется машиной Тьюринга с n состояниями, поэтому, если мы знаем S ( n ), мы можем решить (за конечный промежуток времени), остановится ли она когда-либо или нет, просто запустив машину на такое количество шагов. И если после S ( n ) шагов машина не остановится, мы знаем, что она никогда не остановится и, следовательно, не существует контрпримеров к данной гипотезе (т. е. не существует четных чисел, не являющихся суммой двух простых чисел). Это докажет, что гипотеза верна.

Таким образом, конкретные значения (или верхние границы) для S ( n ) можно использовать для систематического решения многих открытых проблем математики (теоретически). Однако текущие результаты по проблеме занятого бобра предполагают, что это не будет практично по двум причинам:

• Чрезвычайно сложно доказать значения функции занятого бобра (и функции максимального сдвига). Это было доказано только для очень маленьких машин с менее чем пятью состояниями, тогда как предположительно потребуется как минимум 20-50 состояний. сделать полезную машину. Более того, каждое известное точное значение S ( n ) было доказано путем перечисления каждой машины Тьюринга с n состояниями и проверки того, останавливается ли каждая из них. пришлось бы вычислить S ( n ) каким-то менее прямым методом. Чтобы это действительно было полезно,
• Но даже если бы кто-то нашел лучший способ вычисления S ( n ), значения функции занятого бобра (и функции максимального сдвига) станут очень большими и очень быстро. С (6) > 10 ^36,534 для завершения моделирования уже требуется специальное ускорение на основе шаблонов. Точно так же мы знаем, что $S(10)>\Sigma (10)>3\uparrow \uparrow \uparrow 3$ – гигантское число и S (17) > Σ(17) > G > g ₁ , где G – число Грэма – огромное число. Таким образом, даже если бы мы знали, скажем, S (30), совершенно неразумно запускать какую-либо машину на такое количество шагов. В известной части Вселенной недостаточно вычислительных мощностей, чтобы напрямую выполнить даже S (6) операций.

Известные случаи

Была построена двоичная машина Тьюринга с 745 состояниями, которая останавливается тогда и только тогда, когда ZFC несовместим. Была построена машина Тьюринга с 744 состояниями, которая останавливается тогда и только тогда, когда гипотеза Римана ложна. Была построена машина Тьюринга с 43 состояниями, которая останавливается тогда и только тогда, когда гипотеза Гольдбаха ложна, а машина с 27 состояниями для этой гипотезы была предложена, но еще не проверена.

Была построена машина Тьюринга с 15 состояниями, которая останавливается тогда и только тогда, когда следующая гипотеза, сформулированная Полом Эрдешем в 1979 году, неверна: для всех n > 8 существует хотя бы одна цифра 2 в представлении числа 2 по основанию 3. ^н .

Примеры

Пример таблицы состояний занятого бобра с 3 состояниями и ее «запуска» см. в разделах « Примеры машины Тьюринга» § «Занятый бобер с 3 состояниями» и «Примеры машины Тьюринга» .

Показывает первые 100 000 временных шагов лучшего на данный момент занятого бобра с 5 состояниями. Оранжевый — «1», белый — «0» (изображение сжато по вертикали).

Это таблицы правил для машин Тьюринга, генерирующих Σ(1) и S (1), Σ(2) и S (2), Σ(3) (но не S (3)), Σ(4) и S. (4) и наиболее известную нижнюю оценку для Σ(5) и S (5), а также Σ(6) и S (6).

В таблицах столбцы представляют текущее состояние, а строки представляют текущий символ, считанный с ленты. Каждая запись таблицы представляет собой строку из трех символов, указывающую символ для записи на ленту, направление перемещения и новое состояние (именно в этом порядке). Состояние остановки отображается как H .

Каждая машина начинается в состоянии A с бесконечной ленты, содержащей все 0. Таким образом, начальный символ, считанный с ленты, равен 0.

позиции Ключ результата: (начинается с подчеркнутой позиции , заканчивается в подчеркнутой )

Занятый бобр с 1 состоянием и 2 символами

	А
0	1р ч
1	(не используется)

Результат: 0 0 1 0 0 (1 шаг, всего одна «1»)

Занятый бобр с 2 состояниями и 2 символами

	А	Б
0	1Р Б	1л А
1	1л Б	1р ч

Результат: 0 0 1 1 1 1 0 0 (6 шагов, всего четыре единицы)

Анимация занятого бобра с 3 состояниями и 2 символами

Занятый бобр с 3 состояниями и 2 символами

	А	Б	С
0	1Р Б	0Р С	1л С
1	1р ч	1Р Б	1л А

Результат: 0 0 1 1 1 1 1 1 0 0 (14 шагов, всего шесть единиц).

предыдущих машин, эта занята только для Σ, но не для S. В отличие от ( С (3) = 21.)

Анимация занятого бобра с 4 состояниями и 2 символами

Занятый бобр с 4 состояниями и 2 символами

	А	Б	С	Д
0	1Р Б	1л А	1р ч	1р д
1	1л Б	0Л С	1л д	0Р А

Результат: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 шагов, всего тринадцать единиц)

текущий лучший претендент на 5 штатов, 2 символа (возможно, занятой бобер)

	А	Б	С	Д	И
0	1Р Б	1р С	1р д	1л А	1р ч
1	1л С	1Р Б	0Л Э	1л д	0Л А

Результат: 4098 «1» с 8191 «0», разбросанными по 47 176 870 шагам.

Обратите внимание на изображение справа, насколько это решение качественно похоже на эволюцию некоторых клеточных автоматов .

текущий лучший претендент на 6 штатов и 2 символа

	А	Б	С	Д	И	Ф
0	1Р Б	1р С	1л С	0Л Э	1л Ф	0Р С
1	0Л Д	0Р Ф	1л А	1р ч	0Р Б	0Р Э

Результат: 1 0 1 1 1 ... 1 1 1 («10» с последующими более чем 10↑↑15 последовательными «1» за более чем 10↑↑15 шагов, где 10↑↑15=10 ^{10 . . 10} , показательная башня из 15 десятков).

Визуализации

В следующей таблице правила для каждого занятого бобра (максимизирующего Σ) представлены визуально: оранжевые квадраты соответствуют цифре «1» на ленте, а белые соответствуют «0». Положение головы обозначено черным овалом, а ориентация головы представляет состояние. Отдельные ленты раскладываются горизонтально, с течением времени сверху вниз. Состояние остановки представлено правилом, которое отображает одно состояние само на себя (голова не движется).

Эволюция занятых бобров с 1-4 состояниями.

Правила для занятого бобра с 1 состоянием

Правила для занятого бобра с двумя состояниями

Правила для занятого бобра с 3 состояниями

Правила для занятого бобра с 4 состояниями

Эволюция занятого бобра с 1 состоянием до остановки. Начальное состояние вызывает остановку, перед завершением записывается одна цифра «1».

Эволюция занятого бобра с двумя состояниями до остановки

Эволюция занятого бобра с тремя состояниями до остановки

Эволюция занятого бобра с 4 состояниями вплоть до остановки. Нижняя строка левого изображения переносится на верхнюю строку правого изображения. На последнем этапе перед остановкой записывается «1» (не показано).

См. также

• номер Райо
• Турмит

Ссылки

• Радо, Тибор (май 1962 г.). «О невычислимых функциях» (PDF) . Технический журнал Bell System . 41 (3): 877–884. дои : 10.1002/j.1538-7305.1962.tb00480.x .

  Именно здесь Радо впервые сформулировал проблему занятого бобра и доказал, что она невычислима и растет быстрее, чем любая вычислимая функция.

• Линь, Шен; Радо, Тибор (апрель 1965 г.). «Компьютерные исследования проблем машины Тьюринга» . Журнал АКМ . 12 (2): 196–212. дои : 10.1145/321264.321270 . S2CID   17789208 .

  Результаты этой статьи уже частично были опубликованы в докторской диссертации Линя в 1963 году под руководством Радо. Лин и Радо доказывают, что Σ(3) = 6 и S (3) = 21, доказывая, что все 2-символьные машины Тьюринга с 3 состояниями, которые не останавливаются в течение 21 шага, никогда не остановятся. (Большинство из них доказываются автоматически с помощью компьютерной программы, однако 40 случаев доказываются при проверке человеком.)

• Брэди, Аллен Х. (апрель 1983 г.). «Определение значения невычислимой функции Радо Σ( k ) для машин Тьюринга с четырьмя состояниями» . Математика вычислений . 40 (162): 647–665. дои : 10.1090/S0025-5718-1983-0689479-6 . JSTOR   2007539 .

  Брейди доказывает, что Σ(4) = 13 и S (4) = 107. Брейди определяет две новые категории для непрерывных 2-символьных машин Тьюринга с 3 состояниями: рождественские елки и счетчики. Он использует компьютерную программу, чтобы доказать, что все машины, кроме 27, которые выполняют более 107 шагов, являются вариантами рождественских елок и счетчиков, которые, как можно доказать, могут работать бесконечно. После личного осмотра самого Брейди доказано, что последние 27 машин (называемых оставшимися) не остановились.

• Махлин, Рона; Стаут, Квентин Ф. (июнь 1990 г.). «Сложное поведение простых машин» . Физика D: Нелинейные явления . 42 (1–3): 85–98. Бибкод : 1990PhyD...42...85M . дои : 10.1016/0167-2789(90)90068-Z . hdl : 2027.42/28528 .

  Махлин и Стаут описывают проблему занятого бобра и многие методы, используемые для поиска занятых бобров (которые они применяют к машинам Тьюринга с 4 состояниями и 2 символами, тем самым проверяя доказательство Брейди). Они предлагают, как оценить вариант вероятности остановки Чайтина (Ω).

• Марксен, Хайнер; Бунтрок, Юрген (февраль 1990 г.). «Атака на занятого бобра 5» . Бюллетень ЕАТКС . 40 : 247–251. Архивировано из оригинала 9 октября 2006 г. Проверено 19 января 2020 г.

  Марксен и Бантрок демонстрируют, что Σ(5) ≥ 4098 и S (5) ≥ 47 176 870 , и подробно описывают метод, который они использовали для поиска этих машин, и доказывают, что многие другие никогда не остановятся.

• Грин, Милтон В. (1964). Нижняя граница сигма-функции Радо для двоичных машин Тьюринга . 1964 г. Труды пятого ежегодного симпозиума по теории переключающих цепей и логическому проектированию . стр. 91–94. дои : 10.1109/SWCT.1964.3 .

  Грин рекурсивно конструирует машины для любого количества состояний и предоставляет рекурсивную функцию, которая вычисляет их оценку (вычисляет σ), тем самым обеспечивая нижнюю оценку Σ. Рост этой функции сравним с ростом функции Аккермана .

• Дьюдни, Александр К. (1984). «Компьютерная ловушка для занятого бобра, самая трудолюбивая машина Тьюринга». Научный американец . 251 (2): 10–17.

  Программы занятых бобров описаны Александром Дьюдни в журнале Scientific American , август 1984 г., стр. 19–23, а также март 1985 г., стр. 23 апреля 1985 г. с. 30 .

• Чайтин, Грегори Дж . (1987). «Вычисление функции занятого бобра» (PDF) . В Прикрытии, ТМ; Гопинатх, Б. (ред.). Открытые проблемы коммуникации и вычислений . Спрингер. стр. 108–112. ISBN  978-0-387-96621-2 . Архивировано из оригинала (PDF) 30 декабря 2017 г. Проверено 7 июля 2022 г.
• Брэди, Аллен Х. (1995). «Игра занятого бобра и смысл жизни». В Херкене, Рольф (ред.). Универсальная машина Тьюринга: обзор полувека (2-е изд.). Вена, Нью-Йорк: Springer-Verlag. стр. 237–254. ISBN  978-3-211-82637-9 .

  При этом Брэди (известный в четырех штатах) описывает некоторую историю зверя и называет его преследование «Игрой занятого бобра». Он описывает другие игры (например, клеточные автоматы и «Игру жизни» Конвея ). Особый интерес представляет «Игра занятого бобра в двух измерениях» (с. 247). С 19 ссылками.

• Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов . Нью-Йорк: Уайли. ISBN  978-0-471-08848-6 .

  См. главу 9 «Машины Тьюринга». Сложная книга, предназначенная для инженеров-электриков и технических специалистов. Обсуждает рекурсию, частичную рекурсию со ссылкой на машины Тьюринга, проблему остановки. Упоминание в Буте приписывает Rado занятого бобра. Бут также определяет проблему занятого бобра Радо в «домашних проблемах» 3, 4, 5, 6 главы 9, с. 396. Задача 3 состоит в том, чтобы «показать, что проблема занятого бобра неразрешима... для всех значений n».

• Бен-Амрам, AM; Юльстром, бакалавр; Цвик, У. (1996). «Заметка о занятых бобрах и других существах» . Теория математических систем . 29 (4): 375–386. CiteSeerX   10.1.1.75.1297 . дои : 10.1007/BF01192693 . S2CID   30937913 . Архивировано из оригинала 21 июля 2018 г. Проверено 7 июля 2022 г.

  Границы между функциями Σ и S .

• Бен-Амрам, AM; Петерсен, Х. (2002). «Улучшенные границы для функций, связанных с занятыми бобрами». Теория вычислительных систем . 35 : 1–11. CiteSeerX   10.1.1.136.5997 . дои : 10.1007/s00224-001-1052-0 . S2CID   10429773 .

  Улучшенные границы.

• Лафит, Г.; Папазян, К. (июнь 2007 г.). «Ткань маленьких машин Тьюринга». Вычисления и логика в реальном мире, Материалы Третьей конференции по вычислимости в Европе . стр. 219–227. CiteSeerX   10.1.1.104.3021 .

  Эта статья содержит полную классификацию машин Тьюринга с 2 состояниями и 3 символами и, следовательно, доказательство для (2, 3) занятого бобра: Σ(2, 3) = 9 и S(2, 3) = 38.

• Булос, Джордж С.; Берджесс, Джон П.; Джеффри, Ричард С. (2007). Вычислимость и логика (Пятое изд.). Издательство Кембриджского университета. ISBN  978-0-521-87752-7 .
• Кропиц, Павел (2010). Problém Busy Beaver (бакалаврская диссертация) (на словацком языке). Карлов университет в Праге.

  Это описание идей, алгоритмов и их реализации, с описанием экспериментов по изучению машин Тьюринга с 5 и 6 состояниями при параллельном запуске на 31 4-ядерном компьютере и, наконец, лучших результатов для TM с 6 состояниями.

Внешние ссылки

• Страница Хайнера Марксена , который вместе с Юргеном Бунтроком нашел вышеупомянутые записи для машины Тьюринга с 5 и 6 состояниями.
• Паскаля Мишеля , который также содержит лучшие результаты и некоторый анализ. Исторический обзор результатов занятых бобров
• Определение класса RTM — обратные машины Тьюринга, простой и сильный подкласс TM.
• « Проблема занятого бобра: атака нового тысячелетия » ( в архиве ) в лаборатории Rensselaer RAIR. В результате этих усилий было обнаружено несколько новых рекордов и установлено несколько значений четверной формализации.
• Дэниела Бриггса веб-сайта Архив и форум для решения проблемы занятого бобра с 5 состояниями и 2 символами на основе Скелета (Георги Георгиева). списка нерегулярных машин
• Лигоцки, Шон (17 июля 2021 г.). «Коллатцоподобное поведение занятых бобров» . слигоцкий . Проверено 12 июля 2022 г.
• Ааронсон, Скотт (1999), Кто может назвать большее число?
• Вайсштейн, Эрик В. «Занятой бобер» . Математический мир .
• Машины Тьюринга Busy Beaver — компьютерщики , Youtube
• Паскаль Мишель. Конкурс «Занятый бобр»: исторический обзор . 70 страниц. 2017. <hal-00396880v5>