Изменения

}}

----

|statement= Функция <tex>BB(n)</tex> не убывает.

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

Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(|p|) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.

}}

== См. также ==