¿Es este idioma decidible?

Question

como dice el título; ¿Es este idioma decidible y cómo lo demuestras?

$$ l={\ langose M \ rangle \ Mid M \ Text {es una máquina de Turing y hay una entrada que} M \ Text {Halts ON} \}$$

Answer 1

Tu idioma no es decidible. Para demostrar que es suficiente notar que la existencia de una máquina de Turing $ t $ que decidió $ l $ implica la existencia de una máquina de Turing que resuelve el problema de detención.

De hecho, dada cualquier máquina de Turing $ m $ con entrada $ x $ puede construir un turing máquina $ m '$ que ignora su entrada, escribe $ x $ en la cinta, y luego simula < Span Class="Math-contenedor"> $ M $ . Claramente $ m '$ detiene (independientemente de su entrada) si y solo si $ m $ se detiene en la entrada $ x $ . Podemos decidir si $ m '$ se detiene marcando si $ m' \ en l $ usando $ t $ con entrada $ m '$ .