Выдержка из книги
Булос Д.N.
Вычислимость и логика
Доказательство проводится от противного; мы выведем противоречие ( а именно, что 0 1) из предположения о разрешимости проблемы усердного бобра. Будучи запущенной в состоянии 1 на самой левой клетке сплошного блока из п единиц на ленте с пустыми символами во всех остальных клетках, она в конце концов останавливается в состоянии2 k на самой левой клетке сплошного блока из р ( п) единиц на ленте с пустыми символами во всех остальных клетках.
