Википедия

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

Интерактивная навигация по истории
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м →‎Ссылки: convert interwiki wiki: -> c2:, replaced: Wiki: → c2: с помощью AWB
Сделал более развернутое введение
Строка 1:
{{нет сносок|В данной статье}}
В [[теория вычислимостиалгоритмов|теории вычислимостиалгоритмов]] '''проблема остановки''' (или '''проблема останова''') — это [[проблема разрешимости]], которая может неформально быть поставлена в виде:
 
: ''Даны описание [[алгоритм]]а и его начальные входные данные, требуется определить, сможетзавершится ли когда-либо выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки.''
 
[[Тьюринг, Алан|Алан Тьюринг]] доказал в [[1936 год]]у, что не существует общего алгоритма для решения проблемы остановки. Другими словами, проблема остановки ''[[неразрешимость|неразрешима]]'' на [[машина Тьюринга|машине Тьюринга]]. Другими словами, не существует общего алгоритма решения этой проблемы.
 
Проблема остановки занимает центральное место в [[теория вычислимости|теории вычислимости]], поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путем. Для многих других задач можно доказать их алгоритмическую неразрешимость, попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: пусть есть некая задача, для которой требуется установить ее неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует такого алгоритма. А значит, предположение было неверным и исходная задаче также неразрешима.
 
== Набросок доказательства ==
Источник — https://ru.wikipedia.org/wiki/Проблема_остановки