WikiDer > Занятый бобер
Эта статья поднимает множество проблем. Пожалуйста помоги Улучши это или обсудите эти вопросы на страница обсуждения. (Узнайте, как и когда удалить эти сообщения-шаблоны) (Узнайте, как и когда удалить этот шаблон сообщения)
|
В теоретическая информатика, то занятая игра бобра стремится найти прекращение программа заданного размера, обеспечивающего максимально возможную производительность.[1]
Точнее, занятая игра бобра состоит из разработки останавливающегося двоичного алфавита Машина Тьюринга который записывает на ленту наибольшее количество единиц, используя только заданный набор состояний. Правила игры с двумя состояниями следующие:
- машина должна иметь два состояния в дополнение к состоянию остановки, и
- лента изначально содержит только нули.
Игрок должен придумать таблицу переходов, нацеленную на самый длинный вывод единиц на ленте, при этом убедившись, что машина в конечном итоге остановится.
An пй занятый бобер, BB-п или просто «занятой бобер» - это машина Тьюринга, которая выигрывает п-state Busy Beaver Game. То есть он достигает наибольшего числа единиц среди всех других возможных п-государственные машины Тьюринга. В BB-2 машина Тьюринга, например, получает четыре единицы за шесть шагов.
Определить, является ли произвольная машина Тьюринга занятым бобром. неразрешимый. Это имеет значение в теория вычислимости, то проблема остановки, и теория сложности. Концепция была впервые представлена Тибор Радо в его статье 1962 года «О невычислимых функциях».
Игра
В п-государственная занятая бобровая игра (или BB-п игра), введенный в Тибор Радов статье 1962 г. Машины Тьюринга, каждый элемент которого должен соответствовать следующим техническим требованиям:
- В машине есть п "рабочие" состояния плюс состояние остановки, где п положительное целое число, и одно из п состояния выделяется как начальное состояние. (Обычно состояния помечены цифрами 1, 2, ..., п, с состоянием 1 в качестве начального состояния, или А, B, C, ..., с состоянием А в качестве начального состояния.)
- Машина использует одинарную двустороннюю бесконечную (или неограниченную) ленту.
- Алфавит ленты - {0, 1}, где 0 является пустым символом.
- Машины функция перехода принимает два входа:
- текущее состояние без остановки,
- символ в текущей ячейке ленты,
- и производит три выхода:
- символ для записи поверх символа в текущей ячейке ленты (это может быть тот же символ, что и перезаписанный символ),
- направление движения (влево или вправо; то есть сдвиг к ячейке ленты на одно место влево или вправо от текущей ячейки), и
- состояние, в которое нужно перейти (которое может быть состоянием остановки).
- Таким образом, (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:
и асимптотически улучшенная оценка (из [Ben-Amram, Petersen, 2002]): существует постоянная c, так что для всех п ≥ 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×1018267 1 с (ровно (25 * 430341+23) / 9), используя более 7.412×1036534 шаги (найден Павлом Кропицем в 2010 году). Как отмечалось выше, это двухсимвольные машины Тьюринга.
Простое расширение 6-конечного автомата приводит к 7-конечному автомату, который будет записывать более 1010101018705353 1 с на ленту, но, несомненно, есть гораздо более загруженные машины с 7 состояниями. Однако у других занятых охотников на бобров есть другие наборы машин.
Милтон Грин в своей статье 1964 года «Нижняя граница сигма-функции Радо для двоичных машин Тьюринга» построил набор машин Тьюринга, демонстрирующих, что
где ↑ Обозначение Кнута со стрелкой вверх и А является Функция Аккермана.
Таким образом
(с 333 = 7625597484987 члены в экспоненциальной башне), и
где число г1 - огромное начальное значение в последовательности, определяющей Число Грэма.
В 1964 году Милтон Грин разработал нижнюю границу для функции занятого бобра, которая была опубликована в трудах симпозиума IEEE 1964 года по теории коммутационных схем и логическому проектированию. Хайнер Марксен и Юрген Бантрок описали это как «нетривиальную (не примитивно рекурсивную) нижнюю границу». Эту нижнюю границу можно вычислить, но она слишком сложна, чтобы ее можно было сформулировать как единое выражение через n. При n = 8 метод дает Σ (8) ≥ 3 × (7 × 392 - 1) / 2 ≈ 8.248×1044.
Из текущих нижних оценок можно вывести, что:
Напротив, лучшая текущая (по состоянию на 2018 год) нижняя граница Σ (6) равна 1018267, что больше нижней границы, полученной по формуле Грина, 33 = 27 (что очень мало для сравнения). На самом деле это намного больше нижней границы: 3 ↑↑ 3 = 333 = 7625597484987, которая является первой нижней оценкой Грина для Σ (8), а также намного превосходит вторую нижнюю оценку: 3 * (7 * 392-1)/2.
Σ (7) таким же образом намного, намного больше, чем текущая общая нижняя граница 331 (почти 618 триллионов), поэтому вторая нижняя граница также очень и очень слабая.
Доказательство невычислимости S(п) и Σ (п)
Предположим, что S(п) - вычислимая функция и пусть ОЦЕНКИ обозначают TM, оценивая S(п). Учитывая ленту с п 1с он произведет S(п) 1 с на ленте, а затем остановитесь. Позволять Чистый обозначают машину Тьюринга, очищающую последовательность единиц, первоначально записанную на ленте. Позволять Двойной обозначают оценивающую функцию машины Тьюринга п + п. Учитывая ленту с п 1с он произведет 2п 1 с на ленте, а затем остановитесь. Создадим композицию Двойной | ОЦЕНКИ | Чистый и разреши п0 быть количеством состояний этой машины. Позволять Create_n0 обозначают машину Тьюринга, создающую п0 1 с на изначально пустой ленте. Эту машину можно тривиально сконструировать так, чтобы п0 государства (состояние я пишет 1, перемещает голову вправо и переключается в состояние я + 1, кроме состояния п0, который останавливается). Позволять N обозначим сумму п0 + п0.
Позволять BadS обозначают композицию Create_n0 | Двойной | ОЦЕНКИ | Чистый. Обратите внимание, что на этой машине N состояния. Начиная с изначально пустой ленты, он сначала создает последовательность п0 1s, а затем удваивает ее, создавая последовательность N 1с. потом BadS будет производить S(N) Единицы на ленте, и, наконец, он очистит все единицы, а затем остановится. Но фаза очистки будет продолжаться как минимум S(N) шагов, поэтому время работы BadS строго больше, чем S(N), что противоречит определению функции S(п).
Невычислимость Σ (п) доказывается аналогично. В приведенном выше доказательстве необходимо заменить машину ОЦЕНКИ с участием EvalΣ и Чистый с участием Приращение - простой TM, ищущий на ленте первый 0 и заменяющий его на 1.
Невычислимость S(п) также можно установить, сославшись на проблему остановки пустой ленты. Проблема остановки пустой ленты - это проблема принятия решения для любой машины Тьюринга, остановится она или нет при запуске с пустой ленты. Проблема остановки пустой ленты эквивалентна стандартной проблема остановки и поэтому он также невычислим. Если S(п) была вычислимой, то мы могли бы решить проблему остановки пустой ленты, просто запустив любую заданную машину Тьюринга с п государства для S(п) шаги; если он еще не остановился, он никогда не остановится. Итак, поскольку проблема остановки пустой ленты не вычислима, отсюда следует, что S(п) также должны быть невычислимыми.
Обобщения
Для любого модель вычисления существуют простые аналоги занятого бобра. Например, обобщение на машины Тьюринга с п государства и м символы определяют следующие обобщенные функции занятого бобра:
- Σ (п, м): наибольшее количество ненулевых знаков, которые можно распечатать п-штат, м-символ машина запустилась на первоначально пустой ленте перед остановкой, и
- S(п, м): наибольшее количество шагов, сделанных п-штат, м-символ машина запустилась на изначально пустой ленте перед остановкой.
Например, найденная до сих пор самая продолжительная трехсимвольная машина с 3 состояниями работает 119112334170342540 шаги перед остановкой. Самая продолжительная машина с 6 состояниями и 2 символами, которая имеет дополнительное свойство переворачивать значение ленты на каждом этапе, производит 6147 1 с после 47339970 шаги. Так SRTM(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) > 1036534 уже требует специального ускорения на основе шаблонов, чтобы можно было смоделировать до завершения. Точно так же мы знаем, что S(10)> Σ (10)> 3 ↑↑↑ 3 - гигантское число и S(17)> Σ (17)> G, где G - число Грэма - огромное число. Таким образом, даже если бы мы знали, скажем, S(30), совершенно неразумно запускать какой-либо компьютер с таким количеством шагов. В известной части Вселенной недостаточно вычислительных мощностей, чтобы выполнить даже S(6) операции напрямую.[12]
Известные примеры
Была построена бинарная машина Тьюринга с 1919 состояниями, которая останавливает если только ZFC непоследовательно.[5] Была построена машина Тьюринга с 744 состояниями, которая останавливается, если Гипотеза Римана ложно.[5] Была построена машина Тьюринга с 43 состояниями, которая останавливается, если и только если Гипотеза Гольдбаха неверно, и машина с 27 состояниями для этой гипотезы была предложена, но еще не проверена.[5]
Примеры
Это таблицы правил для машин Тьюринга, которые генерируют Σ (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 × 1018267 «1» с в ≈7,412 × 1036534 шаги.
Смотрите также
Заметки
- ^ Поскольку бесконечно зацикленный Программа, производящая бесконечный вывод, легко придумана, такие программы исключены из игры.
- ^ Адам Едидиа и Скотт Ааронсон (май 2016 г.). Относительно небольшая машина Тьюринга, поведение которой не зависит от теории множеств (технический отчет). Массачусетский технологический институт. arXiv:1605.04343. Bibcode:2016arXiv160504343Y.
- ^ Арон, Джейкоб. «Эта машина Тьюринга должна работать вечно, если математика не ошибается». Получено 2016-09-25.
- ^ а б Версия от 3 мая содержала 7918 состояний: «8000-е число занятого бобра ускользает от теории множеств ZF». Блог Shtetl-Optimized. 2016-05-03. Получено 2016-09-25.
- ^ а б c d «Три объявления». Блог Shtetl-Optimized. 2016-05-03. Получено 2018-04-27.
- ^ "GitHub - sorear / metamath-turing-machines: счетчики для проверки Metamath и другие вещи". 2019-02-13.
- ^ "Оживленный бобровый рубеж" (PDF).
- ^ Нерегулярные станки Busy Beaver для класса ТМ (5)
- ^ Тьюринг: проект по завершению "Занятого бобра из пяти"
- ^ Проблема занятого бобра: НОВАЯ АТАКА ТЫСЯЧЕЛЕТИЯ
- ^ Чайтин 1987 г.
- ^ Ллойд 2001. Вычислительная мощность Вселенной.
использованная литература
- Радо, Тибор (Май 1962 г.). «О невычислимых функциях» (PDF). Технический журнал Bell System. 41 (3): 877–884. Дои:10.1002 / j.1538-7305.1962.tb00480.x.
- Именно здесь Радо впервые определил проблему занятого бобра и доказал, что она невычислима и растет быстрее, чем любая вычислимая функция.
- Линь, Шэнь; Радо, Тибор (Апрель 1965 г.). "Компьютерные исследования проблем машины Тьюринга". Журнал ACM. 12 (2): 196–212. Дои:10.1145/321264.321270.
- Результаты этой статьи уже частично были опубликованы в докторской диссертации Линь 1963 года под руководством Радо. Лин и Радо доказывают, что Σ (3) = 6 и S(3) = 21, доказав, что все машины Тьюринга с 3 состояниями и 2 символами, которые не останавливаются в пределах 21 шага, никогда не остановятся. (Большинство из них автоматически проверяется компьютерной программой, однако 40 проверяются человеком.)
- Брэди, Аллен Х. (апрель 1983 г.). «Определение значения невычислимой функции Радо Σ (k) для машин Тьюринга с четырьмя состояниями ». Математика вычислений. 40 (162): 647–665. Дои:10.1090 / S0025-5718-1983-0689479-6. JSTOR 2007539.
- Брэди доказывает, что Σ (4) = 13 и S(4) = 107. Брэди определяет две новые категории для неизменяющихся машин Тьюринга с 3 состояниями и 2 символами: рождественские елки и счетчики. Он использует компьютерную программу, чтобы доказать, что все машины, кроме 27, которые выполняют 107 шагов, являются вариантами рождественских елок и счетчиков, которые могут работать бесконечно. Последние 27 машин (так называемые «упорные») лично Брэди лично осмотрели их, чтобы не останавливаться.
- Махлин, Рона; Стаут, Квентин Ф. (июнь 1990 г.). «Сложное поведение простых машин». Physica D: нелинейные явления. 42 (1–3): 85–98. Bibcode:1990 ФИД ... 42 ... 85M. Дои:10.1016 / 0167-2789 (90) 90068-Z. HDL:2027.42/28528.
- Махлин и Стаут описывают проблему занятого бобра и многие техники, используемые для поиска занятого бобра (которые они применяют к машинам Тьюринга с 4-мя состояниями и 2-значными символами, тем самым подтверждая доказательство Брэди). Они предлагают, как оценить вариант вероятности остановки (Ω) Чайтина.
- Марксен, Хайнер; Buntrock, Юрген (февраль 1990 г.). «Нападение на занятого бобра 5». Бюллетень EATCS. 40: 247–251. В архиве из оригинала от 09.10.2006. Получено 2020-01-19.
- Марксен и Бантрок демонстрируют, что Σ (5) ≥ 4098 и S(5) ≥ 47176870 и подробно опишите метод, который они использовали, чтобы найти эти машины, и докажите, что многие другие никогда не остановятся.
- Грин, Милтон В. (1964). Нижняя граница сигма-функции Rado для двоичных машин Тьюринга. 1964 Труды пятого ежегодного симпозиума по теории коммутационных цепей и логическому проектированию. С. 91–94. Дои:10.1109 / SWCT.1964.3.
- Грин рекурсивно конструирует машины для любого количества состояний и предоставляет рекурсивную функцию, которая вычисляет их оценку (вычисляет σ), тем самым обеспечивая нижнюю границу для Σ. Рост этой функции сопоставим с ростом Функция Аккермана.
- Дьюдни, Александр К. (1984). «Компьютерная ловушка для занятого бобра, самая трудолюбивая машина Тьюринга». Scientific American. 251 (2): 10–17.
- Программы занятых бобра описываются Александр Дьюдни в Scientific American, Август 1984 г., стр. 19–23, также март 1985 г., стр. 23 и Апрель 1985 г. с. 30.
- Чайтин, Грегори Дж. (1987). «Вычисление функции занятого бобра» (PDF). In Cover, T. M .; Гопинатх, Б. (ред.). Открытые проблемы в коммуникации и вычислениях. Springer. С. 108–112. ISBN 978-0-387-96621-2.
- Брэди, Аллен Х. (1995). «Оживленная игра бобра и смысл жизни». В Херкене, Рольф (ред.). Универсальная машина Тьюринга: обзор за полвека (2-е изд.). Вена, Нью-Йорк: Springer-Verlag. С. 237–254. ISBN 978-3-211-82637-9.
- При этом Брэди (известный в четырех штатах) описывает некоторую историю зверя и называет его погоню «Занятой бобровой игрой». Он описывает другие игры (например, клеточные автоматы и Игра жизни Конвея). Особый интерес представляет «Игра занятого бобра в двух измерениях» (стр. 247). С 19 ссылками.
- Бут, Тейлор Л. (1967). Последовательные машины и теория автоматов. Нью-Йорк: Вили. ISBN 978-0-471-08848-6.
- См. Главу 9, Машины Тьюринга. Сложная книга, рассчитанная на инженеров-электриков и технических специалистов. Обсуждает рекурсию, частичную рекурсию со ссылкой на машины Тьюринга, проблему остановки. Ссылка в Booth приписывает Rado занятого бобра. Бут также определяет проблему занятого бобра Rado в «домашних задачах» 3, 4, 5, 6 главы 9, с. 396. Задача 3 состоит в том, чтобы «показать, что проблема занятого бобра неразрешима ... для всех значений n».
- Бен-Амрам, А. М .; Julstrom, B.A .; Цвик, У. (1996). «Заметка о занятых бобрах и других существах». Математическая теория систем. 29 (4): 375–386. CiteSeerX 10.1.1.75.1297. Дои:10.1007 / BF01192693.
- Границы между функциями Σ и S.
- Бен-Амрам, А. М .; Петерсен, Х. (2002). «Улучшенные границы для функций, связанных с занятыми бобрами». Теория вычислительных систем. 35: 1–11. CiteSeerX 10.1.1.136.5997. Дои:10.1007 / s00224-001-1052-0.
- Улучшенные границы.
- Lafitte, G .; Папазян, К. (июнь 2007 г.). «Ткань малых машин Тьюринга». Вычисления и логика в реальном мире, Труды Третьей конференции по вычислимости в Европе. С. 219–227. CiteSeerX 10.1.1.104.3021.
- Эта статья содержит полную классификацию машин Тьюринга с 2 состояниями и 3 символами и, таким образом, доказательство для (2, 3) занятого бобра: Σ (2, 3) = 9 и S (2, 3) = 38.
- Boolos, George S .; Берджесс, Джон П .; Джеффри, Ричард С. (2007). Вычислимость и логика (Пятое изд.). Издательство Кембриджского университета. ISBN 978-0-521-87752-7.
- Кропиц, Павел (2010). Проблем Занят Бобер (Бакалаврская диссертация) (на словацком языке). Карлов университет в Праге.
- Это описание идей, алгоритмов и их реализации, с описанием экспериментов, исследующих машины Тьюринга с 5 и 6 состояниями путем параллельного запуска на 31 4-ядерном компьютере и, наконец, лучшие результаты для TM с 6 состояниями.
внешние ссылки
Викиверситет проводит викторину о занятом бобрах |
- Страница Хайнер Марксен, который вместе с Юргеном Бантроком нашел вышеупомянутые записи для машины Тьюринга с 5 и 6 состояниями.
- Паскаля Мишеля Исторический обзор результатов занятого бобра, который также содержит лучшие результаты и некоторый анализ.
- Определение класса RTM - Обратные машины Тьюринга, простой и сильный подкласс ТМ.
- "Атака тысячелетия"в Rensselaer RAIR Lab по проблеме занятого бобра. Эта попытка позволила установить несколько новых рекордов и установить несколько значений для четверной формализации.
- Дэниел Бриггс ' интернет сайт архив и Форум для решения проблемы занятого бобра с 5 состояниями и 2 символами на основе Скелет (Георгий Георгиев) Список нестандартных машин.
- Ааронсон, Скотт (1999), Кто может назвать самое большое число?
- Вайсштейн, Эрик В. «Занятый бобер». MathWorld.
- Занятый Бобер Гектор Зенил, Вольфрам Демонстрационный проект.
- Машины Тьюринга занятого бобра - компьютерфил
- Паскаль Мишель. Конкурс занятых бобров: исторический обзор. 70 страниц. 2017.