Berechenbarkeit #34 - Satz von Rice
Вставка
- Опубліковано 29 вер 2024
- Wir sehen uns den Satz von Rice an, welche besagt, dass jede semantische und nicht-triviale Eigenschaft von DTMs unentscheidbar ist, d.h. das folgende Problem ist unentscheidbar für jede solche Eigenschaft: Gegeben eine DTM M, hat M sie diese Eigenschaft?
Zum Beweis kann man stets vom Halteproblem oder vom Komplement des Halteproblems reduzieren.