Berechenbarkeitstheorie

Berechenbarkeitstheorie ist ein Teilgebiet der theoretischen Informatik, das sich mit der Frage beschäftigt, welche mathematischen Probleme algorithmisch lösbar sind. Zentrale Konzepte sind Entscheidbarkeit und Berechenbarkeit: Ein Problem ist entscheidbar, wenn es für jede Eingabe in endlicher Zeit mit Ja oder Nein beantwortet werden kann; andernfalls ist es unentscheidbar. Formal wird diese Frage oft mithilfe von Modellen der Berechnung untersucht, etwa Turingmaschinen, rekursiven Funktionen oder dem Lambda-Kalkül; diese Modelle definieren die Klasse der berechenbaren Funktionen. Die Church-Turing-These besagt, dass alle intuitiv „effektiv berechenbaren“ Funktionen von denselben Modellen erfasst werden.

Wichtige Ergebnisse der Theorie betreffen die Unentscheidbarkeit. Das Halteproblem zeigt, dass es keinen allgemeinen Algorithmus gibt, der für jedes Programm und jede Eingabe entscheidet, ob das Programm terminiert. Daraus folgen zahlreiche unentscheidbare Entscheidungsprobleme in Mathematik und Informatik; mittels Reduktion auf das Halteproblem lassen sich weitere Beweise führen. Ferner spielen das Post’s Korrespondenzproblem und das Theorem von Rice eine zentrale Rolle: Rice zeigt, dass fast jede nicht-triviale Eigenschaft von Programmen unentscheidbar ist, also kaum algorithmisch zu entscheiden ist. Reduktionstypen wie many-one- oder Turing-Reduktion dienen dabei als Werkzeug.

Die Theorie trennt Berechenbarkeit von Komplexität: Eine Funktion mag zwar berechenbar sein, aber extrem ineffizient; oder andererseits gibt es unentscheidbare Probleme, bei denen kein Algorithmus existiert. Anwendungen finden sich in der formalen Spracherkennung, der Analyse algorithmischer Fragestellungen und der Untersuchung der Grenzen automatischer Beweisführung.