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

Функция занятого бобра(она же функция BB или сигма-функция Радо, обозначаемая

\Sigma(n)

или

\text{BB}(n)

) — отличительная быстрорастущая функция из теории вычислимости. Это наиболее известная из невычислимых функций. Она определяется как максимальное количество единиц, которые могут быть записаны (на готовую ленту) с n состояниями, двухцветной остановкой Машины Тьюринга, начиная с пустой ленты перед остановкой.^[1]^[2] Эти машины Тьюринга называются занятыми бобрами.

Радо показал, что эта функция в конечном итоге доминирует над всеми вычислимыми функциями, и, таким образом, она неразложима. То есть ни один алгоритм, который завершается после конечного числа шагов, не может вычислить $\Sigma(n)$ для произвольного $n$ . Однако это вычислимо машиной Тьюринга oracle с помощью oracle для задачи остановки.

Это одна из самых быстрорастущих функций, когда-либо возникавших в профессиональной математике. В гугологии только несколько значимых функций превосходят его — например, функция Кси, функция занятого бобра на машине Тьюринга с бесконечным временем и функция Райо.

Как правило, $\Sigma(n,m)$ указывает максимальное количество непустых символов, которые могут быть записаны (на готовую ленту) с n состояниями, m цветами останавливающейся машины Тьюринга, начиная с пустой ленты перед остановкой.

$\Sigma(n)$ также может быть определено как наибольшее число в наборе $T = \{n_1,n_2, \cdots,n_k\}$ , который содержит выходные данные всех машин Тьюринга с $n$ состояниями и 2 цветами. Размер $T$ не больше, чем $(4n +4)^{2n}$ (общее число машин Тьюринга с $n$ состояниями), что показывает, насколько малая часть чисел $\Sigma(n)$ может быть определена.

Busy Beaver Turing Machines - Computerphile

Несколько разных машин Тьюринга заданного размера могут быть занятыми бобрами. Например, следующие машины с тремя состояниями и двумя символами выдают максимум шесть единиц:^[3]

	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

	A	B	C
0	1RB	1LC	1RA
1	1RC	1RH	0LB

Неофициальное объяснение[]

Гостиница "Робот вечности"[]

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

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

"Напуганное" состояние:
1. Если в комнате темно, включите свет и перейдите в комнату слева.
2. Если в комнате светло, ничего не делайте и перейдите в "нормальное" состояние.
"Нормальное" состояние:
1. Если в комнате светло, выключите свет и перейдите в комнату справа.
2. В противном случае перейдите в состояние "напуган".

Одним из особых состояний является состояние "стоп". Когда робот оказывается в этом состоянии, процесс завершается.

Предположим, у робота есть n состояний (не включая состояние "стоп"), и он останавливается. Каково максимальное количество светлых комнат на данный момент?

Эта система является прямой аллегорией машин Тьюринга. Отель - магнитная лента, робот - машина Тьюринга, а тёмные и светлые комнаты - ячейки 0 и 1.

Пример[]

Предположим, что n = 3. Оказывается, что следующий набор правил выигрывает:

"Нормальное" состояние (начальное состояние):
1. Если в комнате темно, включите свет и переместитесь вправо. Затем перейдите в состояние "осторожно".
2. Если в комнате светло, переместитесь влево и перейдите в состояние "легкомысленный".
Сосотояние "осторожно":
1. Если в комнате темно, включите свет и переместитесь влево. Затем перейдите в состояние "нормальное".
2. Если в комнате светло, двигайтесь вправо. (Оставайтесь в состоянии "осторожно".)
Состояние "легкомысленное":
1. Если в комнате темно, включите свет и переместитесь влево. Затем перейдите в состояние "осторожно".
2. Если в комнате светло, остановитесь.

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

При соблюдении правильных правил машин Тьюринга (М-нТ) могут выполнять любую вычислимую операцию, несмотря на их кажущуюся простоту. Если компьютер может вычислить это за конечное время и пространство (даже теоретически), то МТ также может сделать это за конечное (хотя, вероятно, и более длительное) время и пространство. С точки зрения вычислимости процессоры М-нТ и Intel - это одно и то же, хотя первый намного проще. Этот важный факт известен как тезис Чёрча — Тьюринга. (Некоторые эквивалентные простые устройства включают в себя теговые системы, некоторые клеточные автоматы, SKI combinator calculus и Brainfuck язык программирования.)

Легко смоделировать МТ, но гораздо сложнее предсказать поведение МТ. Это связано с тем, что некоторые М-ныТ никогда не останавливаются, и единственный способ проверить это - А) бесконечно моделировать их или Б) найти и доказать закономерность. Вариант А физически невозможен, а вариант Б сложен — как компьютер распознает произвольные шаблоны? — а также проблематично, потому что многие М-ныТ демонстрируют хаотичное поведение и не имеют простых паттернов.

Основная проблема здесь заключается в том, что компьютеры не более мощны, чем М-ныТ. Чтобы контролировать произвольные М-ныТ, нам нужно что-то более мощное, чем МТ. Но, согласно тезису Чёрча–Тьюринга, компьютеры, которыми мы располагаем сегодня, в вычислительном отношении эквивалентны М-намТ! Наблюдать за ними и, таким образом, вычислять $\Sigma(n)$ невозможно.

Гостиница "Божество вечности"[]

Множество всех наборов правил МТ счётно бесконечно - М-ныТ могут быть сопоставлены один к одному с натуральными числами. На самом деле, давайте обозначим их МТ #1, МТ # 2, МТ # 3, ... Точное отображение, которое мы используем, не имеет значения, до тех пор, пока какая-либо МТ может восстановить набор правил по заданному номеру машины.

Обратите внимание, что каждая из М-нТ в этой последовательности может иметь любое конечное число состояний. Есть $(4n +4)^{2n}$ машин Тьюринга для $n$ состояний, поэтому TM # 1-64 могут быть машинами с одним состоянием, М-ныТ #65-20801 - все машины с двумя состояниями, М-ныТ #20802-16798018 - все машины с тремя состояниями и т.д.

Мы дополняем "Робота из гостиницы Вечности", добавляя в него бога. Вводятся три новых специальных состояния: "спросить", "да" и "нет". Если робот переходит в состояние "спросить", он связывается с Триакулой, Богиней Больших чисел. Затем Триакула выполняет следующие действия:

Она подсчитывает все светлые комнаты и называет результат "x".
Она имитирует МТ #x (что невозможно ни для кого, кроме божества).
Если МТ #x останавливается, она переводит робота в состояние "да". В противном случае она переводит его в состояние "нет".

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

Эта новая расширенная ситуация является аллегорией для машин Тьюринга oracle. Для них существует несколько эквивалентных определений; некоторые используют дополнительную ленту для oracle, а некоторые используют другие состояния, отличные от "спросить", "да" и "нет".

Выше гостиницы "божества Вечности"[]

В истинном духе гугологии вы всегда можете пойти на шаг дальше. Мы можем ещё раз превзойти машины Тьюринга oracle, перечислив их МТ₂, МТ₂ #1, МТ₂ #2, МТ₂ #3, ..., где МТ₂ расшифровывается как "машина Тьюринга 2-го уровня" или машина Тьюринга oracle. Превзойдя "те", мы можем получить более высокие показатели машин Тьюринга: МТ₃, затем МТ₄, затем МТ₅, ...

Что мы делаем после прохождения всех этих уровней? Мы можем создать новую "машину Тьюринга уровня ω", или МТ_ω, которая имеет доступ ко всем этим уровням машин Тьюринга. Используйте эту таблицу:

МТ₁#1	МТ₁#2	МТ₁#3	МТ₁#4	МТ₁#5	⋯
МТ₂#1	МТ₂#2	МТ₂#3	МТ₂#4	МТ₂#5	⋯
МТ₃#1	МТ₃#2	МТ₃#3	МТ₃#4	МТ₃#5	⋯
МТ₄#1	МТ₄#2	МТ₄#3	МТ₄#4	МТ₄#5	⋯
МТ₅#1	МТ₅#2	МТ₅#3	МТ₅#4	МТ₅#5	⋯
⋮	⋮	⋮	⋮	⋮	⋱

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

МТ_ω#1	МТ_ω#2	МТ_ω#9	МТ_ω#10	МТ_ω#25	⋯
МТ_ω#4	МТ_ω#3	МТ_ω#8	МТ_ω#11	МТ_ω#24	⋯
МТ_ω#5	МТ_ω#6	МТ_ω#7	МТ_ω#12	МТ_ω#23	⋯
МТ_ω#16	МТ_ω#15	МТ_ω#14	МТ_ω#13	МТ_ω#22	⋯
МТ_ω#17	МТ_ω#18	МТ_ω#19	МТ_ω#20	МТ_ω#21	⋯
⋮	⋮	⋮	⋮	⋮	⋱

Теперь у нас есть определение МТ_ω #n, таким образом, мы успешно превзошли все машины Тьюринга порядка n.

Кстати, максимальный выходной сигнал МТ_a с n состояниями равен Σ_a(n).

За пределами[]

Добавив oracle для TM_ω, мы можем продолжить с тем, что можно было бы назвать "машиной Тьюринга уровня ω+1", или TM_ω+1, затем, добавив другой уровень oracle, мы можем получить TM_ω+2 и так далее. После того, как мы определим TM_ω+a для всех положительных целых чисел a, мы можем использовать трюк, аналогичный тому, который использовался в предыдущем разделе, чтобы построить "машину Тьюринга уровня ω+ω", которая была бы способна решить проблему остановки для всех TM_ω+a.

С помощью ординалов мы можем продолжить этот метод дальше, и мы могли бы определить TM_α для любого счётного ординального числа α. Однако из-за возрастающей сложности кодировок оракулов высокого порядка работать с этим становится очень непрактично, вот почему математики рассматривают различные способы расширения понятия вычислимости. Одним из них, заслуживающим упоминания, является машина Тьюринга с бесконечным временем, разработанная Джей. Д. Хэмкинсом и А. Льюисом.

Изменения ленты[]

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

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

Tree cut by beaver — Выходная запись одного или нескольких занятых бобров в Мендзыхуде, Польша.

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

Другая функция, имеющая сопоставимую скорость роста, — $\S(n)$ , максимальное конечное число шагов, которое может выполнить двухцветная машина Тьюринга с n-состояниями. Некоторые авторы называют эту функцию функцией занятого бобра.^[4]^[5] Для всех $n$ , $S(n) \geq \Sigma(n)$ потому что машина, которая печатает $\Sigma(n)$ единиц, должна претерпеть как минимум столько же переходов состояний.

Аналогично, $S(n,m)$ — максимальное конечное число шагов, которое может выполнить машина Тьюринга с n-состояниями и m-цветами.

Машина, производящая $\Sigma(n)$ , не обязательно является той же самой машиной, которая производит $S(n)$ . Например, следующий занятой бобёр с 3 состояниями и 2 символами выдаёт максимум шесть единиц, но выполняет только 14 шагов:^[6]

	A	B	C
0	1RB	0RC	1LC
1	1RH	1RB	1LA

Для сравнения, следующий занятой бобёр делает максимум 21 шаг, но выдаёт только пять единиц:^[7]

	A	B	C
0	1RB	1LB	1LC
1	1RH	0RC	1LA

$S(745)$ — наименьшее известное значение функции максимального сдвига, которое неразрешимо в ТМЦФ, если оно непротиворечиво.^[8] Первая такая построенная МТ включала 7918 состояний.^[9] Таким образом, $S(745)$ — наименьшее известное неразрешимое число в ТМЦФ, порождённое функцией максимального сдвига в том смысле, что равенство $\underbrace{1+ \cdots +1}_m = S(745)$ недоказуемо в ТМЦФ для любого мета-теоретического натурального числа $m$ до тех пор, пока оно непротиворечиво. Это небольшое улучшение по сравнению с ранее известным порогом $S(748)$ .^[10]^[11]

Тривиальные расширения[]

Можно естественным образом определить функцию $f$ так, что $f(n) = \Sigma^n (n)$ , а затем даже построить вокруг неё рекурсивную иерархию. Однако, чтобы выйти за рамки $\Sigma(n)$ , нам нужна более сложная парадигма.

Функции занятого бобра более высокого порядка[]

Машина Тьюринга (или что-то менее мощное) не может вычислить $\Sigma(n)$ для произвольного $n$ . Однако мы можем создать машину Тьюринга второго порядка или машина Тьюринга с оракулом, которая имеет доступ к чёрному ящику ("оракулу"), который может определить когда обычная машина Тьюринга останавливается. Максимальное количество единиц, которое можно записать с помощью двухцветной машины Тьюринга с оракулом с n-состояниями, обозначается $\Sigma_2(n)$ — функция занятого бобра второго порядка. В отличие от простых вариантов, описанных выше, эта новая функция имеет значительное преимущество перед исходной функцией.

Хотя машина Тьюринга второго порядка может решить проблему остановки для машин Тьюринга первого порядка, она не может предсказать, когда остановится она сама. Таким образом, $\Sigma_2(n)$ невычислимо даже относительно машины Тьюринга с оракулом.

В общем, если определить понятие машины Тьюринга $x$ -го порядка подходящим способом для рекурсивного ординала $x$ , $\Sigma_x(n)$ можно вычислить с использованием машины Тьюринга $(x+1)$ -ого порядка, но не для машин более низкого порядка.

К сожалению, не существует единого стандартного определения для этих машин Тьюринга с оракулом, поэтому сигма-функции высшего порядка не имеют стандартного определения. По крайней мере, при любой разумной формулировке понятия машины Тьюринга высшего порядка правильные порядки ординального типа $\omega_1 ^{\textrm{CK}}$ невычислимы даже относительно $x$ -овой машина Тьюринга с оракулом для любого рекурсивного ординала $x$ . В частности, быстрорастущая иерархия, индексируемая $\mathcal{O}$ Клини относительно системы фундаментальных последовательностей, невычислима даже относительно такой машины Тьюринга более высокого порядка. Поэтому совершенно не очевидно, превосходят ли функции занятого бобра более высокого порядка быстрорастущую иерархию, индексируемую $\mathcal{O}$ Клини, хотя гугологи склонны полагать, что функция занятого бобра первого порядка сравнима с ней и, следовательно, функция занятого бобра второго порядка значительно превосходит её без рассуждений.

Псевдокод[]

Это "алгоритм времени выхода" для нахождения нижних границ — если машина Тьюринга не останавливается после t шагов, предполагается, что она работает бесконечно. Установка бесконечности даёт верное значение BB(n), но это, очевидно, невозможно сделать на компьютере.

function BB(n, t):
    max := 0
    for each rule set r:
        simulate a Turing machine with ruleset r for t steps
        if the machine halts:
            if number of 1's printed > max:
                max := number of 1's printed
    return max

Этот метод использовался для вычисления $\Sigma(3)$ и $\Sigma(4)$ , а также границ для $\Sigma(5)$ и $\Sigma(6)$ .

Метод нахождения границ "снизу вверх" путём построения машин Тьюринга с большими выходными данными представляет собой сложную проблему. Пока что это удалось сделать только людям, а компьютерные доказательства, ограничивающие $\Sigma(n)$ для больших $n$ , ещё предстоит изучить. Примером такой программы является программа BBprover компании Skelet.^[12]

Монотонность[]

$\Sigma(n) = m$ очевидно монотонна. По крайней мере, если у нас есть машина Тьюринга с $n$ -состояниями, которая останавливается на символе 0, то для машины Тьюринга с $n+1$ -состояниями мы можем заменить правило остановки правилом, которое переходит в состояние $n+1$ . В состоянии $n+1$ мы переходим в состояние остановки и записываем 1, записывая $m+1$ единиц и доказываем, что $\Sigma(n+1) \geq m+1$ . Если у нас есть машина Тьюринга с $n$ -состояниями, которая останавливается на символе 1, мы делаем то же самое, за исключением того, что в $n+1$ -м состоянии головка переходит в левый или правый угол единицы, записывает 1 и останавливается.

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

Примечания[]

↑ Радо, Т. "О невычислимых функциях". Bell System Technical J. 41, 877-884, май 1962.
↑ Занятый бобёр -- из Wolfram MathWorld
↑ https://webusers.imj-prg.fr/~pascal.michel/ha.html
↑ Aaronson, Scott. Who Can Name the Bigger Number?. Получено 2013-03-09.
↑ Goucher, Adam. Busy beavers. Получено 2013-03-09.
↑ https://webusers.imj-prg.fr/~pascal.michel/ha.html
↑ https://webusers.imj-prg.fr/~pascal.michel/ha.html
↑ https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf
↑ Адам Йедидиа, Скотт Ааронсон. Относительно небольшая машина Тьюринга, поведение которой не зависит от теории множеств (PDF)
↑ Скотт Ааронсон, Граница занятого бобра (с. 12)
↑ Машина Тьюринга с 748 состояниями на GitHub Стефана О'Рира
↑ Доказательство занятого бобра

[1] Радо, Т. "О невычислимых функциях". Bell System Technical J. 41, 877-884, май 1962.

[2] Занятый бобёр -- из Wolfram MathWorld

[3] ttps://webusers.imj-prg.fr/~pascal.michel/ha.html

[4] Aaronson, Scott. Who Can Name the Bigger Number?. Получено 2013-03-09.

[5] Goucher, Adam. Busy beavers. Получено 2013-03-09.

[6] ttps://webusers.imj-prg.fr/~pascal.michel/ha.html

[7] ttps://webusers.imj-prg.fr/~pascal.michel/ha.html

[8] ttps://www.ingo-blechschmidt.eu/assets/bachelor-thesis-undecidability-bb748.pdf

[9] Адам Йедидиа, Скотт Ааронсон. Относительно небольшая машина Тьюринга, поведение которой не зависит от теории множеств (PDF)

[10] Скотт Ааронсон, Граница занятого бобра (с. 12)

[11] Машина Тьюринга с 748 состояниями на GitHub Стефана О'Рира

[12] Доказательство занятого бобра

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]