Сокращение среди неразрешимых проблем

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

computability reductions undecidability swarnim_narayan
источник

Краткий ответ: далеко не тривиально! Посмотрите на Арифметическую иерархию .

Хендрик Ян

Что об этом: если является неразрешимым язык и наименьший элемент в

. Тогда

сводится (и наоборот) в

. Если вы дополнительно добавите элемент в

(скажем, самый маленький элемент не в

), то у вас есть 1-1-сокращение.

L

$L$

x min L

$x \min L$

L

$L$

L^{'} = L ∖ {x}

$L' = L \setminus \{x\}$

L

$L$

L^{'}

$L'$

L

$L$

Пол GD

Ответы:

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

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

Юваль Фильмус
источник

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

swarnim_narayan

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

Yuval Filmus

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

Юваль Филмус