Является ли решение решаемости разрешимым?

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

computability undecidability decision-problem синхронизация
источник

Эй, черт возьми, я слышал, что тебе нравится решимость, так что ...

Дэвид Ричерби

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

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

. Но как ты это делаешь?

M

$M$

M

$M$

Дэвид Ричерби

Принимая во внимание текущие ответы, есть вопрос «Является ли решение решить, разрешимость решаемо разрешимо?», Но я не собираюсь его задавать :-)

Марк Херд

Ответы:

Основное редактирование моего оригинала:

$P$

$P=$ $L$

Тогда вы спросите

$P$

$L(M)$ $M$ $P$

$P'=$ $\langle M\rangle$ $M$ $L(M)$

$P'$ $P$ $P'$

{⟨ M ⟩ ∣ M is a TM and L (M) is decidable}

$\{\langle M\rangle\mid M \text{ is a TM and $L(M)$ is decidable}\}$

Рик Декер
источник

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

синхронизация

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

rus9384

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

В 1985 году Йост Энгельфриет написал «Невычислимость вычислимости» (Бюллетень EATCS № 26, июнь 1985 г., стр. 36–39) как ответ на вопрос, заданный умным учеником. К сожалению, BEATCS был в то время только для бумаг, и статья не оставила электронных следов.

$\Psi$ $F(m,n)$ $f:\Bbb N \to \Bbb N$ $m,n\in \Bbb N$ $f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$ $\underline m$ $m$

Я цитирую:

$\Phi$ $\Bbb N \to \Bbb N$ $f$ $f$

Самое интересное в следующем наблюдении, сделанном в статье:

$\Phi$

Хендрик Ян
источник

Да. Это всегда решаемо.

Для любой проблемы P пусть Q будет проблемой определения, является ли P разрешимым или нет. Я утверждаю, что Q разрешима. Вот почему Тавтологически, либо P разрешимо, либо нет. Итак, одна из двух программ верна: (1) print "yup P is decidable"или (2) print "nope P is not decidable". Может быть нетривиально выяснить, какая из этих двух программ правильная, одна из них правильная, поэтому определитель Q всегда существует . Следовательно, проблема Q разрешима.

Это напоминает следующий классический вопрос: можно ли сказать, верна ли гипотеза Коллатца? Ответ - да. Это может выглядеть странно, так как никто не знает, верна ли гипотеза Коллатца (это известная открытая проблема). Тем не менее, мы знаем, что гипотеза Коллатца либо верна, либо нет. В первом случае программа print "yup it's true"является решающей. В последнем случае программа print "nope it's not true"является решающей. Мы не знаем, какой из них является действительным решающим фактором, но этого достаточно, чтобы доказать, что существует действительный решающий фактор. Поэтому проблема разрешима.

DW
источник

Я думаю, что Рикки Деккер интерпретирует этот вопрос лучше. Учитывая некоторую кодировку проблемы, решите, является ли проблема разрешимой.

Юваль Фильмус

@YuvalFilmus, хорошо, это разумно. У вас есть конечная кодировка для проблем (например, языков), которые вы считаете разумными, и не делает проблему тривиальной? Естественная конечная кодировка для языка - это машина Тьюринга, которая распознает этот язык, но это делает проблему тривиальной, как показывает ваш комментарий к ответу Рики Деккера. Поэтому нам понадобится другое разумное кодирование, которое не будет страдать от такого рода проблем. У вас есть предложения по этому поводу?

Вы можете использовать логику первого порядка на некотором соответствующем языке. Или вход может быть машиной в 0 '(например), то есть машиной Тьюринга с доступом к остановившемуся оракулу.

Юваль Фильмус

По теореме Райс мы знаем, что даже решение R во вселенной RE неразрешимо. Разве этого не достаточно? (Не все ТМ являются решающими.)

Рафаэль

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

синхронизация