Cтраница 1
Проблема усердного бобра ( ее формулировка и доказательство неразрешимости даны Радо Тибором в Bell System Tecnical Journal, May 1962, с. Тьюринга, вычисляющей функцию р, - причем машины, использующей в качестве символов только В к I. Доказательство неразрешимости этой проблемы опирается на свойства функции р, сформулированные в упр. [1]
Доказательство проводится от противного; мы выведем противоречие ( а именно, что 0 1) из предположения о разрешимости проблемы усердного бобра. Будучи запущенной в состоянии 1 на самой левой клетке сплошного блока из п единиц на ленте с пустыми символами во всех остальных клетках, она в конце концов останавливается в состоянии2 k на самой левой клетке сплошного блока из р ( п) единиц на ленте с пустыми символами во всех остальных клетках. [2]
Оказывается, одну из них вы уже видели: это функция р, определенная в упр. Доказательство ее невычислимости основывается на том факте, что проблема усердного бобра неразрешима. [3]