Grundlagen der Informatik 2, Vorlesung 19: Grenzen der Berechenbarkeit

Unsere Überlegungen zur Algorithmik und Datenstrukturen in den letzten Vorlesungen könnten zu der vorschnellen Annahme verleiten, dass die Algorithmik, so man denn nur clever genug ist, für jedes Problem eine Lösung anzubieten hätte. Wie falsch man mit dieser Annahme läge, werden wir in dieser Vorlesung beginnen zu erarbeiten: Wir werden anhand eines ersten Beispiels sehen, dass es sehr wohl Probleme gibt, die ganz grundsätzlich nicht algorithmisch allgemein gelöst werden können. Damit legen wir die Grundlage, um in der nachfolgenden Vorlesung Techniken zu erarbeiten, um nachzuweisen, dass ein Problem unentscheidbar ist.