Что мы знаем об ограниченных версиях проблемы остановки

16

( UPDATE : лучше формируются вопрос ставятся здесь в качестве комментариев к общепринятом ответу ниже , показывает , что этот вопрос не является четко определенным)


Классическое доказательство невозможности проблемы остановки зависит от демонстрации противоречия при попытке применить алгоритм обнаружения остановки к себе в качестве входных данных. Смотрите фон ниже для получения дополнительной информации.

Продемонстрированное противоречие применимо из-за парадокса самоссылки (например, предложение «Это предложение не соответствует действительности»). Но если мы строго запрещаем такие ссылки на себя (т.е. принимаем тот факт, что такие ссылки не могут быть остановлены), с каким результатом мы останемся? Решается ли проблема остановки для оставшегося набора машин, которые не ссылаются на саму себя, или нет?

Вопросы это:

Если мы рассмотрим подмножество всех возможных машин Тьюринга, которые не имеют самоссылки (то есть не принимают их в качестве входных данных), что мы знаем о проблеме остановки для этого подмножества?

ОБНОВИТЬ

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

Предпосылки: Предполагая, что существует противоречие, что существует машина Тьюринга которая может определить вход M, который является кодированием для машины Тьюринга и X , независимо от того, останавливается ли M ( X ) . Затем рассмотрим машину Тьюринга K, которая принимает M и X и использует Q, чтобы решить, останавливается ли M ( X ) или нет, а затем делает обратное, то есть K останавливается, если M ( X ) не останавливается, и не останавливается, если М ( Х )QMXM(X)KMXQM(X)KM(X)M(X)привалы. Тогда демонстрирует противоречие, так как K должен остановиться, если он не останавливается, и не останавливается, когда он останавливается.K(K)K

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

ОБНОВИТЬ

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

Цель состоит в том, чтобы определить его как множество, которое не приводит к противоречию, поставленному в доказательстве (см. «Предпосылки» выше). Это может быть определено следующим образом:

Предполагая, что существует машина Тьюринга которая решает проблему остановки для набора машины Тьюринга S , тогда S не является самоссылкой относительно Q, если она исключает все машины, которые вызывают Q на S (прямо или косвенно). (Понятно, что это означает, что Q не может быть членом S. )QSSQQSQS

Чтобы уточнить, что имеется в виду, косвенно вызывая на S :QS

Вызов на S обозначается машиной Тьюринга Q с набором состояний и определенными возможными начальными входами на ленте (соответствующими любому члену S ), причем голова изначально находится в начале этого входа. Машина W вызывает Q на S «косвенно», если существует (конечная) последовательность шагов, которые W предпримет, чтобы сделать свою конфигурацию «гомоморфной» начальной конфигурации Q ( S ) .QSQSWQSWQ(S)

ОБНОВЛЕНИЕ 2

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

ОБНОВЛЕНИЕ 3

Определение гомоморфизма машины Тьюринга:

TM A гомоморфен TM B, если граф переходов A гомоморфен графу переходов B, в стандартном смысле гомоморфизмов графов с помеченными узлами AND ребер. Граф переходов (V, E) ТМ таков, что V = состояния, E = дуги перехода между состояниями. Каждая дуга помечена символом (S, W, D), S = символом, считываемым с ленты, и W = символом, который должен быть записан на нее, и D = направление, в котором движется шоу головы.

М. Алагган
источник
5
«оставшийся набор несамостоятельных ссылок» Прежде чем я смогу разумно обсудить этот набор, я бы хотел дать определение «самореференции». Тем не менее, я думаю, что это будет сложно определить?
Сэм Нид
1
Существуют исследования о том, как можно остановить программы (хотя этот класс не включает все программы остановки). По сути, они являются парой программы и доказательством того, что она останавливается. Например, если я не ошибаюсь, Agda разрешает только те программы, которые останавливаются. Я думаю, что людям, работающим над логикой и языками программирования, есть, что сказать по этому поводу.
Цуёси Ито
1
QS
2
Возникает интересный вопрос: все ли доказательства неисчислимости (неразрешимости) прослеживаются до метода диагонализации Кантора? Есть ли какое-либо доказательство неразрешимости, которое не опирается прямо или косвенно на метод диагонализации?
Мухаммед Аль-Туркистани

Ответы:

9

Я думаю, что потребуется немного больше работы, чтобы добраться до «четко определенного» вопроса. В частности, это проблематично:

Вызов Q на S обозначается машиной Тьюринга Q с набором состояний и определенными возможными начальными входами на ленте (соответствующими любому члену S), причем голова изначально находится в начале этого входа. Машина W вызывает Q на S «косвенно», если существует (конечная) последовательность шагов, которые W предпримет, чтобы сделать свою конфигурацию «гомоморфной» начальной конфигурации Q (S).

Одна проблема состоит в том, что существует бесконечно много машин Тьюринга, которые вычисляют одну и ту же функцию. В стандартном аргументе диагонализации я могу просто заменить подпрограмму Q другим решающим фактором для HALT, поскольку их бесконечно много. Или функция, которая вычислимо эквивалентна HALT. Так что мне не совсем понятно, как определить ваше понятие «косвенный вызов».

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

Марк Рейтблатт
источник
QЧАС
Это не так просто. Ваше определение сейчас парадоксально, так как вы ищете вычислимый HALT. Но если это вычислимо, любая вычислимая функция вычислимо эквивалентна ей. Но если ваш входной набор содержал частично вычислимые задачи (TM), у вас возникло бы противоречие, поскольку решение проблемы остановки для такого TM дало бы вам процедуру решения этой проблемы.
Марк Рейтблатт
1) Разве невычисляемый HALT не будет означать неразрешимость? Я предполагал, что такой вычислимый HALT существует, надеясь на противоречие. 2) Я не знаком с концепцией, что все вычислимые функции вычислимо эквивалентны друг другу, я цитировал вас, и имел в виду, что это функция, которая решает проблему HALT. Очевидно, что λx.1 вычислимо, но оно не решает HALT. Поправьте меня, если я ошибаюсь, пожалуйста. Что касается полувычислимых задач, HALT может предпринять бесконечное количество шагов, что все равно не приведет к противоречию в первоначальном доказательстве того, что HALT не разрешима.
М. Алагган
1) Верно. Но проблема состоит в том, чтобы попытаться определить ваше представление о «несамостоятельных ссылках». Либо это слабое ограничение, которое допускает диагонализацию, как я утверждал, либо это сильное ограничение, которое устраняет все. 2) Все просто. «Вычислимый эквивалент» примерно означает, что существует вычислимое отображение от одного к другому, которое сохраняет ответы. Но если я могу вычислить ответ, я могу обмануть и сделать отображение тривиальным. 3) Если TM, решающий HALT, сам не завершает свою работу, это не решение для HALT.
Марк Рейтблатт
Еще одна вещь, которая немного сбивает с толку, - это связь ТМ с решаемой ими проблемой решения. Нормально говорить о том, что ТМ вычислительно эквивалентен друг другу. Скорее вычисленные ими функции могут быть эквивалентными (или равными). Проблема в том, что пытаться сказать, что ТМ не моделирует другую ТМ, трудно определить вообще, не давая чего-то конкретного для разделения вычисляемых ими функций. Например, TM Log-space не может имитировать TM, решающую проблему пространства EXP.
Марк Рейтблатт
9

Если я правильно понимаю вашу мотивацию, похоже, что это проблема «правильности компиляции», а не проблема «ограниченной остановки». У вас есть свойство (завершение), которое вы доказали для некоторой программы Prog исходного уровня, которую вы хотите затем распространить на скомпилированный код, чтобы получить то же свойство скомпилированного (Prog) . Но компилятор может (в общем) делать произвольные глупые вещи, такие как реализация среды выполнения с полным лечением (скажем, JVM), компилирование вашей завершающей программы в байт-код JVM, а затем выгрузка исполняемого файла, запускающего JVM, и подача его скомпилированным байт-кодом.

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

Один вариант заключается в том, чтобы иметь компилятор, который принимает в качестве входных данных программу Prog и завершение проверки (Prog), а вывод - компилирование (Prog) и завершение (компилирование (Prog)) - последний может быть проверен дважды, независимо от компилятор. Я считаю, что классическим документом по этому вопросу является Necula and Lee's . Дизайн и реализация сертифицирующего компилятора .

В качестве альтернативы, вы можете доказать факт о функции compiles () - всякий раз, когда compiles () дает завершающий ввод, он производит завершающий вывод. Доступным введением в этот подход к правильности компиляции является статья Ксавье Лероя CACM « Формальная проверка реалистичного компилятора» .

(PS Я надеюсь, что этот ответ полезен - я признаю, что он немного отличается от вопроса, который вы задали, поэтому дайте мне знать, если я зашла в тупик и / или повторяю что-то, что вы уже знаете.)

Роб Симмонс
источник
Спасибо за отличный ответ. Это было бы определенно полезно для моего коллеги. Однако я (независимо от моего коллеги) больше интересуюсь теоретическими последствиями для доказательства проблемы остановки, что, если мы избавимся от случая, который показал противоречие, то что еще мы знаем о разрешимости проблемы остановки?
М. Алагган