Как утверждать, что если мы сможем решить проблему остановки, то мы сможем и решить занятого бобра?

Question

Это одна из задач моего поручения.У меня есть симуляция машины Тьюринга, которая может имитировать занятая функция бобра.Я провел небольшое исследование, чтобы доказать эту проблему, но до сих пор не понял ее, поэтому думаю, возможно, вы сможете мне помочь.Хороший источник, к которому я мог бы обратиться, или пример того, как это аргументировать, было бы хорошо.

Answer 1

Функция BB определяется как максимальное количество шагов, которые машина Тьюринга определенного размера может выполнить и при этом остановиться.(Другой способ выразить это так: все машины Тьюринга размера x либо остановятся менее чем за BB(x) шагов, либо будут работать вечно).

Предположим, что у вас есть машина Тьюринга сложности x, тогда вы можете определить, остановится она или нет, позволив ей работать в течение временных шагов BB(x) - если она не остановилась к тому времени, то по определению она никогда не остановится.

Точно так же, если бы вы могли решить проблему остановки, вы могли бы оценить все возможные машины Тьюринга размера x, исключить те, которые не останавливаются, и принять BB(x) за максимальное время выполнения остатков.

Конечно, BB(x) невычислима – и на самом деле растет быстрее, чем любая вычислимая функция, которую вы могли бы назвать – следовательно, ее невозможно даже аппроксимировать.

Answer 2

Вы можете найти доказательство, которое ищете здесь, ниже доказательство того, что проблема Занятого Бобера невычислима.