Разрешимость и рекурсивная перечислимость

Question

Скажем, существуют машины Тьюринга M1, M2, M3, которые они распознают как L (M1), L (M2) и L (M3) соответственно. Следующий язык L = {(M1, M2, M3): L(M1), L(M2) и L (M3) не равны} Является ли язык разрешимым? Рекурсивно перечислимый? Или нет?

Answer 1

Пусть M_{Mi, я} машина, которая на входе имитирует работу другой машины M_i I и возвращается true если M_{я в} конце концов останавливается на Iи петли навсегда в противном случае.

Пусть M_∞ - тривиальная машина, которая просто зацикливается навсегда.

Тогда (M_{Mi, I}, M_∞, M_∞) находится в L, если M_i останавливается на входе I,

Это снижает разрешимость проблемы остановки до разрешимости L, поэтому L неразрешима.

=============

Далее докажем, что L не является рекурсивно перечислимым по противоречию.

Предположим, что L рекурсивно перечислимо, поэтому существует машина Тьюринга M, такая, что если M_i, M_j и M_k - три машины Тьюринга, соответствующие языки которых не равны, то M в конечном итоге выплюнет тройку (M_i, M_j, M_k).

Теперь давайте рассмотрим модификацию M, называемую M ', которая определяется путем взятия M и добавления значения (M, M', M ') к L(M'). Важный вопрос, который нужно задать: если (M, M ', M') находится в L? Хорошо, если (M, M ', M') находится в L, то L (M) не должно быть равным L (M ') (в противном случае это не соответствует определению в L), поэтому L (M) не должен включать (M, M ', M') (так как это единственная модификация, которую мы сделали). И наоборот, если (M, M ', M') не находится в L, то L(M)!= L(M') (потому что мы добавили этот трип к L (M')), поэтому он должен быть в L (M), потому что языки не равны.

Таким образом, мы достигли парадокса, который подразумевает, что M не может существовать, и, следовательно, L не является рекурсивно перечислимым.