Пусть M M i , I - машина, которая имитирует работу другой машины M i на входе I и возвращает true, если M i в конечном итоге останавливается на I и в противном случае возвращается к циклу.
Пусть M ∞ - тривиальная машина, которая просто зацикливается навсегда.
Тогда (M M i , 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 не является рекурсивно перечислимым.