Проблема остановки: различия между версиями
[непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
Syarik (обсуждение | вклад) Сделал более развернутое введение |
Нет описания правки |
||
Строка 6:
[[Тьюринг, Алан|Алан Тьюринг]] доказал в [[1936 год]]у, что не проблема остановки ''[[неразрешимость|неразрешима]]'' на [[машина Тьюринга|машине Тьюринга]]. Другими словами, не существует общего алгоритма решения этой проблемы.
Проблема остановки занимает центральное место в [[теория вычислимости|теории вычислимости]], поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путем. Для многих других задач можно доказать их алгоритмическую неразрешимость, попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: пусть есть некая задача, для которой требуется установить ее неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует такого алгоритма. А значит, предположение было неверным и исходная
== Набросок доказательства ==
|