¿Es el problema que determina cada vez que el miembro de la palabra $ \ en $ L (m) decidible o no?

Question

Dada una máquina de Turing M en el alfabeto {M, E, B, R} Se nos pide que determine si Miembro $ \ en $ L (M). Debe darse cuenta de que M no es una máquina específica y puede ser una máquina de Turing con el mismo alfabeto. Mi objetivo es determinar siempre que este problema sea decidible o no.

Mi idea era usar la reducibilidad de mapeo.El objetivo era ver si podemos traducir todos los problemas de $ a_ {tm} $ que se sabe que es indecidible en nuestro problema actual.Esto haría que nuestro problema actual no sea decidible por el contagio.Sin embargo, estoy luchando en hacerlo porque no estoy seguro de si es posible. $ a_ {tm} $ se define como una máquina de Turing M que acepta la palabra w.

Se apreciaría cualquier ayuda para despegarse.

Answer 1

Lo intentaría así:

Reducción de $ a_ {tm} $ : Dado TM $ A $ und word $ W $ .

Use que para definir una nueva máquina $ A '$ que funciona de la siguiente manera:

1. Ejecute como $ a $ en la entrada $ w $
2. si $ A $ rechaza $ w $ , vaya al bucle eterno.
3. si $ a $ acepta, elimina el contenido de la banda y escribe "Miembro"