Busy beaver

Поиск усердных бобров (англ. busy beaver) — известная задача в теории вычислимости. Под усердным бобром в теории вычислимости понимают машину Тьюринга с заданным числом состояний конечного автомата, которая будучи запущенной на пустой ленте, записывает на нее максимальное количество ненулевых символов и останавливается.

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

Определение:

[math]BB(n)[/math] — функция от натурального аргумента [math]n[/math], равная максимальному числу шагов, которое может совершить программа длиной [math]n[/math] символов и затем остановиться.

---

Утверждение:

Функция [math]BB(n)[/math] не убывает.

[math]\triangleright[/math]

Рассмотрим программу длины [math]n[/math], совершающую максимальное число шагов. Существует программа длины [math]n + 1[/math], которая делает столько же шагов: получается добавлением в предыдущую одного незначащего символа, например, пробельного. Значит, существует программа длины на один больше, которая делает не меньше шагов. Следовательно, [math]BB[/math] не убывает.

[math]\triangleleft[/math]

---

Утверждение:

[math]BB(n)[/math] растет быстрее любой всюду определенной неубывающей вычислимой функции [math]f(n) : N \rightarrow N [/math], то есть для всех [math]n[/math] кроме конечного числа выполнено [math]BB(n) \gt f(n).[/math]

[math]\triangleright[/math]

Докажем, что для любой вычислимой функции [math]f(n)[/math] функция [math]BB(n)[/math] будет превышать ее значение (за исключением конечного множества значений числа [math]n[/math]). Пусть [math]f(n)[/math] представлена своим кодом. Для каждого [math]n[/math] определим программы вида: [math]p_n()[/math]: k = десятичная запись числа n m = f(k) for i = 1 to m + 1 шаг программы Каждая такая программа делает как минимум [math]f(n) + 1[/math] шагов. Так как мы рассматриваем [math]n[/math] в десятичной записи, то длина [math]p_n[/math] будет равна [math] \lg n + const [/math], где [math]const[/math] — длина кода без десятичной записи [math]n[/math]. Пусть [math]n_0[/math] — решение уравнения [math]\lg n + const = n[/math]. Тогда для всех натуральных [math] n \gt \left \lceil n_0 \right \rceil [/math] будет выполнено неравенство: [math] n \gt len(p_n) \Rightarrow BB(n) \geqslant BB(len(p_n)) \gt m = f(n) [/math]. Данный переход корректен, так как мы доказали, что [math]BB(n)[/math] — монотонно возрастающая функция. Так как [math]n_0[/math] конечно, то мы всегда можем найти такие значения [math]n[/math], при которых будет выполняться полученное неравенство. Отсюда следует, что утверждение доказано.

[math]\triangleleft[/math]

Вывод: доказав предыдущее утверждение, мы проверили, что максимальное число шагов, которое может совершить программа и при этом остановиться, на самом деле растет с большей скоростью, чем любая вычислимая функция. Отсюда следует, что [math]BB(n)[/math] невычислима.

---

Утверждение:

Функция Busy beaver невычислима.

[math]\triangleright[/math]

По теореме о рекурсии, программа может знать свой исходный код. Значит, в неё можно написать функцию [math] \mathrm{getSrc()} [/math], которая вернёт строку — исходный код программы. Предположим, что функция Busy beaver вычислима. Тогда напишем такую программу [math]p(){:}[/math] for i = 1..BB([math]|\mathrm{getSrc()}|[/math]) + 1 do smth Такая программа всегда совершает больше шагов, чем функция [math] BB [/math] от этой программы. А это невозможно, так [math] BB(|p|) [/math] равна максимальному числу шагов как раз этой программы. Получили противоречие.

[math]\triangleleft[/math]

См. также

• Вычислимые функции
• Машина Тьюринга

Источники информации

• Хопкрофт Д., Мотвани Р., Ульман Д. — Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
• Английская Википедия — Busy beaver
• Федотов П.В., Царев Ф.Н., Шалыто А.А. — Задача поиска усердных бобров и ее решения