Ist das Problem, das bestimmt, wann immer das Wort-Mitglied $ \ in $ l (m) entgreift oder nicht?

Question

Angesichts einer Turingmaschine M auf Alphabet {m, e, b, r} werden gebeten, festzustellen, ob das Mitglied $ \ in $ l (m) ist. Sie müssen erkennen, dass M nicht eine bestimmte Maschine ist und eine beliebige Turing-Maschine mit demselben Alphabet sein kann. Mein Ziel ist es, wann immer dieses Problem entschieden ist oder nicht.

Meine Idee bestand darin, Kartierungsmonizilität zu verwenden.Ziel war es zu sehen, ob wir alle Probleme von $ A_ {TM} $ übersetzen können, das bekannt ist, dass er unbeeintrahmt in unser aktuelles Problem ist.Dies würde unser aktuelles Problem durch Ansteckung unentscheidbar machen.Ich kämpfe jedoch dabei, weil ich nicht sicher bin, ob es möglich ist. $ A_ {TM} $ ist definiert als Turing-Maschine M, die das Wort akzeptiert.

Jede Hilfe, um loszuwerden, würde geschätzt werden.

Answer 1

Ich würde es so ausprobieren:

Reduktion von $ A_ {TM} $ : gegeben tm $ A $ und word $ W $ .

Verwenden Sie diese Verwendung, um eine neue Maschine zu definieren $ A '$ , die wie folgt funktioniert:

.
1. läuft wie $ A $ bei input $ W $
2. Wenn $ A $ ablehnt $ W $ , gehen Sie in die ewige Schleife.
3. Wenn $ A $ akzeptiert, löschen Sie den Bandinhalt und schreiben Sie "Mitglied"