в чем именно причина остановки

Проблема остановки заключается в том, что при наличии входных данных и программы не существует алгоритма, который мог бы решить, будет ли программа остановлена. Это делает эту проблему неразрешимой. Мое неправильное понимание проблемы остановки состоит в том, что мы не можем просто создать другую программу, которая могла бы проверять, есть ли в программе бесконечные циклы. Я просто имею в виду, что можно проверить случаи, когда цикл не останавливается, и на основе этого решить, остановится программа или нет. Не могли бы вы сообщить мне, что не так в моем понимании этой проблемы?


algorithm theory computation-theory halting-problem
person Monalizza    schedule 13.11.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Ну, знаете, доказательство проблемы остановки довольно тривиально. Предположим, у вас есть программа, которая сообщает вам, остановится данная программа или нет (для простоты забудьте о вводе). Назовем эту программу doesHalt (программа). Давайте теперь напишем новую программу под названием

myHalt() 
  if doesHalt(myHalt):
     infinite loop
  else 
     return

Каким должно быть возвращаемое значение

doesHalt(myHalt)

Чтобы ответить на ваш конкретный вопрос: как ваша программа, исследующая циклы, узнает, остановлен ли данный цикл или нет? Петля

for (i = 1; i += 10; ) {
   if (i == 7) break;
}

цикл навсегда или нет? Как ваша программа это выяснила?

person MK.    schedule 13.11.2015
comment
Отлично, вы имеете в виду, что сама программа, которая проверяет программу myHalt, не может останавливаться! Понятно, не думаю, что моя программа когда-либо сможет оценить 7-е i. Большое спасибо - person Monalizza; 13.11.2015
comment
нет, в этом доказательстве мы берем предполагаемую рабочую программу DoesHalt () и показываем, что мы можем использовать ее для построения новой программы, которая вызовет логический парадокс / противоречие и, таким образом, докажет наше предположение о том, что doesHalt существует неверно. - person MK.; 13.11.2015