Проблема остановки: различия между версиями
[непроверенная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
~~~~Энцо А Метки: с мобильного устройства из мобильной версии |
м откат правок 178.176.113.112 (обс.) к версии Vlsergey-at-work Метки: откат отмена |
||
Строка 6:
Проблема остановки занимает центральное место в [[теория вычислимости|теории вычислимости]], поскольку представляет собой первый пример задачи, которую невозможно решить алгоритмическим путём. Для многих других задач можно доказать их алгоритмическую неразрешимость, попытавшись свести задачу к проблеме остановки. Это делается по следующей схеме: пусть есть некая задача, для которой требуется установить её неразрешимость. Тогда предположим, что она разрешима, и попытаемся, используя этот факт, написать алгоритм решения проблемы остановки. Если это удастся, то мы придем к противоречию, ведь известно, что не существует такого алгоритма. А значит, предположение было неверным и исходная задача также неразрешима.
== Набросок доказательства ==
Рассмотрим множество <math>S</math> алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Выберем какой-нибудь полный по Тьюрингу язык программирования. Каждый алгоритм можно записать в виде конечной последовательности символов на этом языке. Упорядочим множество <math>S</math> (это возможно, поскольку оно является множеством конечных [[Последовательность|последовательностей]] элементов конечного множества и потому [[Счётное множество|счётно]]), при этом каждый алгоритм получит свой порядковый номер. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел <math>(N, X)</math>, и:
* останавливается и возвращает 1, если алгоритм с номером <math>N</math> не останавливается, получив на вход <math>X</math>
* не останавливается в противном случае (если алгоритм с номером <math>N</math> останавливается, получив на вход <math>X</math>).
Проблему остановки можно переформулировать следующим образом: существует ли Анализатор?
''Теорема.'' Анализатор не существует.
Докажем это от противного. Допустим, Анализатор существует.
Напишем алгоритм Диагонализатор, который принимает на вход число <math>N</math>, передает пару аргументов <math>(N, N)</math> Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только том случае, если не останавливается алгоритм с номером <math>N</math>, получив на вход число <math>N</math>. Пусть <math>K</math> — это порядковый номер Диагонализатора в множестве <math>S</math>. Запустим Диагонализатор, передав ему это число <math>K</math>. Диагонализатор остановится в том и только том случае, если алгоритм с номером <math>K</math> (то есть, он сам) не останавливается, получив на вход число <math>K</math> (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.
== См. также ==
|