Неформально, в теоретической информатике, игра о занятом бобре направлена на поиск завершающей программы заданного размера, которая дает максимально возможный результат.
Точнее, игра «занятый бобер» состоит из разработки останавливающейся, двоично-алфавитной машины Тьюринга, которая записывает наибольшее количество единиц на ленту, используя только заданный набор состояния. Правила для игры с двумя состояниями следующие:
Игрок должен задумать таблица переходов, нацеленная на максимально длительный вывод на ленту единиц, при этом убедитесь, что машина в конечном итоге остановится.
n-й занятый бобер, BB-n или просто «занятый бобер» - это машина Тьюринга, которая побеждает в n-state Busy Beaver Game. То есть он достигает наибольшего числа единиц среди всех других возможных конкурирующих машин Тьюринга с n-состояниями. Например, машина Тьюринга BB-2 выдает четыре единицы за шесть шагов.
Определение того, является ли произвольная машина Тьюринга занятым бобром, неразрешимо. Это имеет значение в теории вычислимости, проблеме остановки и теории сложности. Эта концепция была впервые представлена Тибором Радо в его статье 1962 года «О невычислимых функциях».
n-состояние игра «занятый бобер» (или игра BB-n ), представленная в статье Тибора Радо 1962 года, включает в себя класс машин Тьюринга, каждый член из которых требуется для соответствия следующим техническим требованиям:
«Запуск» машины состоит из запуска в начальном состоянии, при этом текущая ячейка ленты представляет собой любую ячейку пустой (полностью 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".)
В дополнение к функции Σ Радо [1962] ввел еще одно экстремальная функция для BB-класса машин Тьюринга, функция максимального сдвига, S, определяемая следующим образом:
Потому что эти От машин Тьюринга требуется сдвиг в каждом переходе или «шаге» (включая любой переход в состояние остановки), функция максимальных сдвигов одновременно является функцией максимальных шагов.
Радо показал, что 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:
и асимптотически улучшенная оценка (из [Ben-Amram, Petersen, 2002]): там существует константа c такая, что для всех n ≥ 2
Там есть тенденция быть около квадрата , и на самом деле многие машины дают меньше, чем .
По состоянию на 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 года «Нижняя граница сигма-функции Радо для двоичных машин Тьюринга» построил набор машин Тьюринга, демонстрирующих, что
где ↑ - Стрелка вверх по Кнута, а A - функция Аккермана.
Таким образом,
(с 3 = 7625597484987 членами в экспоненциальной башне) и
где число g 1 - огромное начальное значение в последовательности, определяющей Число Грэма.
В 1964 году Милтон Грин разработал нижнюю границу для функции занятого бобра, которая была опубликована в трудах симпозиума IEEE 1964 года по теории коммутационных схем и логическому проектированию. Хайнер Марксен и Юрген Бантрок описали это как «нетривиальную (не примитивно рекурсивную) нижнюю границу». Эту нижнюю границу можно вычислить, но она слишком сложна, чтобы ее можно было сформулировать как единое выражение через n. При n = 8 метод дает Σ (8) ≥ 3 × (7 × 3 - 1) / 2 ≈ 8,248 × 10.
Из текущих нижних оценок можно вывести, что:
Напротив, лучший ток (по состоянию на 2018 год) нижняя граница на Σ (6) равно 10, что больше, чем нижняя граница, заданная формулой Грина, 3 = 27 (что очень мало для сравнения). Фактически, это намного больше, чем нижняя граница: 3 ↑↑ 3 = 3 = 7625597484987, что является оценкой Грина. первая нижняя оценка для Σ (8), а также намного больше, чем вторая нижняя граница: 3 * (7 * 3-1) / 2.
Σ (7) таким же образом намного, намного больше чем текущая общая нижняя граница 3 (почти 618 триллионов), поэтому вторая нижняя граница также очень и очень слабая.
Предположим, что 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 символами определяет следующие обобщенные функции занятого бобра :
Например, найденная до сих пор самая продолжительная машина с 3 состояниями и 3 символами выполняет 119112334170342540 шагов перед остановкой. Самая продолжительная машина с 6 состояниями и 2 символами, которая имеет дополнительное свойство реверсирования значения ленты на каждом шаге, выдает 6147 единиц после 47339970 шагов. Таким образом, S RTM (6) ≥ 47339970 и Σ RTM (6) ≥ 6147.
Можно дополнительно обобщить функцию занятого бобра, расширив ее до более чем одно измерение.
Аналогичным образом мы могли бы определить аналог функции Σ для регистровых машин как наибольшее число, которое может присутствовать в любом регистре при остановке для заданного количества инструкций.
В следующей таблице перечислены точные значения и некоторые известные нижние границы для S (n, m) и Σ (n, m) для обобщенных задач занятого бобра. Примечание: записи перечислены как «???» ограничены снизу максимумом всех записей слева и сверху. Эти машины либо не исследовались, либо были впоследствии заменены более мелкими машинами.
Машины Тьюринга, которые достигают этих значений, доступны на веб-странице Паскаля Мишеля. Каждый из этих веб-сайтов также содержит анализ машин Тьюринга и ссылки на доказательства точных значений.
Значения S (n, m) | ||||||
nm | 2 состояния | 3 состояния | 4 состояния | 5 состояний | 6 состояний | 7 состояний |
---|---|---|---|---|---|---|
2 символа | 6 | 21 | 107 | 47176870? | >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) | ||||||
nm | 2-состояние | 3-состояние | 4-состояние | 5-состояние | 6 состояний | 7 состояний |
2 символа | 4 | 6 | 13 | 4098? | >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) могут использоваться для систематического решения многих открытых проблем математики (теоретически). Однако текущие результаты по проблеме занятого бобра показывают, что это нецелесообразно по двум причинам:
Была сконструирована двоичная машина Тьюринга с 1919 состояниями, которая останавливается iff ZFC несовместим. Была построена машина Тьюринга с 744 состояниями, которая останавливается, если гипотеза Римана ложна. Была построена машина Тьюринга с 43 состояниями, которая останавливается, если гипотеза Гольдбаха ложна, и машина с 27 состояниями для этой гипотезы была предложена, но еще не проверена.
Это таблицы правил для машин Тьюринга, которые генерируют Σ (1) и S (1), Σ (2) и S (2), Σ (3) (но не S (3)), Σ (4) и S (4), а также наиболее известная нижняя оценка для Σ (5) и S (5), и Σ (6) и S (6).
В таблицах столбцы представляют текущее состояние, а строки представляют текущий символ, считанный с ленты. Каждая запись в таблице представляет собой строку из трех символов, указывающую символ для записи на ленту, направление движения и новое состояние (в указанном порядке). Состояние остановки показано как H.
. Каждая машина начинает в состоянии A с бесконечной ленты, содержащей все нули. Таким образом, начальным символом, считываемым с ленты, является 0.
Клавиша результата: (начинается с выделенной позиции, останавливается в подчеркнутой позиции)
A | |
---|---|
0 | 1RH |
1 | (не используется) |
Результат: 0 0 1 0 0 (1 шаг, всего одна "1")
A | B | |
---|---|---|
0 | 1RB | 1LA |
1 | 1LB | 1RH |
Результат: 0 0 1 1 1 1 0 0 (6 шагов, всего четыре "1" с)
A | B | C | |
---|---|---|---|
0 | 1RB | 0RC | 1LC |
1 | 1RH | 1RB | 1LA |
Результат: 0 0 1 1 1 1 1 1 0 0 (14 шагов, всего шесть единиц).
В отличие от предыдущих машин, эта машина является занятым бобром только для Σ, но не для S. (S (3) = 21.)
A | B | C | D | |
---|---|---|---|---|
0 | 1RB | 1LA | 1RH | 1RD |
1 | 1LB | 0LC | 1LD | 0RA |
Результат: 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 (107 шагов, всего тринадцать "1", см. Изображение)
A | B | C | D | E | |
---|---|---|---|---|---|
0 | 1RB | 1RC | 1RD | 1LA | 1RH |
1 | 1LC | 1RB | 0LE | 1LD | 0LA |
Результат: 4098 "1" с 8191 "0" с вкраплениями 47 176 870 шагов.
A | B | C | D | E | F | |
---|---|---|---|---|---|---|
0 | 1RB | 1RC | 1LD | 1RE | 1LA | 1LH |
1 | 1LE | 1RF | 0RB | 0LC | 0RD | 1RC |
Результат: ≈3,515 × 10 "1" с с шагом ≈7,412 × 10 шагов.
Викиверситет проводит викторину по занятой бобер |