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

Question

Я перехожу к доказательству проблемы останова в Введение в теорию вычислений от Sipser, и моя главная проблема связана с приведенным ниже доказательством:

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

Answer 1

Прочитав это и попытавшись визуализировать доказательство, я придумал этот код, который является упрощенной версией кода в этом ответе на связанный вопрос:

function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}

Если halts(deceiver) возвращает true, deceiver будет работать вечно, а если возвращается false, deceiver остановится, что противоречит определению halts. Следовательно, функция halts невозможна.

Answer 2

Это «доказательство от противоречия», reductio ad absurdum .(Латинские фразы всегда хороши в теоретических классах ... конечно, если они имеют смысл.)

Эта программа H - это просто программа с двумя входами: строка, представляющаяпрограмма для какой-то машины и вход.В целях доказательства вы просто предполагаете, , что программа H верна: она просто остановит и примет, если М примет w .Вам не нужно думать о как это сделает это;на самом деле, мы собираемся доказать, что это невозможно, что такая программа H не может существовать, ...

ПОТОМУ ЧТО

если бы существовала такая программа, мы могли бы немедленно создать другую программу H ', которую H не смог бы решить.Но, по предположению, такой программы не существует: H может решить все.Итак, мы вынуждены сделать вывод, что никакая программа, определенная так, как мы определили H , невозможна.

Кстати, метод доказательства reductio является более спорным, чемВы можете ожидать, учитывая, как часто его используют, особенно в области компьютерных наук.Вы не должны смущаться, чтобы найти это немного странным.Волшебный термин «неконструктивный», и если вы чувствуете себя действительно амбициозным, спросите одного из своих профессоров о критике неконструктивной математики Эрретом Бишопом.