Изменения

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

Для начала покажем, что функция <tex>BB(n)</tex> не убывает. <br>В данной задаче также существует функция <tex>\Sigma(n)</tex>, которая в зависимости от числа состояний <tex>n</tex> возвращает максимальное число единиц на ленте, которое может появиться в результате работы программы. То, что эта функция монотонно возрастает, очевидно. <br>Теперь покажем, что <tex>\forall n \ BB(n) > \Sigma(n).</tex> Для того, чтобы поместить одну единицу на ленту, требуется совершить хотя бы 1 шаг. Из этого следует, что <tex>BB(n)</tex> растет быстрее, чем <tex>\Sigma(n)</tex>. Сделовательно, <tex>BB(n)</tex> монотонно возрастает.  <br>Для доказательства непосредственно утверждения докажем, что для любой вычислимой функции <tex>f(n)</tex> функция <tex>BB(n)</tex> будет превышать ее значение (за исключением конечного множества значений числа <tex>n</tex>). <br> Пусть <tex>f(n)</tex> представлена своим кодом.Для каждого <tex>n</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)) > m = f(n) </tex>. Данный переход корректен, так как мы доказали, что <tex>BB(n)</tex> {{---}} монотонно возрастающая функция. Так как <tex>n_0</tex> конечно, то мы всегда можем найти такие значения <tex>n</tex>, при которых будет выполняться полученное неравенство. Отсюда следует, что утверждение доказано.