L = {<T> | T ist eine Turingmaschine, die {00, 01}} erkennt.
Beweisen Sie, dass L unentscheidbar ist.
Ich habe wirklich Schwierigkeiten, die Reduktion hier zu verstehen.
Ich frage nicht nach einem kostenlosen Mittagessen, sondern nur in die richtige Richtung.
Antworten:
0 für die Antwort № 1Eine direkte Anwendung des Satzes von Rice lässt Sie dies beweisen, ohne irgendwelche Arbeit zu tun.
Einige Turingmaschinen erkennen {00, 01}. Einige nicht. Der Unterschied ist insofern semantisch, als er mit den akzeptierten Strings und nicht mit der Struktur des Automaten zusammenhängt. Daher ist diese Menge nach dem Satz von Rice unentscheidbar.