Informatik 2: Reduktionen & Rice's Theorem – Unentscheidbare Probleme verstehen 📚

Wir haben in der letzten Vorlesung zwar gesehen, dass es unentscheidbare Probleme gibt, unser bisheriges Beispiel ist aber akademischer Natur. In dieser Vorlesung werden wir zwei Techniken kennen lernen, um für weitere Probleme nachzuweisen, dass sie unentscheidbar sind: Reduktionsbeweise und den Satz von Rice. Der Satz von Rice charakterisiert eine Vielzahl an Problemen, die auch praktisch relevant sind, als unentscheidbar. Insbesondere für die Fragestellung der Verifikation der Korrektheit von Software stellt der Satz von Rice eine entscheidende Hürde dar.