Berechenbarkeit #34 - Satz von Rice

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. ----------------------- ► Paypal-Link für Spenden: http://paypal.me/Leifaktor ► Liberapay: https://de.liberapay.com/NLogSpace/ ► Patreon: http://www.patreon.com/Leifaktor