Проблема остановки
Материал из Википедии — свободной энциклопедии
В теории вычислимости проблема остановки — это проблема разрешимости, которая может неформально быть поставлена в виде:
- Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.
Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы зависания для любых возможных входных данных не может существовать. Мы можем сказать, что проблема зависания неразрешима на машине Тьюринга.
[править] См. также
- Граф выполнения может быть использован для быстрой категоризации, когда программа не имеет циклов (и поэтому останавливается), имеет тривиальные циклы (и поэтому останавливается), имеет нетривиальные циклы (неразрешимо) или входит в бесконечный цикл.
[править] Ссылки
- Алан Тьюринг, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230—265. online version Это эпохальная публикация где Тьюринг вводит определение машины Тьюринга, формулирует проблему зависания и показывает, что она (также как и en:Entscheidungsproblem) неразрешима.
- Wiki:HaltingProblem
Это незавершённая статья по математике. Вы можете помочь проекту, исправив и дополнив её. |