È il problema che determina ogni volta che il membro del genere $ \ in $ L (m) decidabile o no?

Question

Dato una macchina di tinger m su alfabeto {m, e, b, r} Avremo chiesto di determinare se il membro $ \ in $ l (m). Devi rendermi conto che M non è una macchina specifica e può essere una macchina di Turing con lo stesso alfabeto. Il mio obiettivo è determinare ogni volta che questo problema è decidabile o meno.

La mia idea era usare la riducibilità della mappatura.L'obiettivo era vedere se possiamo tradurre tutti i problemi da $ A_ {TM} $ che è noto per essere indecidabile nel nostro problema corrente.Ciò renderebbe il nostro problema attuale indecidabile per contagio.Comunque sto lottando nel farlo perché non sono sicuro che sia possibile. $ A_ {TM} $ è definito come una macchina MACCHINA M che accetta la parola w.

Qualsiasi aiuto per essere scollato sarebbe apprezzato.

Answer 1

Lo proverei in questo modo:

Riduzione da $ A_ {TM} $ : Dato TM $ a $ und $ W $ .

Utilizzare quello per definire una nuova macchina $ a '$ funziona come segue:

.
1. Esegui come $ a $ su input $ w $
2. se $ A $ rifiuta $ W $ , vai in eternal loop.
3. se $ a $ accetta, elimina il contenuto della banda e scrivi "Membro"