Busy beaver

Материал из Викиконспекты
Перейти к: навигация, поиск
Эта статья находится в разработке!
Определение:
[math]BB(n)[/math] — функция от натурального аргумента [math]n[/math] (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной [math]n[/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]n[/math] определим программы вида:

 [math]P_n[/math]():
   k = {десятичная запись числа n}
   f = f(k)
   for i = 1 to f + 1
     do smth

Каждая такая программа делает как минимум [math]f(n) + 1[/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]BB(n)[/math], будет выполнено: [math] n \gt len(P_n) \Rightarrow BB(n) \geqslant BB(len(P_n)) \gt f = f(n) [/math]. Так как [math]n_0[/math] конечно, то утверждение доказано.
[math]\triangleleft[/math]
  • Из этого утверждения следует, что [math]BB(n)[/math] невычислима.