Berechenbarkeit #34: Der Satz von Rice – Unentscheidbarkeit semantischer Eigenschaften von DTMs 🤖

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.