Почему рекурсивно перечислимые языки неразрешимы

Question

Это определение разрешимо из Википедии

В теории вычислимости неразрешимая проблема состоит из семейства примеров, для которых требуется конкретный ответ «да / нет», такой, что нет компьютераПрограмма, которая, учитывая любой экземпляр проблемы в качестве входных данных, завершает и выводит требуемый ответ после конечного числа шагов.Более формально неразрешимая проблема - это проблема, язык которой не является рекурсивным набором

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

Answer 1

Рекурсивно перечислимые языки / наборы также известны как полуразрешимые. Они не разрешимы, потому что нет машины, которая смотрит на ввод и говорит да или нет (правильно). Полуразрешимый означает, что вы можете написать машину, которая смотрит на вход и говорит «да», если вход находится в наборе, или не может остановиться, если вход не находится в наборе. Полуразрешаемое оказывается эквивалентным рекурсивно перечислимому точно так же, как decidable эквивалентно рекурсивному : -

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

И наоборот, если у вас есть машина Тьюринга D, которая отвечает да или не может остановиться, вы можете создать новую машину R, которая использует обычную технику для параллельного запуска нескольких экземпляров D с различными входами: все элементы, которые могут или не могут быть в наборе. Каждый раз, когда одно из параллельных выполнений D останавливается с ответом «да», R выводит этот ввод D и продолжает выполнять D на всех оставшихся входах. R никогда не остановится (потому что есть некоторые входы, на которых D не остановится), но в конечном итоге он выведет каждый элемент, для которого D ответил «да», то есть каждый элемент в наборе / языке.

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

Answer 2

Полуразрешимая проблема (или эквивалентно рекурсивно перечислимая проблема) может быть:

1. Разрешаемая : если задача и ее дополнение являются полуразрешимыми (или рекурсивно перечислимыми)), то проблема разрешима (рекурсивна).

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

Важное примечание: Помните, что разрешимая (рекурсивная) задача также является полурешаемой (рекурсивно перечислимой).И наоборот, если проблема не является рекурсивно-перечислимой (полуразрешимой), то она не является рекурсивной (разрешимой).

В записи в Википедии говорится, что:

Частично разрешимые проблемы ТО, ЧТО НЕ ПОСТАНОВЛЯЕМЫЕ называются неразрешимыми.

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

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

Answer 3

Я считаю, что графическое представление наборов задач могло бы быть более полезным здесь (размер различных наборов здесь не имеет значения).

Подведем итог:

1. Каждая разрешимая (рекурсивная) задача также является полуразрешимой (рекурсивно перечислимой).
2. Каждая неразрешимая (рекурсивно-перечислимая) задача, которая не разрешима (рекурсивно), неразрешима.
3. Существуют неразрешимые проблемы, которые не являются полуразрешимыми (рекурсивно перечисляемыми).