Проблема остановки: различия между версиями

В [[теория алгоритмов|теории алгоритмов]] '''проблема остановки''' (или '''проблема останова''')  — это проблема, которая может неформально быть поставлена в виде:

Докажем это от противного. Допустим, Анализатор существует.

Напишем алгоритм Диагонализатор, который принимает на вход число <math>N</math>, передает пару аргументов <math>(N, N)</math> Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером <math>N</math>, получив на вход число <math>N</math>. Пусть <math>K</math> - — это порядковый номер Диагонализатора в множестве <math>S</math>. Запустим Диагонализатор, передав ему это число <math>K</math>. Диагонализатор остановится в том и только том случае, если алгоритм с номером <math>K</math> (то есть, он сам) не останавливается, получив на вход число <math>K</math> (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.

* [[Граф выполненияпотока управления]] может быть использован для быстрой категоризации, когда программа не имеет циклов (и поэтому останавливается), имеет тривиальные циклы (и поэтому останавливается), имеет нетривиальные циклы (неразрешимо) или входит в бесконечный цикл.

* {{статья |автор=[[Тьюринг, Алан|Алан Тьюринг]] |заглавие=On computable numbers, with an application to the Entscheidungsproblem |издание=Proceedings of the London Mathematical Society, Series 2 |том=42 |год=1936 |страницы=230–265 |ссылка=http://www.turingarchive.org/browse.php/B/12}} (в этой публикации Тьюринг вводит определение [[Машина Тьюринга|машины Тьюринга]], формулирует проблему зависания и показывает, что она, (также как и [[проблема разрешения]]), неразрешима).