Есть ли доказательства неразрешимости проблемы остановки, которая не зависит от самоссылки или диагонализации?

40

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

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

Так что вопрос

Есть ли доказательство того, что проблема остановки неразрешима, что не зависит от того, чтобы показать, что HALT не может решить сам, и не зависит от аргумента диагонализации?

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

М. Алагган
источник
Вы ищете тот, который не зависит от аргумента диагонализации, или тот, который не диагонализируется с помощью HALT напрямую? Я не уверен, что доказательство, предложенное Бьёрном, удовлетворяет первому.
Марк Рейтблатт
@Mark: я не уверен на самом деле. Если аргумент диагонализации соответствует не самоссылке, а другому аспекту, такому как несоответствие количества элементов, тогда я действительно надеюсь, что он даст некоторое представление о том, почему прекращение HALT (Q) (где Q! = HALT) неразрешимо ,
М. Алагган
1
Ну, в таком случае, я могу привести более простой аргумент. Начните с наблюдения, что существуют неразрешимые проблемы (простой аргумент кардинальности) и, более того, существует неразрешимая проблема P, у которой есть TM M, который распознает своих членов (но может не заканчиваться на нечленах). Теперь решение HALT (M) дает вам решение для P. Сначала проверим, останавливается ли M на x. Если это так, мы запускаем его и возвращаем то же самое, что и M. В противном случае мы отвергаем, поскольку M останавливается на каждом члене P. Это теперь противоречие, так как мы предполагали, что P был языком без решающего.
Марк Рейтблатт
Этот аргумент фактически является доказательством того, что HALT RE-полон.
Марк Рейтблатт
1
Попался. Если все ТМ были решающими, то HALT тривиален. Если остановка нетривиальна (распознаватели существуют), то (в отличие от положительного) существование нетривиального HALT делает решатели распознавателей ТМ решающими, что означает, что HALT является тривиальным противоречием. Поэтому такой HALT не может существовать для всех распознавателей. Это замечательно, спасибо за ваш замечательный комментарий; Вы можете опубликовать его в ответ :)
M. Alaggan

Ответы:

31

Да, есть такие доказательства в теории вычислимости (она же теория рекурсии).

Сначала вы можете показать, что проблема остановки (набор ) может быть использована для вычисления набора который является 1-общим, что означает, что в некотором смысле каждый факт о решается конечным префикс . Тогда легко доказать, что такое множество не может быть вычислимо (т. Е. Разрешимо). G N Σ 0 1 G G G0GNΣ10GGG

Мы могли бы заменить 1- общий тип на 1-случайный, т. Е. Случайный Мартин-Лёф , для того же эффекта. Здесь используется теорема Джокуша-Соаре о низком базисе .

(Предупреждение: можно было бы просто показать, что вычисляет Chaitin's , который является 1-случайным, но здесь мы должны быть осторожны с тем, полагает ли доказательство того, что 1-random, делает проблему остановки неразрешимой! безопаснее просто использовать теорему о низком базисе).Ω Ω0ΩΩ

Бьёрн Кьос-Хансен
источник
Очень интересно! Можете ли вы предоставить мне ссылку или набор ключевых слов для поиска, чтобы я мог лучше понять его? Большое спасибо!
М. Алагган
6
@M. Алагган: Лучшая ссылка может быть в недавней книге Андре Ниеса « Вычислительность и случайность» , Oxford Logic Guides, Oxford University Press, 2009. Также есть статья в Википедии о теореме низкого базиса и статья в Scholarpedia об алгоритмической случайности: scholarpedia.org / article / Algorithmic_randomness
Бьёрн Кьос-Ханссен
@M. Alaggan, это зависит от вас, но голоса предполагают, что это должен быть принятый ответ.
Мухаммед Аль-Туркистани
Я спрашиваю о мета (проверьте meta.cstheory.stackexchange.com/questions/642/when-is-it-ptable-to-change-the-accepted-answer). Я знаю, что этот ответ действительно хорош и очень полезен. Я принял другой, однако, потому что мне было намного легче понять с более интуитивным подходом. Тем не менее, выше, кажется, обсуждение его правильности (!). Так что, если он окажется неверным, я действительно перейду к этому ответу. Путаница возникла из-за того, что я не был конкретен в исходном вопросе, который я хотел избежать диагонализации с использованием HALT, а не всех диагонализаций.
М. Алагган
Я очень смущен тем, что мне следует принять до этого момента, поскольку я выбираю между выдающимся великолепным ответом и простым / интуитивным ответом (мой опыт не очень твердый / зрелый). Так что, пожалуйста, не обижайтесь :) Мы можем обсудить это и прийти к удовлетворительному решению для всех. Спасибо.
М. Алагган
5

Повторно из моего комментария согласно запросу:

Начните с наблюдения, что существуют неразрешимые проблемы (простой аргумент кардинальности) и, более того, существует неразрешимая проблема P, у которой есть TM M, который распознает своих членов (но может не заканчиваться на нечленах). Теперь решение HALT (M) дает вам решение для P. Сначала проверим, останавливается ли M на x. Если это так, мы запускаем его и возвращаем то же самое, что и M. В противном случае мы отвергаем, поскольку M останавливается на каждом члене P. Теперь это противоречие, так как мы предполагали, что P неразрешима.

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

РЕДАКТИРОВАТЬ: Этот аргумент застрял. Можете ли вы показать, что RE - REC не пуст, кроме того, что показывает, что HALT там?

Марк Рейтблатт
источник
Аргумент счетности использует очень похожую (только немного более простую) диагонализацию, чем стандартное доказательство для проблемы остановки. (То есть, чтобы показать, что мощность языков больше, чем у ТМ, используется диагонализация.) :)
Джошуа Грохов
@ Джошуа Читайте комментарии. Я спросил, ищет ли он доказательство, которое избегало диагонализацию, или то, которое просто избегало диагонализацию с использованием HALT. Он ищет последнее.
Марк Рейтблатт
@Mark: Ах, я пропустил это. Спасибо. +1
Джошуа Грохов
4
@ Марк: Не могли бы вы уточнить что-нибудь, пожалуйста? Вы начинаете с того, что замечаете, что существует неразрешимая проблема P, которую можно распознать, а затем наблюдаете, что если бы HALT был разрешимым, то мы могли бы построить решающее значение для P. Однако в прочитанных мною текстах все доказано в другом порядке: неразрешимость HALT используется для демонстрации существования таких проблем P. Можете ли вы показать существование неразрешимых, но все же узнаваемых проблем, не используя неразрешимость HALT?
Курт
2
Тот факт, что существует распознаваемая, но неразрешимая проблема, возможно, легче всего доказать, если показать, что проблема остановки - это такая проблема, и в этом случае вы вернулись к тому, с чего начали. Существует только много узнаваемых языков.
Бьёрн Кьос-Хансен
2

Другой постер ссылался на это (ссылаясь на Chaitin), но вы можете использовать парадокс Берри, чтобы доказать, что проблема остановки неразрешима. Вот краткий набросок доказательства:

Пусть HALT будет машиной, которая решает, будет ли какая-либо машина M останавливаться на входе I. Мы покажем, что сам HALT не останавливается на конкретном входе, что показывает, что он не может выбрать язык.

Рассмотрим следующую функцию f:

f (M, n) = a, где a - наименьшее натуральное число, не вычисляемое машиной M на любом входе I с | I | <п

Предполагая, что HALT является вычислимой функцией, f также вычислимой функцией; просто смоделируйте HALT (M, I) для каждой машины M и введите строку I с длиной I, меньшей n. Если имитация останавливается, смоделируйте M (I) и запишите, что это за выход, и найдите наименьший выход a, который не выводится ни одной из пар M, n.

Теперь покажем, что f не вычислимо: рассмотрим f (f, 10000000 * | f | +10000000). Независимо от того, что он выводит, это должно быть (положительное) целое число, которое не может быть вычислено машиной, вычисляющей f на входе I с длиной, меньшей заданной ... и все же мы только что вывели такое целое число с f и намного более коротким вход.

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

Филип Уайт
источник
Whatever it outputs, it ought to be an integer that is not computable by the machine computing f on input I with length less than that given.>nn
5
Я не пытаюсь быть грубым, но ваши возражения не имеют смысла. Функция f определяется как функция, которая выводит целое число, которое не может быть вычислено M на любом входе с длиной меньше n. Таким образом, если не считать бессмысленных апелляций к модульной арифметике, вам будет трудно показать, что выделенное вами предложение является недействительным.
Филипп Уайт
@johne Я согласен с Филиппом. Нет никаких предположений относительно пределов представления машины. Это ТМ.
Марк Рейтблатт
@Philip Незначительная техническая коррекция: вы должны изменить целое число на натуральное или положительное целое.
Марк Рейтблатт
1
ff
0

{We}e=1feWe=Wf(e)0fe0We0eWe(0)Wf(e)(0)


источник
6
Это стандартное доказательство диагонализации.
Юваль Фильмус