Изменения

Перейти к: навигация, поиск

Busy beaver

120 байт убрано, 18:19, 16 января 2016
Нет описания правки
|proof=
Рассмотрим программу длины <tex>n</tex>, совершающую максимальное число шагов. Существует программа длины <tex>n + 1</tex>, которая делает столько же шагов: надо просто в предыдущую добавить один незначащий символ. Например, пробельный. Значит, существует программа длины на один больше, которая делает не меньше шагов. Следовательно, <tex>BB</tex> не убывает. Значит, переход является корректным и наше утверждение доказано.
}}
----
25
правок

Навигация