Проблема зависания

В теории вычислимости проблема зависания — это проблема разрешимости, которая может неформально быть поставлена в виде:

Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда либо. Альтернативой этому является то, что он работает всё время без остановки (зависает).

Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы зависания для любых возможных входных данных не может существовать. Мы можем сказать, что проблема зависания неразрешима на машине Тьюринга.

См. также

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

Ссылки

  • en:Alan Turing, 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) неразрешима.
 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home