Проблема остановки: различия между версиями
| [непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
финитных -> конечных |
|||
Строка 3:
: ''Даны описание процедуры и её начальные входные данные, требуется определить, завершится ли когда-либо выполнение процедуры с этими данными. Альтернативой этому является то, что она работает всё время без остановки.''
[[Тьюринг, Алан|Алан Тьюринг]] доказал в [[1936 год]]у, что проблема остановки ''[[неразрешимость|неразрешима]]'' на [[машина Тьюринга|машине Тьюринга]]. Другими словами, не существует общего алгоритма решения этой проблемы.<ref>{{
Проблема остановки занимает центральное место в [[теория вычислимости|теории вычислимости]], поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём. Для многих других задач можно доказать их алгоритмическую неразрешимость, попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует такого алгоритма. А значит, предположение было неверным и исходная задача также неразрешима.
| |||