неразрешимая проблема и ее отрицание неразрешима

13

Тем не менее, многие «знаменитые» неразрешимые проблемы, по крайней мере, полуразрешимы, а их дополнение неразрешимо. Одним из примеров, прежде всего, может быть проблема остановки и ее дополнение.

Тем не менее, кто-нибудь может привести пример, в котором проблема и ее дополнение неразрешимы и не полурегулируемы? Я думал о языке диагонализации Ld, но мне не кажется, что дополнение неразрешимо.

В этом случае означает ли это, что машина Тьюринга M может «потерять» некоторые строки, которые вместо этого должны быть распознаны, поскольку они являются частью языка, который мы пытаемся идентифицировать?

Джулия Фраскария
источник

Ответы:

15

Рассмотрим следующий язык:

L2={(M1,x1,M2,x2):M1 halts on input x1 and M2 doesn't halt on input x2}.

неразрешима и не полуразрешима, и то же самое верно для ее дополнения. Почему? Интуиция в том, что « M 2 не останавливается на входе x 2 », не является полуразрешимой, поэтому L 2 не является полуразрешимой; и когда вы смотрите на дополнение L 2L2M2x2L2L2 , то же самое происходит и для . Это можно формализовать более тщательно, используя сокращения.M1

В более общем смысле, если является языком, который неразрешим и не является полурешируемым, тоL

L={(x,y):xL,yL}

удовлетворяет вашим требованиям: неразрешима и не полускучаема, и то же самое верно для дополнения L LL .

DW
источник
7

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

Для примера, пусть будет проблемой остановки для машин Тьюринга и пусть М класса машин Тьюринга с оракулом для  H . Пусть H 2 будет проблема остановки для  M . Я утверждаю, что ни H 2, ни  ¯ H 2 не являются полуразрешимымиHMHH2MH2H2¯

Мы можем показать, что не определяется ни одной машиной из  M : аргумент совпадает с аргументом о том, что проблема остановки обычной машины Тьюринга  H не решается ни одной обычной машиной Тьюринга. Теперь предположим, что для противного , что H 2  является полу-решению какой - то обычной машины Тьюринга  T . Что ж, с оракулом для  H мы можем проверить,  останавливается ли T для какого-либо конкретного ввода, что противоречит тому факту, что ни одна машина в  M не принимает решение  H 2 . Итак, H 2H2MHH2THTMH2H2  не является полуразрешимым.

Остается показать , что не пол-разрешим. Во-первых, обратите внимание, что он полуопределен машиной в  M : опять же, аргумент такой же, как H  , полуопределенный обычной машиной Тьюринга. ¯ H -  не может быть пол-решению какой - то машина в  M , потому что, если он был, H 2 и  ¯ H 2 будут как бы пол-решения машин  M , поэтому оба языка будет решаться на машинах в  M . Но мы уже знаем , что H 2  не решается на любой машине в  M . Следовательно,H2¯MHH2¯MH2H2¯MMH2M  не полу решил на любой машине в M. Кроме того, ¯ Н 2 не является полу-решению любой обычной машины Тьюринга, такМ содержит каждую обычную машину Тьюринга. (Обычная машина Тьюринга - это машина Тьюринга с оракулом для Н,которая никогда не использует этот оракул.)H2¯MH2¯MH

Дэвид Ричерби
источник
7

Вот несколько естественных примеров:

  • Язык всех машин Тьюринга, останавливающийся на всех входах, иногда обозначается как TOT. Этот язык Π20 -полный.

  • Язык всех машин Тьюринга, останавливающихся на бесконечном множестве входов, иногда обозначается как INF. Этот язык также -комплектный.Π20

  • Язык всех машин Тьюринга, останавливающихся на произвольно длинных входах, иногда обозначается COF. Этот язык является -полное.Σ30

и Σ 0 3 являются уровниарифметической иерархии. Результаты полноты подразумевают, в частности, что эти языки не являются ни полуразрешимыми, ни полуразрешимыми.Π20Σ30

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