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

Я просматриваю доказательство проблемы остановки в Введение в теорию вычислений Сипсера и моих Основное беспокойство вызывает приведенное ниже доказательство:

Если TM M не знает, когда он зацикливается (он не может принять или отклонить, поэтому TM является распознаваемым по Тьюрингу для всех строк), то как может решающий H решить если M может быть в цикле? Та же проблема возникнет, когда TM D выполнит свою обработку.

the halting problem is undecideable

18
задан Cœur 9 November 2018 в 14:58
поделиться