Изменения

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