Проблема с остановкой - Halting problem

В теория вычислимости, то проблема остановки проблема определения по описанию произвольного компьютерная программа и вход, будет ли программа завершена или продолжена работать вечно. Алан Тьюринг в 1936 г. доказал, что генерал алгоритм для решения проблемы остановки для всех возможных пар программа-ввод не может существовать.

Для любой программы ж это может определить, останавливаются ли программы, "патологическая" программа грамм, вызываемый с некоторым входом, может передавать свой собственный источник и свой вход в ж а затем конкретно делать противоположное тому, что ж предсказывает грамм Сделаю. Нет ж может существовать, который занимается этим делом. Ключевой частью доказательства является математическое определение компьютера и программы, известное как Машина Тьюринга; проблема остановки неразрешимый над машинами Тьюринга. Это один из первых случаев проблемы решения оказалось неразрешимым. Это доказательство важно для практических вычислений, поскольку определяет класс приложений, которые никакое изобретение в области программирования не может выполнять идеально.

Джек Коупленд (2004) приписывает введение термина проблема остановки к работе Мартин Дэвис в 1950-е гг.^[1]

Фон

Проблема остановки - это проблема решения о свойствах компьютерных программ на фиксированной Полный по Тьюрингу модель вычислений, то есть все программы, которые могут быть написаны в некоторой данной язык программирования это достаточно общее, чтобы быть эквивалентным машине Тьюринга. Проблема состоит в том, чтобы определить, учитывая программу и входные данные для программы, остановится ли программа в конечном итоге при запуске с этим входом. В этой абстрактной структуре нет ограничений по ресурсам на объем памяти или время, необходимое для выполнения программы; это может занять произвольно много времени и использовать произвольный объем памяти перед остановкой. Вопрос просто в том, остановится ли данная программа на определенном входе.

Например, в псевдокод, программа

пока (правда) продолжить

не останавливается; скорее, это продолжается вечно в бесконечный цикл. С другой стороны, программа

print "Привет, мир!"

действительно останавливается.

Хотя решить, останавливать ли эти программы просто, более сложные программы оказываются проблематичными. Один из подходов к решению проблемы может заключаться в том, чтобы запустить программу, сделав некоторое количество шагов, и проверить, не останавливается ли она. Но если программа не останавливается, неизвестно, остановится ли программа в конечном итоге или будет работать вечно. Тьюринг доказал, что не существует алгоритма, который всегда правильно решает, останавливается ли для данной произвольной программы и ввода программа при запуске с этим вводом. Суть доказательства Тьюринга состоит в том, что любой такой алгоритм может противоречить самому себе и, следовательно, не может быть правильным.

Последствия программирования

Немного бесконечные циклы может быть весьма полезным. Например, петли событий обычно кодируются как бесконечные циклы.^[2]Однако большинство подпрограмм предназначены для завершения (остановки).^[3]В частности, в жестких вычисления в реальном времени, программисты пытаются писать подпрограммы, которые не только гарантированно завершатся (остановятся), но также гарантированно завершатся до заданного крайнего срока.^[4]

Иногда эти программисты используют какой-либо универсальный (полный по Тьюрингу) язык программирования, но пытаются писать в ограниченном стиле, например MISRA C или же ИСКРА - что позволяет легко доказать, что результирующие подпрограммы завершаются раньше заданного срока.^{[нужна цитата ]}

В других случаях эти программисты применяют правило наименьшей мощности - они намеренно используют компьютерный язык, который не является полностью полным по Тьюрингу. Часто это языки, которые гарантируют завершение всех подпрограмм, например Coq.^{[нужна цитата ]}

Общие подводные камни

Сложность проблемы остановки заключается в том, что процедура принятия решения должна работать для всех программ и входов. Конкретная программа либо останавливается на заданном входе, либо не останавливается. Рассмотрим один алгоритм, который всегда отвечает «останавливается», а другой - «не останавливается». Для любой конкретной программы и ввода один из этих двух алгоритмов отвечает правильно, даже если никто не знает, какой именно. Однако ни один алгоритм не решает проблему остановки в целом.

Есть программы (переводчики ), которые имитируют выполнение предоставленного им исходного кода. Такие программы могут продемонстрировать, что программа действительно останавливается, если это так: сам интерпретатор в конечном итоге останавливает свое моделирование, что показывает, что исходная программа остановилась. Однако интерпретатор не остановится, если его входная программа не остановится, поэтому этот подход не может решить проблему остановки, как указано; он не отвечает успешно "не останавливается" для программ, которые не останавливаются.

Проблема остановки теоретически разрешима при линейно ограниченные автоматы (LBA) или детерминированные машины с конечной памятью. Машина с ограниченным объемом памяти имеет конечное количество конфигураций, и поэтому любая детерминированная программа на ней должна в конечном итоге либо останавливаться, либо повторять предыдущую конфигурацию:

...любой конечный автомат, если его полностью предоставить самому себе, в конечном итоге превратится в идеально периодическую повторяющуюся модель. Продолжительность этого повторяющегося паттерна не может превышать количество внутренних состояний машины ... (курсив в оригинале, Минский 1967, стр. 24)

Мински, однако, отмечает, что компьютер с миллионом мелких деталей, каждая из которых имеет два состояния, будет иметь как минимум 2^1,000,000 возможные состояния:

Это единица, за которой следует около трехсот тысяч нулей ... Даже если бы такая машина работала на частотах космических лучей, эоны галактической эволюции были бы ничем по сравнению со временем путешествия через такой цикл ( Минский 1967 с. 25):

Мински утверждает, что, хотя машина может быть конечной, конечные автоматы «имеют ряд теоретических ограничений»:

... вовлеченные величины должны наводить на мысль, что теоремы и аргументы, основанные главным образом на простой конечности [диаграммы] состояний, могут не иметь большого значения. (Минский с. 25)

Также можно автоматически решить, остановится ли недетерминированная машина с конечной памятью ни на одной, некоторых или всех возможных последовательностях недетерминированных решений, путем перечисления состояний после каждого возможного решения.

История

Проблема остановки исторически важна, потому что это была одна из первых проблем, которые нужно было доказать. неразрешимый. (Доказательство Тьюринга было опубликовано в мае 1936 г., тогда как Церковь Алонсо доказательство неразрешимости проблемы в лямбда-исчисление уже был опубликован в апреле 1936 г. [Church, 1936]). Впоследствии были описаны многие другие неразрешимые проблемы.

График

1900: Дэвид Гильберт задает свои «23 вопроса» (теперь известные как Проблемы Гильберта ) на втором Международный конгресс математиков в Париже. "Из них вторым было доказательство последовательности"Аксиомы Пеано 'от которого, как он показал, зависела строгость математики "(Ходжес, стр. 83, комментарий Дэвиса в Davis, 1965, стр. 108).
1920–1921: Эмиль Пост исследует проблему остановки для системы тегов, считая его кандидатом на неразрешимость. (Абсолютно неразрешимые проблемы и относительно неразрешимые предположения - счет предвкушения, in Davis, 1965, pp. 340–433). Его неразрешимость была установлена намного позже, Марвин Мински (1967).
1928: Гильберт переработал свою «Вторую проблему» на Болонском международном конгрессе. (Рейд, стр. 188–189) Ходжес утверждает, что задал три вопроса: например, №1: была ли математика полный? # 2: Была математика последовательный? # 3: Была математика разрешимый? (Ходжес стр. 91). Третий вопрос известен как Entscheidungsproblem (Проблема решения). (Ходжес стр.91, Пенроуз стр.34)
1930: Курт Гёдель объявляет доказательство как ответ на первые два вопроса Гильберта 1928 г. [ср. Reid p. 198]. «Сначала он [Гильберт] был только зол и разочарован, но затем он начал пытаться конструктивно решить проблему ... Сам Гёдель чувствовал - и выразил мысль в своей статье, - что его работа не противоречит формалистической точке зрения Гильберта. вид »(Рид стр. 199)
1931: Гедель публикует «О формально неразрешимых предложениях Principia Mathematica и родственных систем I» (перепечатано в Davis, 1965, стр. 5ff).
19 апреля 1935 г .: Церковь Алонсо публикует "Неразрешимую проблему элементарной теории чисел", в которой он определяет, что означает, что функция должна быть эффективно вычисляемый. Такая функция будет иметь алгоритм, и «... факт завершения работы алгоритма становится фактически известным ...» (Дэвис, 1965, стр. 100)
1936: Черч публикует первое доказательство того, что Entscheidungsproblem неразрешимо. (Замечание о проблеме Entscheidungsproblem, перепечатано в Davis, 1965, p. 110.)
7 октября 1936 г .: Эмиль Пост Получена статья «Конечные комбинаторные процессы. Формулировка I». Пост добавляет к своему «процессу» инструкцию «(C) Stop». Он назвал такой процесс «типом 1 ... если процесс, который он определяет, завершается для каждой конкретной проблемы». (Дэвис, 1965, стр. 289 и далее).
1937: Алан Тьюринг бумага О вычислимых числах в приложении к задаче Entscheidungs. выходит в печать в январе 1937 г. (перепечатано в Davis, 1965, стр. 115). Доказательство Тьюринга отклоняется от расчета рекурсивные функции и вводит понятие машинного вычисления. Стивен Клини (1952) называет это одним из «первых примеров проблем, связанных с решением, которые оказались неразрешимыми».
1939: Дж. Баркли Россер отмечает существенную эквивалентность «эффективного метода», определенного Геделем, Черчем и Тьюрингом (Россер в Дэвисе, 1965, стр. 273, «Неформальное изложение доказательств теоремы Геделя и теоремы Черча»)
1943: В статье, Стивен Клини утверждает, что «При создании полной алгоритмической теории мы описываем процедуру ... которая обязательно завершается таким образом, чтобы по ее результату мы могли прочитать однозначный ответ« Да »или« Нет »на вопрос: "Верно ли значение предиката?" ".
1952: Клини (1952) Глава XIII («Вычислимые функции») включает обсуждение неразрешимости проблемы остановки для машин Тьюринга и переформулирует ее в терминах машин, которые «в конечном итоге останавливаются», то есть останавливаются: «... нет алгоритм определения того, может ли данная машина при запуске из любой данной ситуации в конце концов останавливается. »(Клини (1952) стр. 382)
1952: "Мартин Дэвис считает вероятным, что он впервые использовал термин «проблема остановки» в серии лекций, которые он прочитал в Лаборатории систем управления в Университете Иллинойса в 1952 году (письмо Дэвиса Коупленду, 12 декабря 2001 г.) »(сноска 61 в Коупленд (2004), стр. 40 и далее)

Формализация

В своем первоначальном доказательстве Тьюринг формализовал понятие алгоритм путем введения Машины Тьюринга. Однако результат никоим образом не специфичен для них; это в равной степени относится к любой другой модели вычисление это эквивалентно по своей вычислительной мощности машинам Тьюринга, таким как Марковские алгоритмы, Лямбда-исчисление, Почтовые системы, зарегистрировать машины, или же системы тегов.

Важно то, что формализация позволяет напрямую отображать алгоритмы в некоторые тип данных что алгоритм можно оперировать. Например, если формализм позволяет алгоритмам определять функции над строками (такими как машины Тьюринга), тогда должно быть отображение этих алгоритмов на строки, и если формализм позволяет алгоритмам определять функции над натуральными числами (такими как вычислимые функции ) тогда должно быть отображение алгоритмов в натуральные числа. Сопоставление со строками обычно является наиболее простым, но строки по алфавит с п символы также могут быть сопоставлены с числами, интерпретируя их как числа в п-ари система счисления.

Представление в виде набора

Условное представление задач решения - это совокупность объектов, обладающих рассматриваемым свойством. В остановка

K = {(я, Икс) | программа я останавливается при запуске на входе Икс}

представляет собой проблему остановки.

Этот набор рекурсивно перечислимый, что означает, что существует вычислимая функция, которая перечисляет все пары (я, Икс) это содержит. Однако дополнение этого набора не является рекурсивно перечислимым.^[5]

Есть много эквивалентных формулировок проблемы остановки; любой набор, чей Степень Тьюринга такая формулировка равна проблеме остановки. Примеры таких наборов включают:

{я | программа я в конечном итоге останавливается при запуске с вводом 0}
{я | есть вход Икс такая программа я в конечном итоге останавливается при запуске с вводом Икс}.

Концепция доказательства

Доказательство неразрешимости проблемы остановки - это доказательство от противного. Чтобы проиллюстрировать концепцию доказательства, предположим, что существует общий вычислимая функция остановки (f) который возвращает истину, если подпрограмма ж останавливается (при запуске без входных данных) и возвращает false в противном случае. Теперь рассмотрим следующую подпрограмму:

def грамм():    если остановки(грамм):        loop_forever()

остановки (г) должен либо вернуть истину, либо ложь, потому что остановки предполагалось, что это общий. Если остановки (г) возвращает истину, тогда грамм позвоню loop_forever и никогда не останавливаться - противоречие. Если остановки (г) возвращает false, тогда грамм остановится, потому что он не будет звонить loop_forever; это тоже противоречие. Общий, остановки (г) не может вернуть значение истинности, которое согласуется с тем, грамм останавливается. Поэтому исходное предположение, что остановки полная вычислимая функция должна быть ложной.

Метод, использованный в доказательстве, называется диагонализация - грамм делает противоположное тому, что остановки говорит грамм стоит сделать. Разница между этим наброском и фактическим доказательством состоит в том, что в фактическом доказательстве вычислимая функция остановки не принимает подпрограмму в качестве аргумента напрямую; вместо этого он берет исходный код программы. Фактическое доказательство требует дополнительной работы для решения этой проблемы. Более того, фактическое доказательство избегает прямого использования рекурсии, показанной в определении грамм.

Эскиз доказательства

Приведенная выше концепция показывает общий метод доказательства; в этом разделе будут представлены дополнительные сведения. Общая цель - показать, что нет общий вычислимая функция это решает, будет ли произвольная программа я останавливается при произвольном вводе Икс; то есть следующая функция час не вычислимо (Пенроуз 1990, стр. 57–63):

{displaystyle h (i, x) = {egin {case} 1 & {ext {if}} {ext {program}} i {ext {останавливается при вводе}} x, 0 & {ext {else.}} end {cases }}}

Здесь программа я относится к я -я программа в перечисление всех программ фиксированного Полный по Тьюрингу модель вычисления.

ж(я,j)		я
ж(я,j)		1	2	3	4	5	6
j	1	1	0	0	1	0	1
	2	0	0	0	1	0	0
	3	0	1	0	1	0	1
	4	1	0	0	1	0	0
	5	0	0	0	1	1	1
	6	1	1	0	0	1	0

	ж(я,я)	1	0	0	1	1	0
	грамм(я)	U	0	0	U	U	0

Возможные значения для полной вычислимой функции ж расположены в 2D-массиве. Оранжевые клетки - диагональ. Ценности ж(я,я) и грамм(я) показаны внизу; U указывает, что функция грамм не определено для конкретного входного значения.

Доказательство начинается с прямого установления того, что никакая полная вычислимая функция с двумя аргументами не может быть искомой функцией. час. Как в наброске концепции, для любой вычислимой полной бинарной функции ж, следующее частичная функция грамм также вычисляется какой-то программой е:

{displaystyle g (i) = {egin {case} 0 & {ext {if}} f (i, i) = 0, {ext {undefined}} & {ext {else.}} end {cases}}}

Подтверждение того, что грамм вычислимо полагается на следующие конструкции (или их эквиваленты):

вычислимые подпрограммы (программа, которая вычисляет ж это подпрограмма в программе е),
дублирование значений (программа е вычисляет входы я,я за ж со входа я за грамм),
условное ветвление (программа е выбирает между двумя результатами в зависимости от значения, которое он вычисляет для ж(я,я)),
не дает определенного результата (например, бесконечный цикл),
возвращает значение 0.

Следующее псевдокод иллюстрирует простой способ вычисления грамм:

процедура compute_g(я):    если ж(я, я) == 0 тогда        возвращаться 0    еще        петля навсегда

Потому что грамм частично вычислим, должна быть программа е что вычисляет грамм, исходя из предположения, что модель вычислений является полной по Тьюрингу. Эта программа - одна из всех программ, в которых функция остановки час определено. Следующий шаг доказательства показывает, что час(е,е) не будет иметь того же значения, что и ж(е,е).

Из определения грамм что должен выполняться ровно один из следующих двух случаев:

ж(е,е) = 0 и поэтому грамм(е) = 0. В этом случае час(е,е) = 1, потому что программа е останавливается при вводе е.
ж(е,е) ≠ 0 и поэтому грамм(е) не определено. В этом случае час(е,е) = 0, поскольку программа е не останавливается при вводе е.

В любом случае, ж не может быть той же функцией, что и час. Потому что ж был произвольный полная вычислимая функция с двумя аргументами, все такие функции должны отличаться от час.

Это доказательство аналогично Диагональный аргумент Кантора. Можно визуализировать двумерный массив с одним столбцом и одной строкой для каждого натурального числа, как указано в таблице выше. Значение ж(я,j) помещается в столбец я, ряд j. Потому что ж предполагается, что это полная вычислимая функция, любой элемент массива может быть вычислен с использованием ж. Построение функции грамм можно визуализировать с помощью главной диагонали этого массива. Если массив имеет 0 в позиции (я,я), тогда грамм(я) равно 0. В противном случае грамм(я) не определено. Противоречие связано с тем, что есть столбец е массива, соответствующего грамм сам. Теперь предположим ж была функция остановки час, если грамм(е) определено (грамм(е) = 0 в этом случае), грамм(е) останавливается так ж(е, е) = 1. Но грамм(е) = 0 только тогда, когда ж(е, е) = 0, что противоречит ж(е, е) = 1. Аналогично, если грамм(е) не определено, то функция остановки ж(е, е) = 0, что приводит к грамм(е) = 0 при грамм'строительство. Это противоречит предположению грамм(е) не определяется. В обоих случаях возникает противоречие. Поэтому любая произвольная вычислимая функция ж не может быть функцией остановки час.

Теория вычислимости

Типичный метод доказательства неразрешимости проблемы - это метод снижение^{[требуется разъяснение ]}. Для этого достаточно показать, что если решение новой проблемы было найдено, его можно было бы использовать для решения неразрешимой проблемы путем преобразования экземпляров неразрешимой проблемы в экземпляры новой проблемы. Поскольку мы уже знаем, что нет метод может решить старую проблему, никакой метод также не может решить новую проблему. Часто новая проблема сводится к решению проблемы остановки. (Тот же метод используется, чтобы продемонстрировать, что проблема НП завершена, только в этом случае, вместо демонстрации отсутствия решения, он демонстрирует отсутствие полиномиальное время решение, предполагая P ≠ NP.)

Например, одним из таких последствий неразрешимости проблемы остановки является то, что не может быть общего алгоритм это решает, будет ли данное утверждение о натуральные числа верно или неверно. Причина в том, что предложение утверждение, что определенная программа остановится при определенных входных данных, может быть преобразовано в эквивалентное утверждение о натуральных числах. Если бы у нас был алгоритм, который мог бы найти значение истинности каждого утверждения о натуральных числах, он определенно мог бы найти значение истинности этого утверждения; но это определило бы, остановится ли исходная программа, что невозможно, поскольку проблема остановки неразрешима.

Теорема Райса обобщает теорему о неразрешимости проблемы остановки. В нем говорится, что для любой нетривиальное свойство, не существует общей процедуры принятия решения, которая для всех программ решает, имеет ли частичная функция, реализованная входной программой, это свойство. (Частичная функция - это функция, которая не всегда может давать результат, и поэтому используется для моделирования программ, которые могут либо давать результаты, либо не останавливаться.) Например, свойство «остановка для входа 0» неразрешимо. Здесь «нетривиальный» означает, что набор частичных функций, удовлетворяющих этому свойству, не является ни пустым набором, ни набором всех частичных функций. Например, «останавливается или не останавливается на входе 0» явно верно для всех частичных функций, так что это тривиальное свойство, и его можно определить с помощью алгоритма, который просто сообщает «истина». Кроме того, эта теорема верна только для свойств частичной функции, реализованной программой; Теорема Райса не распространяется на свойства самой программы. Например, «остановка на входе 0 в пределах 100 шагов» будет нет свойство частичной функции, реализуемой программой, - это свойство программы, реализующей частичную функцию, и оно очень разрешимо.

Григорий Чайтин определил вероятность остановки, представленный символом Ω, тип действительного числа, которое неформально считается представляющим вероятность что случайно созданная программа останавливается. Эти числа совпадают Степень Тьюринга как проблема остановки. Это нормальный и трансцендентное число который может быть определенный но не может быть полностью вычислен. Это означает, что можно доказать, что нет алгоритм который дает цифры Ω, хотя первые несколько цифр могут быть вычислены в простых случаях.

Хотя доказательство Тьюринга показывает, что не может быть общего метода или алгоритма для определения того, останавливаются ли алгоритмы, отдельные экземпляры этой проблемы вполне могут быть уязвимы для атаки. Учитывая конкретный алгоритм, часто можно показать, что он должен останавливаться при любом вводе, и на самом деле компьютерные ученые часто делают это как часть доказательство правильности. Но каждое доказательство должно разрабатываться специально для рассматриваемого алгоритма; здесь нет механический, общий способ чтобы определить, останавливаются ли алгоритмы на машине Тьюринга. Однако есть некоторые эвристика которые можно использовать в автоматическом режиме, чтобы попытаться построить доказательство, которое часто оказывается успешным в типичных программах. Эта область исследований известна как автоматизированная анализ прекращения.

Поскольку отрицательный ответ на проблему остановки показывает, что существуют проблемы, которые не могут быть решены машиной Тьюринга, Тезис Черча – Тьюринга ограничивает возможности любой машины, на которой эффективные методы. Однако не все машины, вообразимые человеческим воображением, подчиняются тезису Чёрча-Тьюринга (например, машины-оракулы ). Это открытый вопрос, могут ли быть детерминированные физические процессы что, в конечном итоге, ускользнет от моделирования машиной Тьюринга, и, в частности, можно ли использовать какой-либо такой гипотетический процесс в виде вычислительной машины ( гиперкомпьютер ), который, помимо прочего, может решить проблему остановки машины Тьюринга. Также остается открытым вопрос, участвуют ли такие неизвестные физические процессы в работе человеческий мозг и смогут ли люди решить проблему остановки (Copeland 2004, p. 15).

Теоремы Гёделя о неполноте

Концепции, поднятые Теоремы Гёделя о неполноте очень похожи на те, которые возникают в связи с проблемой остановки, и доказательства очень похожи. Фактически, более слабая форма Первой теоремы о неполноте является простым следствием неразрешимости проблемы остановки. Эта более слабая форма отличается от стандартной формулировки теоремы о неполноте тем, что утверждает, что аксиоматизация натуральных чисел, которое является как полным, так и звук невозможно. «Здоровая» часть - это ослабление: это означает, что мы требуем, чтобы рассматриваемая аксиоматическая система доказывала только истинный утверждения о натуральных числах. Поскольку разумность подразумевает последовательность, эту более слабую форму можно рассматривать как следствие сильной формы. Важно отметить, что утверждение стандартной формы первой теоремы Гёделя о неполноте совершенно не связано с истинностью утверждения, а касается только вопроса о том, можно ли найти его с помощью математическое доказательство.

Более слабая форма теоремы может быть доказана из неразрешимости проблемы остановки следующим образом. Предположим, что у нас есть звук (и, следовательно, непротиворечивый) и полный аксиоматизация всего правда логика первого порядка заявления о натуральные числа. Затем мы можем построить алгоритм, который перечислит все эти утверждения. Значит, есть алгоритм N(п), что при натуральном числе п, вычисляет истинное логическое утверждение первого порядка о натуральных числах, и что для всех истинных утверждений существует хотя бы один п такой, что N(п) дает это утверждение.Теперь предположим, что мы хотим решить, будет ли алгоритм с представлением а останавливается при вводе я. Мы знаем, что это утверждение может быть выражено логическим утверждением первого порядка, например ЧАС(а, я). Из полной аксиоматизации следует, что либо существует п такой, что N(п) = ЧАС(а, я) или есть п ' такой, что N(п ') = ¬ ЧАС(а, я). Итак, если мы повторять общий п пока мы не найдем ЧАС(а, я) или его отрицание, мы всегда будем останавливаться, и, более того, ответ, который он нам дает, будет истинным (по разумности). Это означает, что это дает нам алгоритм для решения проблемы остановки. Поскольку мы знаем, что такого алгоритма быть не может, отсюда следует, что предположение о том, что существует непротиворечивая и полная аксиоматизация всех истинных логических утверждений первого порядка о натуральных числах, должно быть ложным.

Обобщение

Многие варианты проблемы остановки можно найти в учебниках по вычислимости (например, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft and Ullman 1979, Börger 1989). Обычно их неразрешимость следует из снижение из стандартной проблемы остановки. Однако у некоторых из них выше степень неразрешимости. Следующие два примера типичны.

Остановка на всех входах

В универсальная проблема остановки, также известный (в теория рекурсии ) в качестве совокупность, проблема определения, остановит ли данная компьютерная программа для каждого входа (название совокупность происходит из эквивалентного вопроса о том, является ли вычисляемая функция общий Эта проблема не только неразрешима, как проблема остановки, но и в высшей степени неразрешима. Что касается арифметическая иерархия, это ${displaystyle Pi _ {2} ^ {0}}$ -полное (Börger 1989, p. 121).

Это, в частности, означает, что его нельзя решить даже с помощью оракул для проблемы остановки.

Признание частичных решений

Есть много программ, которые для некоторых входных данных возвращают правильный ответ на проблему остановки, в то время как для других входных данных они не возвращают ответ вообще. Однако проблема "данной программы" п"является ли это решатель частичной остановки" (в описанном смысле) по крайней мере так же сложен, как и проблема остановки. Чтобы убедиться в этом, предположим, что для этого существует алгоритм PHSR ("распознаватель решателя частичной остановки"). Тогда он может использоваться для решения проблемы остановки следующим образом: Чтобы проверить, работает ли программа ввода Икс останавливается на у, построить программу п что на входе (Икс,у) отчеты истинный и расходится по всем остальным входам. Потом тест п с PHSR.

Приведенный выше аргумент является снижение проблемы остановки к распознаванию PHS, и, таким же образом, более сложные проблемы, такие как остановка на всех входах также может быть уменьшено, подразумевая, что распознавание PHS не только неразрешимо, но и выше в арифметическая иерархия, конкретно ${displaystyle Pi _ {2} ^ {0}}$ -полный.

Расчет с потерями

А машина Тьюринга с потерями - это машина Тьюринга, в которой часть ленты может недетерминированно исчезнуть. Проблема остановки разрешима для машины Тьюринга с потерями, но непримитивно рекурсивный.^[6]^:92

Машины Oracle

Машина с оракул поскольку проблема остановки может определить, остановятся ли определенные машины Тьюринга на определенных входных данных, но они не могут определить, в целом, остановятся ли машины, эквивалентные им самим.

Смотрите также

Примечания

^ Ни в одной из своих работ Тьюринг не использовал слова «остановка» или «прекращение». У биографа Тьюринга Ходжеса нет слова «остановка» или слова «проблема остановки» в указателе. Самое раннее известное употребление слова «проблема остановки» находится в доказательстве Дэвиса (1958, стр. 70–71):
"Теорема 2.2 Существует машина Тьюринга, проблема остановки которой рекурсивно неразрешима..
"Связанная проблема - проблема печати для простой машины Тьюринга Z относительно символа S_я".
Дэвис не добавляет никаких указаний на свое доказательство, поэтому можно сделать вывод, что оно принадлежит ему оригиналу. Но Дэвис указал, что формулировка доказательства неформально существует в Клини (1952, стр. 382). Коупленд (2004, стр. 40) утверждает, что:
«Проблема остановки была так названа (и, кажется, впервые сформулирована) Мартином Дэвисом [см. Сноску Коупленда 61] ... (Часто говорят, что Тьюринг сформулировал и доказал теорему остановки в« О вычислимых числах », но строго это неправда)."
^ МакКоннелл, Стив (2004), Код завершен (2-е изд.), Pearson Education, стр. 374, г. ISBN 9780735636972
^ Хан-Вэй Хуанг.«HCS12 / 9S12: Введение в интерфейс программного и аппаратного обеспечения».п. 197. цитата: «... если программа застревает в каком-то цикле, ... выясняйте, что не так».
^ Дэвид Э. Саймон.«Учебник по встроенному программному обеспечению».1999.p. 253. цитата: «Поэтому для систем жесткого реального времени важно писать подпрограммы, которые всегда выполняются в одно и то же время или имеют четко определяемый наихудший случай».
^ Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений. Издательство Оксфордского университета. С. 236–237. ISBN 978-0-19-923321-2.
^ Абдулла, Парош Азиз; Йонссон, Бенгт (1996). «Проверка программ с ненадежными каналами». Информация и вычисления. 127 (2): 91–101. Дои:10.1006 / inco.1996.0053.

внешняя ссылка

Зачерпание петли snooper - поэтическое доказательство неразрешимости проблемы остановки
мультфильм - анимация, поясняющая доказательство неразрешимости проблемы остановки
2-минутное доказательство второй по важности теоремы 2-го тысячелетия - доказательство всего в 13 строках

[1] Ни в одной из своих работ Тьюринг не использовал слова «остановка» или «прекращение». У биографа Тьюринга Ходжеса нет слова «остановка» или слова «проблема остановки» в указателе. Самое раннее известное употребление слова «проблема остановки» находится в доказательстве Дэвиса (1958, стр. 70–71):
"Теорема 2.2 Существует машина Тьюринга, проблема остановки которой рекурсивно неразрешима..
"Связанная проблема - проблема печати для простой машины Тьюринга Z относительно символа S_я".
Дэвис не добавляет никаких указаний на свое доказательство, поэтому можно сделать вывод, что оно принадлежит ему оригиналу. Но Дэвис указал, что формулировка доказательства неформально существует в Клини (1952, стр. 382). Коупленд (2004, стр. 40) утверждает, что:
«Проблема остановки была так названа (и, кажется, впервые сформулирована) Мартином Дэвисом [см. Сноску Коупленда 61] ... (Часто говорят, что Тьюринг сформулировал и доказал теорему остановки в« О вычислимых числах », но строго это неправда)."

[2] МакКоннелл, Стив (2004), Код завершен (2-е изд.), Pearson Education, стр. 374, г. ISBN 9780735636972

[3] Хан-Вэй Хуанг.«HCS12 / 9S12: Введение в интерфейс программного и аппаратного обеспечения».п. 197. цитата: «... если программа застревает в каком-то цикле, ... выясняйте, что не так».

[4] Дэвид Э. Саймон.«Учебник по встроенному программному обеспечению».1999.p. 253. цитата: «Поэтому для систем жесткого реального времени важно писать подпрограммы, которые всегда выполняются в одно и то же время или имеют четко определяемый наихудший случай».

[5] Мур, Кристофер; Мертенс, Стефан (2011). Природа вычислений. Издательство Оксфордского университета. С. 236–237. ISBN 978-0-19-923321-2.

[Undecidable_over_unreliable_channels-6] Абдулла, Парош Азиз; Йонссон, Бенгт (1996). «Проверка программ с ненадежными каналами». Информация и вычисления. 127 (2): 91–101. Дои:10.1006 / inco.1996.0053.

[1]

[2]

[3]

[4]

[5]

[6]