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

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

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

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

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

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

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

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

Содержание

  • 1 Игра
  • 2 Связанные функции
    • 2.1 Функция занятого бобра Σ
      • 2.1.1 Невычислимость
      • 2.1.2 Сложность и недоказуемость Σ
    • 2.2 Максимум функция сдвига S
    • 2.3 Известные значения для Σ и S
    • 2.4 Доказательство невычислимости S (n) и Σ (n)
    • 2.5 Обобщения
    • 2.6 Точные значения и нижние границы
  • 3 Приложения
    • 3.1 Примечательные примеры
  • 4 Примеры
  • 5 См. Также
  • 6 Примечания
  • 7 Ссылки
  • 8 Внешние ссылки

Игра

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

  • Машина имеет n «рабочих» состояний плюс состояние остановки, где n - положительное целое число, и одно из n состояний выделяется как начальное. (Обычно состояния помечены цифрами 1, 2,..., n, с состоянием 1 как начальное состояние, или как A, B, C,..., с состоянием A как начальным состоянием.)
  • Машина использует одинарную двустороннюю бесконечную (или неограниченную) ленту.
  • Алфавит ленты - {0, 1}, где 0 является пустым символом.
  • Лента машины функция перехода принимает два входа:
  1. текущее состояние без остановки,
  2. символ в текущей ячейке ленты,
и производит три выхода:
  1. символ для записи поверх символ в текущей ячейке ленты (это может быть тот же символ, что и перезаписанный символ),
  2. направление перемещения (влево или вправо; то есть сдвиг к ячейке ленты на одно место влево или вправо от текущая ячейка) и
  3. состояние, в которое нужно перейти (которое может быть состоянием остановки).
Таким образом, существует (4n + 4) n-состояний машины Тьюринга, удовлетворяющие этому определению.
Более подробная версия той же формулы: (символы * направления * (состояния + 1)).
Функция перехода может быть рассматривается как конечная таблица из 5 кортежей, каждый из которых имеет форму
(текущее состояние, текущий символ, символ для записи, направление сдвига, следующее состояние).

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

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

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

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

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

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

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

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

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

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

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

Более того, это подразумевает, что неразрешимо с помощью общего алгоритма, является ли произвольная машина Тьюринга занятым бобром. (Такой алгоритм не может существовать, потому что его существование позволило бы вычислить Σ, что является доказанной невозможностью. В частности, такой алгоритм может быть использован для построения другого алгоритма, который будет вычислять Σ следующим образом: для любого заданного n каждый из конечное число двухсимвольных машин Тьюринга с 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 состояний.

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

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

Функция максимального сдвига S

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

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

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

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

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

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

S (n) ≥ Σ (n) S (n) ≤ (2 n - 1) Σ (3 n + 3) S (n) < Σ ( 3 n + 6) ; {\displaystyle {\begin{aligned}S(n)\geq \Sigma (n)\\S(n)\leq (2n-1)\Sigma (3n+3)\\S(n)<\Sigma (3n+6);\end{aligned}}}{\ displaystyle {\ begin {align} S (n) \ geq \ Sigma (n) \\ S ( n) \ leq (2n-1) \ Sigma (3n + 3) \\ S (n) <\ Sigma (3n + 6); \ end {align}}}

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

S (n) ≤ Σ (n + ⌈ 8 n log 2 ⁡ n ⌉ + c). {\ Displaystyle S (n) \ leq \ Sigma \ left (n + \ left \ lceil {\ frac {8n} {\ log _ {2} n}} \ right \ rceil + c \ right).}{\ displaystyle S (n) \ leq \ Sigma \ left (n + \ left \ lceil {\ frac {8n} {\ log _ {2} n}} \ right \ rceil + c \ right).}

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

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

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

Текущее (по состоянию на 2018 г. Чемпион занятых бобров с 5 состояниями производит 4098 единиц, используя 47176870 шагов (обнаружено Хайнером Марксеном и Юргеном Бантроком в 1989 году), но остается 18 или 19 (возможно, менее 10, см. Ниже) машин с нестандартным поведением, которые, как считается, никогда не останавливаться, но не было доказано, что они работают бесконечно. Скелет перечисляет 42 или 43 недоказанных машины, но 24 уже проверены. Остальные машины были смоделированы до 81,8 миллиарда шагов, но ни одна из них не остановилась. Дэниел Бриггс тоже испытал некоторые машины. Другой источник говорит, что 98 машин остаются непроверенными. Есть анализ несогласных. Таким образом, вероятно, что Σ (5) = 4098 и S (5) = 47176870, но это остается недоказанным, и неизвестно, остались ли еще несогласованные (по состоянию на 2018 год). На данный момент рекордсмен с шестью штатами производит более 3,515 × 10 единиц (точно (25 * 4 + 23) / 9), используя более 7,412 × 10 шагов (обнаружено Павлом Кропицем в 2010 году). Как отмечалось выше, это двухсимвольные машины Тьюринга.

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

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

Σ (2 k)>3 ↑ k - 2 3>A (k - 2, k - 2) для k ≥ 2, {\ displaystyle \ Sigma (2k)>3 \ uparrow ^ {k-2} 3>A (k-2, k-2) \ qquad {\ t_dv {for}} k \ geq 2,}{\displaystyle \Sigma (2k)>3 \ uparrow ^ {k-2} 3>A (k-2, k-2) \ qquad {\ t_dv {for}} k \ geq 2,}

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

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

Σ (10)>3 ↑↑↑ 3 = 3 ↑↑ 3 3 3 = 3 3 3. 3 {\ displaystyle \ Sigma (10)>3 \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow 3 ^ {3 ^ {3}} = 3 ^ {3 ^ {3 ^ {. ^ {. ^ {. ^ {3}}}}}}}\Sigma (10)>3 \ uparrow \ uparrow \ uparrow 3 = 3 \ uparrow \ uparrow 3 ^ {3 ^ {3}} = 3 ^ {3 ^ {3 ^ {. ^ {. ^ {. ^ {3}}}}}}

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

Σ (12)>3 ↑↑↑↑ 3 = g 1, {\ displaystyle \ Sigma (12)>3 \ uparrow \ uparrow \ uparrow \ uparrow 3 = g_ {1},}\Sigma (12)>3 \ uparrow \ uparrow \ uparrow \ uparrow 3 = g_ {1},

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

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

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

Σ (2 k + 1)>3 ↑ k - 2 31>A (k - 2, k - 2) для k ≥ 2, { \ Displaystyle \ Sigma (2k + 1)>3 \ uparrow ^ {k-2} 31>A (k-2, k-2) \ qquad {\ t_dv {for}} k \ geq 2,}{\displaystyle \Sigma (2k+1)>3 \ uparrow ^ {k-2} 31>A (k-2, k-2) \ qquad {\ t_dv {for}} k \ geq 2,}

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

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

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

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

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

Невычислимость Σ (n) может быть доказана аналогичным образом. В приведенном выше доказательстве нужно заменить машину EvalS на EvalΣ и Clean with 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-символами, запущенными на первоначально пустой ленте перед остановкой.

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

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

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

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

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

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

Значения S (n, m)
nm2 состояния3 состояния4 состояния5 состояний6 состояний7 состояний
2 символа62110747176870?>7,4 × 10>10
3-значное38≥ 119112334170342540>1,0 × 10???
4-значное≥ 3932964>5,2 × 10????
5-значное>1,9 × 10?????
6-значное>2,4 × 10?????
Значения Σ (n, m)
nm2-состояние3-состояние4-состояние5-состояние6 состояний7 состояний
2 символа46134098?>3,5 × 10>10
3-значное9≥ 374676383>1,3 × 10???
4-значное≥ 2050>3,7 × 10????
5-значное>1,7 × 10?????
6-значное>1,9 × 10?????

Приложения

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

1-состояние, 2-символьный занятый бобер
A
01RH
1(не используется)

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

2-х позиционный, 2-символьный активный бобер
AB
01RB1LA
11LB1RH

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

3-х фазный, 2-символьный активный бобер
ABC
01RB0RC1LC
11RH1RB1LA

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

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

4-х состояний, 2-х символьный занятый бобер
ABCD
01RB1LA1RH1RD
11LB0LC1LD0RA

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

текущий 5-позиционный, 2-символьный лучший претендент (возможно занятый бобер)
ABCDE
01RB1RC1RD1LA1RH
11LC1RB0LE1LD0LA

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

текущий лучший претендент на 6 состояний, 2 символа
ABCDEF
01RB1RC1LD1RE1LA1LH
11LE1RF0RB0LC0RD1RC

Результат: ≈3,515 × 10 "1" с с шагом ≈7,412 × 10 шагов.

См. Также

Примечания

  1. ^Поскольку программа с бесконечным циклом, производящая бесконечный вывод, легко придумать, такие программы исключен из игры.
  2. ^Адам Едидиа и Скотт Ааронсон (май 2016 г.). Относительно небольшая машина Тьюринга, поведение которой не зависит от теории множеств (технический отчет). Массачусетский технологический институт. arXiv : 1605.04343. Bibcode : 2016arXiv160504343Y.
  3. ^Арон, Джейкоб. «Эта машина Тьюринга должна работать вечно, если математика не ошибается». Проверено 25 сентября 2016 г.
  4. ^ Версия от 3 мая содержала 7918 состояний: «8000-й номер занятого бобра ускользает от теории множеств ZF». Штетл-оптимизированный блог. 2016-05-03. Проверено 25 сентября 2016 г.
  5. ^ «Три объявления». Штетл-оптимизированный блог. 2016-05-03. Проверено 27 апреля 2018 г.
  6. ^«GitHub - sorear / metamath-turing-machines: счетчики для проверки Metamath и другие вещи». 2019-02-13.
  7. ^«Граница занятых бобров» (PDF).
  8. ^Нестандартные машины занятых бобров для класса TM (5)
  9. ^Тьюринг: проект по завершению «занятых бобров» из 5
  10. ^Проблема занятого бобра: НОВАЯ АТАКА ТЫСЯЧЕЛЕТИЯ
  11. ^Чейтин 1987
  12. ^Ллойд 2001. Вычислительные возможности Вселенной.

Ссылки

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

Викиверситет проводит викторину по занятой бобер
Последняя правка сделана 2021-05-13 06:54:53
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте