355
правок
Изменения
Нет описания правки
{{в разработке}}
{{Определение
|definition =
<b><tex>BB(n)</tex></b> {{---}} функция от натурального аргумента <tex>n</tex> (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной <tex>n</tex> символов и затем остановиться.
}}
{{Утверждение
|statement=
<tex>BB(n)</tex> растет быстрее любой всюду определенной неубывающей вычислимой функции <tex>f(n) : N \rightarrow N </tex>, то есть для всех <tex>n</tex> кроме конечного числа выполнено <tex>BB(n) > f(n)</tex>
|proof=
Пусть <tex>f(n)</tex> представлена своим кодом.
Для каждого <tex>n</tex> определим программы вида:
<tex>P_n</tex>():
k = {десятичная запись числа n}
f = f(k)
for i = 1 to f + 1
do smth
Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.
Длина <tex>P_n</tex> будет равна <tex> \lg n + const </tex>, где <tex>const</tex> {{---}} длина кода без десятичной записи <tex>n</tex>. Пусть <tex>n_0</tex> {{---}} решение уравнения <tex>\lg n + const = n</tex>. Тогда для всех натуральных <tex> n > \left \lceil n_0 \right \rceil </tex>, в силу неубывания <tex>BB(n)</tex>, будет выполнено: <tex> n > len(P_n) \Rightarrow BB(n) \geqslant BB(len(P_n)) > f = f(n) </tex>. Так как <tex>n_0</tex> конечно, то утверждение доказано.
}}
* Из этого утверждения следует, что <tex>BB(n)</tex> невычислима.
