25
правок
Изменения
Нет описания правки
Пусть <tex>f(n)</tex> представлена своим кодом.
Для каждого <tex>n</tex> определим программы вида:
<tex>p_n()</tex>:
k = десятичная запись числа n
m = f = BB(k) '''for ''' i = 1 '''to f ''' m + 1 do /* шаг программы */
Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.
Длина <tex>P_np_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_np_n) \Rightarrow BB(n) \geqslant BB(len(P_np_n)) > f m = f(n) </tex>. Так как <tex>n_0</tex> конечно, то утверждение доказано.
}}
