Доказательство неразрешимости не путем сокращения от проблемы остановки

Обычный способ доказать неразрешимость состоит в том, чтобы свести к минимуму RE-полную задачу, такую как проблема остановки, правильность в логике первого порядка, выполнимость диофантовых уравнений и т. Д.

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

Как справиться с доказательством неразрешимости без сокращения из RE-полной проблемы? Диагонализация?

computability Дэвид Моннио
источник

Может быть, правильный вопрос: «Каковы разные прямые методы доказать неразрешимость»?

Суреш Венкат

Теорема Гёделя о неполноте рассматривается как «другой путь» ... другое доказательство диагонализации основано на том, что число программ / входных пар исчисляется, но языки неисчислимы, и таким образом, подобен несоизмеримости вещественных чисел. с целыми числами. см. также Q / A относительно теоремы Лаврэ о неподвижной точке

vzn

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

Каве

@vzn: я думаю о незавершенности Годеля как о том же самом доказательстве ...

Джошуа Грохов

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

Марцио Де Биаси

Ответы:

Можно прямо показать, что сложность Колмогорова не вычислима, см., Например, Sipser, 3-е издание, проблема 6.23.

Бьёрн Кьос-Хансен
источник

Это также должно следовать непосредственно из теоремы Чайтена о неполноте , доказательство которой весьма похоже.

Йонатан N

Из предыдущих задач мне кажется, что Сипсер намеревается использовать в этом доказательстве неразрешимость проблемы остановки, поэтому, возможно, стоит набросать прямое доказательство невычислимости в ответе.

Усул

На самом деле сравнение с упражнениями 6.24 и 6.25 также помогает.

Бьорн Кьос-Ханссен

Я подумал, что, возможно, стоит указать - учитывая, что OQ специально спросил о диагонализации - что доказательство того, что K не вычислима, также по существу является диагонализацией. (Действительно, это в основном та же диагонализация с простой ванилью, которая используется, чтобы доказать, что HALT невычислима, что совпадает с оригинальным доказательством Кантора о кардинальности, которое совпадает с доказательством неполноты Годеля и Чейтина, которые являются всего лишь теоремой версии парадокса Рассела ...

Джошуа Грохов

Подумайте, что мне нравится называть проблемой ПОСЛЕДОВАТЕЛЬНОГО ГАССИРОВАНИЯ.

$M$

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

Теперь, изменив оригинальное доказательство Тьюринга, довольно легко показать, что ПОСТОЯННОЕ Угадай неразрешимо (я оставлю это как упражнение для тебя).

$A$ $A$

Скотт Ааронсон
источник

Спасибо, но ... опять же, диагонализационное доказательство. ;-) Моя проблема в том, что у меня есть кое-что, что я считаю неразрешимым (в основном, в течение 35 лет люди всегда искали эвристические алгоритмы или алгоритмы, действительные для подклассов, чтобы решить это), но для которых, кажется, нет ни «очевидного» сокращение от ре ни какой-нибудь хороший аргумент диагонализации ...

Дэвид Моннио

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

Коди

Коди: Я тоже так думал. Но если вы готовы рассмотреть более общие задачи, нежели выбор языка, тогда CONSISTENT GUESSING является довольно естественным контрпримером! (Между прочим, я предполагаю, что вы имели в виду, сводя известные неразрешимые проблемы к вашей проблеме, а не наоборот.)

Скотт Ааронсон

Если то, что вы ищете, является доказательством, которое не является ни а) уменьшением известной полной проблемы, ни б) прямой диагонализацией (которую вы указали в ваших различных комментариях), то, насколько я знаю, вам не повезло. Все доказательства, которые я знаю об этом, не являются сокращением - в том числе и в других превосходных ответах, данных здесь Ааронсоном и Кьос-Ханссеном - основаны на прямой диагонализации.

И все эти диагонализации по сути одно и то же доказательство . Некоторые из них являются небольшими вариантами в доказательстве, которые дают несколько более сильные / более слабые утверждения, но сами доказательства, как правило, представляют собой лишь незначительные изменения. (И все эти доказательства по существу совпадают с оригинальным доказательством Кантора о мощностях, которое совпадает с доказательствами неполноты Годеля и Чейтина, которые являются единственно справедливыми версиями теорем парадокса Рассела ... Настолько, что в одном Я хотел бы знать, можно ли формализовать теорию теоремы обратным математикой, в которой говорится, что по существу существует только одно такое доказательство.)

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

Джошуа Грохов
источник

Я не очень разбираюсь в этой теме, но разве теорема Лоувера о фиксированной точке не является общим обобщением почти всех из них?

Сашо Николов