Википедия

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

Интерактивная навигация по истории
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
викификация, уточнение
Нет описания правки
Строка 1:
{{нет сносок|В данной статье}}
В [[теория алгоритмов|теории алгоритмов]] '''проблемаПроблема остановки''' (или '''проблема останова''') — это проблемаодна из центральных проблем в [[теория алгоритмов|теории алгоритмов]]<ref>''Н.К.Верещагин, А.Шень'' [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции]</ref>, которая может неформально быть поставлена в виде:
 
: ''Даны описание процедуры и ее начальные входные данные, требуется определить, завершится ли когда-либо выполнение процедуры с этими данными. Альтернативой этому является то, что она работает всё время без остановки.''
 
[[Тьюринг, Алан|Алан Тьюринг]] доказал в [[1936 год]]у, что проблема остановки ''[[неразрешимость|неразрешима]]'' на [[машина Тьюринга|машине Тьюринга]]. Другими словами, не существует общего алгоритма решения этой проблемы.<ref>{{статья |автор=[[Тьюринг, Алан|Алан Тьюринг]] |заглавие=On computable numbers, with an application to the Entscheidungsproblem |издание=Proceedings of the London Mathematical Society, Series 2 |том=42 |год=1936 |страницы=230–265 |ссылка=http://www.turingarchive.org/browse.php/B/12}} (в этой публикации Тьюринг вводит определение [[Машина Тьюринга|машины Тьюринга]], формулирует проблему зависания и показывает, что она, также как и [[проблема разрешения]], неразрешима).</ref>
 
Проблема остановки занимает центральное место в [[теория вычислимости|теории вычислимости]], поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путем. Для многих других задач можно доказать их алгоритмическую неразрешимость, попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: пусть есть некая задача, для которой требуется установить ее неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует такого алгоритма. А значит, предположение было неверным и исходная задача также неразрешима.
Строка 24:
 
== Ссылки ==
* {{статья |автор=[[Тьюринг, Алан|Алан Тьюринг]] |заглавие=On computable numbers, with an application to the Entscheidungsproblem |издание=Proceedings of the London Mathematical Society, Series 2 |том=42 |год=1936 |страницы=230–265 |ссылка=http://www.turingarchive.org/browse.php/B/12}} (в этой публикации Тьюринг вводит определение [[Машина Тьюринга|машины Тьюринга]], формулирует проблему зависания и показывает, что она, также как и [[проблема разрешения]], неразрешима).
* [[c2:HaltingProblem]]
* [http://www.cprogramming.com/tutorial/computersciencetheory/halting.html Проблема зависания]{{ref-en}}
Источник — https://ru.wikipedia.org/wiki/Проблема_остановки