Скажем, существуют машины Тьюринга M1, M2, M3, языки, которые они распознают, это L(M1), L(M2) и L(M3) соответственно. Следующий язык L = {(M1, M2, M3) : L(M1), L(M2) и L(M3) не равны} Является ли язык разрешимым? Рекурсивно перечислимы? Или ни то, ни другое?
Разрешимость и рекурсивная перечислимость
comment
Может быть, переехать в теоретическую информатику? Это домашнее задание?
- person Cris Stringfellow schedule 10.03.2012
comment
Разве это не проблема «эквивалентны ли два автомата»? NP-жесткий?
- person Cris Stringfellow schedule 10.03.2012
comment
Я думаю, что проблема эквивалентности машины Тьюринга гласит, что языки должны быть равны? В каком случае это неразрешимо. В этом вопросе языки не равны.
- person Glen Marek schedule 10.03.2012
Ответы (1)
Пусть MMi,I — машина, которая имитирует работу другой машины Mi на входе I и возвращает true, если Mi в конце концов останавливается на I и в противном случае зацикливается навсегда.
Пусть M∞ — тривиальная машина, которая просто бесконечно зацикливается.
Тогда (MMi,I, M∞, M∞) находится в L тогда и только тогда, когда Mi останавливается на входе I.
Это сводит разрешимость проблемы остановки к разрешимости L, поэтому L неразрешима.
=============
Далее докажем, что L не является рекурсивно перечислимым от противного.
Предположим, что L рекурсивно перечислима, поэтому существует машина Тьюринга M такая, что если Mi, Mj и Mk — три Машины, соответствующие языки которых не равны, M в конце концов выдаст тройку (Mi, Mj, Mk).
Теперь давайте рассмотрим модификацию M, называемую M', которая определяется путем взятия M и добавления значения (M, M', M') к L(M'). Важный вопрос, который нужно задать, состоит в том, находится ли (M, M', M') в L? Что ж, если (М, М', М') находится в L, то L(M) не должно быть равно L(M') (иначе это не соответствовало бы определению быть в L), поэтому L(M) не должен включать (M, M', M') (поскольку это единственная модификация, которую мы сделали). Наоборот, если (M, M', M') не находится в L, то L(M) != L(M') (потому что мы добавили этот рубец в L(M')), поэтому он должен быть в L (М), потому что языки не равны.
Таким образом, мы пришли к парадоксу, из которого следует, что M не может существовать, а значит, L не является рекурсивно перечислимым.
person
Ben Taitelbaum
schedule
10.03.2012
Ха... интересно. Можно ли сказать, что этот язык L рекурсивно перечислим?
- person Glen Marek; 10.03.2012
Я обновил ответ, чтобы решить вопрос о рекурсивном перечислении. Это была действительно забавная проблема :)
- person Ben Taitelbaum; 10.03.2012
О, ваше решение очень интересное, я многое узнаю о рекурсивной перечислимости и разрешимости. Я рад, что вам понравилось. Однако у меня есть один вопрос: если язык не является RE, не означает ли это автоматически, что он неразрешим? Или я что-то упускаю?
- person Glen Marek; 10.03.2012
да, ты прав. Технически мне нужно было только показать, что это не RE, я просто сначала не мог понять, как это сделать, и хотел убедиться, что это неразрешимо.
- person Ben Taitelbaum; 10.03.2012
Ваше доказательство, кажется, работает для аналогичного вопроса с двумя машинами Тьюринга. Интересно, почему инструктор использовал три?
- person Nemo; 10.03.2012
Хорошо, рад, что не упустил какой-то важной концепции. Я понятия не имею, почему он использовал три, я не уверен, есть ли разница.
- person Glen Marek; 11.03.2012
Я тоже все выходные думал, почему это рубец, а не пара. Мое единственное предположение состоит в том, что либо есть решение, использующее все 3, либо это просто дополнительная информация. Я надеюсь, что правильно понял, что «не равно» означает, что «не все они равны», а не «любые два из них не равны». То же основное доказательство выполняется, но вы должны изменить третий элемент, чтобы он был чем-то другим.
- person Ben Taitelbaum; 12.03.2012
Означает ли демонстрация того, что предположение приводит к парадоксу, что это предположение неверно? Если мы примем аксиомы теории множеств и воспользуемся ими, чтобы прийти к парадоксу Рассела, опровергнет ли это теорию множеств? Другими словами, мы не предполагали М, а затем показывали, что М не может существовать, мы предполагали М, а затем нашли элемент, который не принадлежит ни М, ни не М. Это показывает неполноту L(M), но I не уверен насчет рекурсивной перечислимости.
- person Ben Taitelbaum; 12.03.2012
