Cómo demostrar que EQTM = {: L (M1) = L (M2)} es indecidible (suponga que M1 y M2 son codificaciones de TM)

Lo primero que pienso es que si la equivalencia de TMs fuera decidible en general, también lo sería la equivalencia a una TM divergente. La TM divergente tiene un lenguaje vacío y, por lo tanto, podemos usar el verificador de equivalencia para averiguar si alguna máquina de Turing tiene el idioma vacío (estos son mis primeros pensamientos porque la equivalencia con TM divergentes suena como un problema de detención, lo que recuerdo es indecidible). , los TM dirvergentes tienen el lenguaje vacío, al igual que las máquinas de terminación que siempre rechazan, por lo que no es el problema de detención; pero intuitivamente, va en la dirección correcta).

Entonces, si podemos descubrir que no es posible verificar si alguna máquina de Turing tiene el idioma vacío, también sabemos que la equivalencia no es decidible.

Ahora, ¿por qué no sería posible verificar que cualquier máquina de turing tenga el idioma vacío? Creo que podría tener sentido codificar el problema de detención de alguna manera.

Mi primera idea sería crear una máquina [math] Halt_X [/ math] para cada máquina de turing [math] X [/ math], que acepta iff [math] X [/ math] termina en la entrada [math] \ langle X \ rangle [/ math]. Esto no suena tan difícil; simplemente use la máquina universal de turing [matemática] U [/ matemática] y un prefijo finito de estados que coloca [matemática] \ langle X \ rangle \ # \ langle X \ rangle [/ math] en la cinta utilizada por [math] U [/ math], pero haga de cada estado un estado de aceptación. Esta máquina acepta todo, es decir, si la máquina termina, que es cuando [math] X [/ math] termina en la entrada [math] \ langle X \ rangle [/ math], o no acepta nada, es decir, si la máquina no terminar, que es cuando [math] X [/ math] no termina en la entrada [math] \ langle X \ rangle [/ math].

Como consecuencia, si sabemos si [math] Halt_X [/ math] acepta palabras o no, sabemos si [math] X [/ math] termina en la entrada [math] \ langle X \ rangle [/ math].

Por lo tanto, decidir para todas [matemáticas] X [/ matemáticas] si [matemáticas] Halt_X [/ matemáticas] acepta palabras o no, es lo mismo que decidir para todas las máquinas de Turing [matemáticas] X [/ matemáticas] si termina en la entrada [ matemáticas] \ langle X \ rangle [/ matemáticas] o no, y este es exactamente el problema de detención.

Sabemos que el problema de detención es indecidible, por lo que también es indecidible (para [math] X [/ math] general) si machine [math] Halt_X [/ math] acepta palabras o no; por lo tanto, no podemos tener una máquina que decida en general si una máquina acepta palabras o no; y dado que una máquina que prueba la equivalencia puede usarse para hacer eso, no puede haber una máquina que pruebe la equivalencia.