Reis-Satz für Turing-Maschine mit fester Ausgabe
-
29-09-2020 - |
Frage
Also sollte ich mit Hilfe von Rice's Theorem beweisen, ob die Sprache:
Zunächst einmal: Ich verstehe nicht, warum wir Rice's Theorem an erster Stelle nutzen können: Wenn ich zwei Turniermacher wählen würde $ m_ {w} $ und $ m_ {w '} $ mit $ w \ neq w' $ dann würde ich $ m_ {w} (w)= m_ {w '} (w)= x $ . Dies würde jedoch dazu führen, dass $ W '$ nicht in $ l_ {5} $ und $ w \ in l_ {5} $ . Oder bin ich falsch verständlich?
Sekunden: Die Lösung sagt, dass die Sprache $ l_ {5} $ als $ l_ {5} entschieden wird=\ emptyet $ , da der Ausgang mit einem festen Eingang eindeutig bestimmt wird.
Aber warum ist das so? Ich dachte, dass
Lösung
ein word $ W $ gehört zu $ l_5 $ wenn für alle $ x \ in \ {0,1 \} ^ * $ Es ist der Fall, dass $ m_w (w)= x $ .Wenn insbesondere $ w \ in l_5 $ dann $ m_w (w)= 0 $ und