Занятый бобер - Busy beaver

Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) эта статья может быть слишком техническим для большинства читателей, чтобы понять. Пожалуйста помогите улучшить это к сделать понятным для неспециалистов, не снимая технических деталей. (Октябрь 2016) (Узнайте, как и когда удалить этот шаблон сообщения) Эта статья включает в себя список общих использованная литература, но он остается в основном непроверенным, потому что ему не хватает соответствующих встроенные цитаты. Пожалуйста, помогите улучшить эта статья введение более точные цитаты. (Февраль 2013) (Узнайте, как и когда удалить этот шаблон сообщения) (Узнайте, как и когда удалить этот шаблон сообщения)

В теоретическая информатика, то занятая игра бобра стремится найти прекращение программа заданного размера, обеспечивающего максимально возможную производительность.^[1]

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

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

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

An пй занятый бобер, BB-п или просто «занятой бобер» - это машина Тьюринга, которая выигрывает п-state Busy Beaver Game. То есть он достигает наибольшего числа единиц среди всех других возможных п-государственные машины Тьюринга. В BB-2 машина Тьюринга, например, получает четыре единицы за шесть шагов.

Определить, является ли произвольная машина Тьюринга занятым бобром. неразрешимый. Это имеет значение в теория вычислимости, то проблема остановки, и теория сложности. Концепция была впервые представлена Тибор Радо в его статье 1962 года «О невычислимых функциях».

Игра

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

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

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

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

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

Таким образом, (4п + 4)^2п п-состояние машины Тьюринга, отвечающее этому определению.

Более подробная версия той же формулы (символы * направления * (состояния + 1))^{(символы * состояния)}.

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

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

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

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

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

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

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

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

Функция занятого бобра, Σ: N → N, определяется так, что Σ (п) - максимально достижимая оценка (максимальное количество единиц на ленте) среди всех остановившихся двух символов п-состояние машины Тьюринга описанного выше типа при запуске с чистой ленты.

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

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

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

Работа Радо 1962 г. доказала, что если ж: ℕ → ℕ есть ли вычислимая функция, то Σ (п) > f (n) для всех достаточно больших п, а значит, Σ не вычислимая функция.

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

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

В 2016 году Адам Едидиа и Скотт Ааронсон получили первую (явную) верхнюю оценку минимума п для которого Σ (п) недоказуемо в ZFC. Для этого они построили 7910-штатный^[2] Машина Тьюринга, поведение которой нельзя доказать на основе обычных аксиом теории множеств (Теория множеств Цермело – Френкеля с аксиома выбора ), при гипотезах разумной согласованности (стационарное свойство Рамсея ).^[3][4] Позже это число было сокращено до 1919 штатов с устранением зависимости от стационарного свойства Рамсея.^[5][6] а затем в 748 штатов.^[7]

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

Вариант Колмогоровская сложность определяется следующим образом [ср. Boolos, Burgess & Jeffrey, 2007]: The сложность из числа п - наименьшее количество состояний, необходимое для машины Тьюринга BB-класса, которая останавливается одним блоком п последовательные единицы на изначально пустой ленте. Соответствующий вариант Теорема Чайтина о неполноте заявляет, что в контексте данного аксиоматическая система для натуральных чисел существует число k так что никакое конкретное число не может иметь сложность больше, чем k, и, следовательно, никакой конкретной верхней оценки для Σ (k) (последнее из-за "сложности п больше, чем k"будет доказано, если"п > Σ (k) "были доказаны). Как упоминалось в цитируемой ссылке, для любой аксиоматической системы" обычной математики "наименьшее значение k для которого это верно, намного меньше, чем 10↑↑10; следовательно, в контексте обычной математики ни значение, ни верхняя граница Σ (10 ↑↑ 10) не могут быть доказаны. (Первая теорема Гёделя о неполноте иллюстрируется этим результатом: в аксиоматической системе обычной математики есть истинное, но недоказуемое предложение вида «Σ (10 ↑↑ 10) = п", и существует бесконечно много истинных, но недоказуемых предложений вида" Σ (10 ↑↑ 10) < п".)

Функция максимальной смены S

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

• s(M) = количество смен M делает перед остановкой для любого M в E_п,
• S(п) = max { s(M) | M ∈ E_п } = наибольшее количество сдвигов, сделанных при любой остановке п-состояние 2-символьной машины Тьюринга.

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

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

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

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

${ Displaystyle { begin {выровнен} S (n) & geq Sigma (n) S (n) & leq (2n-1) Sigma (3n + 3) S (n) & < Sigma (3n + 6); конец {выровнено}}}$

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

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

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

Известные значения Σ и S

По состоянию на 2016 г. значения функции Σ (п) и S(п) известны только точно п < 5.^[4]

Текущий (по состоянию на 2018 год) чемпион занятых бобров в 5 штатах производит 4098 1s, используя 47176870 шагов (обнаруженных Хайнером Марксеном и Юргеном Бантроком в 1989 году), но остается 18 или 19 (возможно, менее 10, см. ниже) машин с нерегулярным поведением, которые, как считается, никогда не останавливаются, но которые не доказали, что работают бесконечно. Скелет перечисляет 42 или 43 недоказанных машины, но 24 уже проверены.^[8] Остальные машины были смоделированы до 81,8 миллиарда шагов, но ни одна из них не остановилась. Дэниел Бриггс тоже испытал несколько машин.^[9] Другой источник говорит, что 98 машин остаются непроверенными. Есть анализ несогласных.^[10] Таким образом, вероятно, что Σ (5) = 4098 и S (5) = 47176870, но это остается недоказанным, и неизвестно, остались ли еще несогласованные (по состоянию на 2018 год). На данный момент рекордсмен из шести штатов производит более 3.515×10¹⁸²⁶⁷ 1 с (ровно (25 * 4³⁰³⁴¹+23) / 9), используя более 7.412×10³⁶⁵³⁴ шаги (найден Павлом Кропицем в 2010 году). Как отмечалось выше, это двухсимвольные машины Тьюринга.

Простое расширение 6-конечного автомата приводит к 7-конечному автомату, который будет записывать более 10^{10101018705353} 1 с на ленту, но, несомненно, есть гораздо более загруженные машины с 7 состояниями. Однако у других занятых охотников на бобров есть другие наборы машин.

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

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

где ↑ Обозначение Кнута со стрелкой вверх и А является Функция Аккермана.

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

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

(с 3³³ = 7625597484987 члены в экспоненциальной башне), и

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

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

В 1964 году Милтон Грин разработал нижнюю границу для функции занятого бобра, которая была опубликована в трудах симпозиума IEEE 1964 года по теории коммутационных схем и логическому проектированию. Хайнер Марксен и Юрген Бантрок описали это как «нетривиальную (не примитивно рекурсивную) нижнюю границу». Эту нижнюю границу можно вычислить, но она слишком сложна, чтобы ее можно было сформулировать как единое выражение через n. При n = 8 метод дает Σ (8) ≥ 3 × (7 × 3⁹² - 1) / 2 ≈ 8.248×10⁴⁴.

Из текущих нижних оценок можно вывести, что:

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

Напротив, лучшая текущая (по состоянию на 2018 год) нижняя граница Σ (6) равна 10¹⁸²⁶⁷, что больше нижней границы, полученной по формуле Грина, 3³ = 27 (что очень мало для сравнения). На самом деле это намного больше нижней границы: 3 ↑↑ 3 = 3³³ = 7625597484987, которая является первой нижней оценкой Грина для Σ (8), а также намного превосходит вторую нижнюю оценку: 3 * (7 * 3⁹²-1)/2.

Σ (7) таким же образом намного, намного больше, чем текущая общая нижняя граница 3³¹ (почти 618 триллионов), поэтому вторая нижняя граница также очень и очень слабая.

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

Предположим, что S(п) - вычислимая функция и пусть ОЦЕНКИ обозначают TM, оценивая S(п). Учитывая ленту с п 1с он произведет S(п) 1 с на ленте, а затем остановитесь. Позволять Чистый обозначают машину Тьюринга, очищающую последовательность единиц, первоначально записанную на ленте. Позволять Двойной обозначают оценивающую функцию машины Тьюринга п + п. Учитывая ленту с п 1с он произведет 2п 1 с на ленте, а затем остановитесь. Создадим композицию Двойной | ОЦЕНКИ | Чистый и разреши п₀ быть количеством состояний этой машины. Позволять Create_n₀ обозначают машину Тьюринга, создающую п₀ 1 с на изначально пустой ленте. Эту машину можно тривиально сконструировать так, чтобы п₀ государства (состояние я пишет 1, перемещает голову вправо и переключается в состояние я + 1, кроме состояния п₀, который останавливается). Позволять N обозначим сумму п₀ + п₀.

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

Невычислимость Σ (п) доказывается аналогично. В приведенном выше доказательстве необходимо заменить машину ОЦЕНКИ с участием EvalΣ и Чистый с участием Приращение - простой TM, ищущий на ленте первый 0 и заменяющий его на 1.

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

Обобщения

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

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

Например, найденная до сих пор самая продолжительная трехсимвольная машина с 3 состояниями работает 119112334170342540 шаги перед остановкой. Самая продолжительная машина с 6 состояниями и 2 символами, которая имеет дополнительное свойство переворачивать значение ленты на каждом этапе, производит 6147 1 с после 47339970 шаги. Так S_RTM(6) ≥ 47339970 и Σ_RTM(6) ≥ 6147.

Возможно дальнейшее обобщение функции занятого бобра, расширив ее до более чем одного измерения.

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

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

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

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

Значения S (п, м)
п м	2-состояние	3 состояния	4-состояние	5-состояние	6-состояние	7-состояние
2 символа	6	21	107	47176870?	> 7.4×1036534	> 1010101018705353
3 символа	38	≥ 119112334170342540	> 1.0×1014072	?	?	?
4 символа	≥ 3932964	> 5.2×1013036	?	?	?	?
5-значное	> 1.9×10704	?	?	?	?	?
6-значное	> 2.4×109866	?	?	?	?	?
Значения Σ (п, м)
п м	2-состояние	3 состояния	4-состояние	5-состояние	6-состояние	7-состояние
2 символа	4	6	13	4098?	> 3.5×1018267	> 1010101018705353
3 символа	9	≥ 374676383	> 1.3×107036	?	?	?
4 символа	≥ 2050	> 3.7×106518	?	?	?	?
5 символов	> 1.7×10352	?	?	?	?	?
6-значное	> 1.9×104933	?	?	?	?	?

Приложения

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

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

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

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

• Чрезвычайно сложно доказать значения для функции занятого бобра (и функции максимального сдвига). Это было доказано только для чрезвычайно маленьких машин с менее чем пятью состояниями, в то время как для создания полезной машины предположительно потребуется не менее 20-50 состояний. Кроме того, каждое известное точное значение S(п) было доказано перечислением каждого п-состояние машины Тьюринга и доказательство того, останавливается ли каждая из них. Придется вычислить S(п) каким-либо менее прямым способом, чтобы он действительно был полезным.
• Но даже если бы кто-то нашел лучший способ вычислить S(п), значения функции занятого бобра (и функции максимального сдвига) становятся очень большими, очень быстро. S(6) > 10³⁶⁵³⁴ уже требует специального ускорения на основе шаблонов, чтобы можно было смоделировать до завершения. Точно так же мы знаем, что S(10)> Σ (10)> 3 ↑↑↑ 3 - гигантское число и S(17)> Σ (17)> G, где G - число Грэма - огромное число. Таким образом, даже если бы мы знали, скажем, S(30), совершенно неразумно запускать какой-либо компьютер с таким количеством шагов. В известной части Вселенной недостаточно вычислительных мощностей, чтобы выполнить даже S(6) операции напрямую.^[12]

Известные примеры

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

Примеры

Забег занятого бобра с 4 состояниями и 2 символами. Синий: лента ("0" печатается как "_"), красный: состояние (отображается непосредственно перед текущим положением головы).

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

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

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

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

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

	А
0	1RЧАС
1	(не используется)

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

2 состояния, 2 символа занятого бобра

	А	B
0	1RB	1лА
1	1лB	1RЧАС

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

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

	А	B	C
0	1RB	0RC	1лC
1	1RЧАС	1RB	1лА

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

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

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

	А	B	C	D
0	1RB	1лА	1RЧАС	1RD
1	1лB	0LC	1лD	0RА

Результат: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 шагов, всего тринадцать дюймов, см. Изображение)

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

	А	B	C	D	E
0	1RB	1RC	1RD	1лА	1RЧАС
1	1лC	1RB	0LE	1лD	0LА

Результат: 4098 "1" с 8191 "0" с вкраплениями 47 176 870 шагов.

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

	А	B	C	D	E	F
0	1RB	1RC	1лD	1RE	1лА	1лЧАС
1	1лE	1RF	0RB	0LC	0RD	1RC

Результат: ≈3.515 × 10¹⁸²⁶⁷ «1» с в ≈7,412 × 10³⁶⁵³⁴ шаги.

Смотрите также

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

Заметки

использованная литература

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

• Страница Хайнер Марксен, который вместе с Юргеном Бантроком нашел вышеупомянутые записи для машины Тьюринга с 5 и 6 состояниями.
• Паскаля Мишеля Исторический обзор результатов занятого бобра, который также содержит лучшие результаты и некоторый анализ.
• Определение класса RTM - Обратные машины Тьюринга, простой и сильный подкласс ТМ.
• "Атака тысячелетия "в Rensselaer RAIR Lab по проблеме занятого бобра. Эта попытка позволила установить несколько новых рекордов и установить несколько значений для четверной формализации.
• Дэниел Бриггс ' интернет сайт архив и Форум для решения проблемы занятого бобра с 5 состояниями и 2 символами на основе Скелет (Георгий Георгиев) Список нестандартных машин.
• Ааронсон, Скотт (1999), Кто может назвать самое большое число?
• Вайсштейн, Эрик В. «Занятый бобер». MathWorld.
• Занятый Бобер Гектор Зенил, Вольфрам Демонстрационный проект.
• Машины Тьюринга занятого бобра - компьютерфил
• Паскаль Мишель. Конкурс занятых бобров: исторический обзор. 70 страниц. 2017.