Berechenbarkeitstheorie

Gegenstand und Bedeutung

Die Berechenbarkeitstheorie, auch Rekursionstheorie genannt, ist ein Teilgebiet der theoretischen Informatik und der mathematischen Logik. Sie untersucht, welche Probleme mithilfe einer Maschine beziehungsweise eines mathematischen Maschinenmodells lösbar sind. Dabei interessiert besonders, ob Programme und Algorithmen terminieren, also nach endlich vielen Schritten enden.

Die zentrale Frage lautet, welche Funktionen oder Mengen sich mit einem bestimmten Berechenbarkeitsmodell berechnen lassen. Dazu werden verschiedene Modelle und ihre Leistungsfähigkeit verglichen. Ein wichtiger Schwerpunkt ist die relative Berechenbarkeit: Sie fragt, welche Funktionen sich mithilfe einer bereits gegebenen Funktion in einem bestimmten Berechnungsmodell berechnen lassen, beispielsweise im Zusammenhang mit Turinggraden.

Die Abgrenzung zur Komplexitätstheorie ist unscharf. Während die Berechenbarkeitstheorie grundsätzlich nach der Lösbarkeit eines Problems fragt, untersucht die Komplexitätstheorie vor allem Berechnungsmodelle mit Ressourcenbeschränkungen.

Berechnungsmodelle und Leitfragen

Eine Hauptfrage ist, wie sich der intuitive Begriff der Berechenbarkeit mathematisch formalisieren lässt. Als weitgehend anerkannte Antwort dient die Turingmaschine. Nach der Church-Turing-These erfasst sie den intuitiven Begriff des algorithmisch Berechenbaren. Ihre Berechnungsfähigkeit ist gleichmächtig zu vielen anderen Berechnungsmodellen, das heißt, diese können grundsätzlich dieselben Funktionen berechnen.

Außerdem wird untersucht, welche Aufgaben unterschiedliche Maschinenklassen lösen können und für welche Probleme leistungsfähigere Modelle erforderlich sind. Betrachtet werden insbesondere deterministische und nichtdeterministische Varianten von endlichen Automaten, Kellerautomaten, linear beschränkten Turingmaschinen (LBA), Turingmaschinen und Registermaschinen. Deterministisch bedeutet, dass in jedem Berechnungsschritt eindeutig feststeht, wie es weitergeht; bei einem nichtdeterministischen Modell können mehrere Fortsetzungen möglich sein.

Entscheidbare und unentscheidbare Probleme

Ein Problem heißt entscheidbar, wenn es einen Algorithmus gibt, der es löst und nach endlich vielen Schritten terminiert. Neben vielen entscheidbaren Problemen sind zahlreiche unentscheidbare Probleme bekannt, für die kein solcher Algorithmus existiert.

Nach dem Satz von Rice sind alle nichttrivialen semantischen Eigenschaften von Programmen unentscheidbar. Semantische Eigenschaften betreffen dabei das Verhalten oder die Bedeutung eines Programms und nicht lediglich seine Schreibweise.

Ein Beispiel ist das Entscheidungsproblem im engeren Sinn: Zu einer Aussage der Prädikatenlogik erster Stufe soll algorithmisch festgestellt werden, ob sie wahr ist. Church und Turing wiesen unabhängig voneinander nach, dass dieses Problem nicht algorithmisch gelöst werden kann.

Ein weiteres grundlegendes Beispiel ist das Halteproblem. Gegeben sind ein Algorithmus und eine Eingabe; gefragt wird, ob der Algorithmus für diese Eingabe schließlich hält. Turing bewies, dass diese Frage unentscheidbar ist.

Gleichmächtige und schwächere Modelle

Mehrere sehr unterschiedlich aufgebaute Modelle besitzen dieselbe grundsätzliche Berechnungsfähigkeit wie eine Turingmaschine. Dazu gehören Turingmaschinen mit mehreren Bändern oder mit einem zweidimensionalen „Band“, Registermaschinen, erweiterte Kellerautomaten mit zwei Kellerspeichern, endliche Automaten mit zwei Zählern, Typ-0-Grammatiken, der Lambda-Kalkül, rekursive Funktionen, erweiterte Petri-Netze mit Sperrkanten, Markow-Algorithmen, Termersetzungssysteme und die meisten modernen Programmiersprachen.

Weniger leistungsfähige Maschinen können nur eingeschränkte Klassen formaler Sprachen erkennen. Die Chomsky-Hierarchie ordnet solche Sprachen vier Klassen von Algorithmen zu. Ausgangspunkt ist jeweils ein nichtdeterministischer endlicher Automat mit einem Speicher:

• Bei unendlich großem Speicher entspricht das Modell einer Turingmaschine.
• Ist der Speicher proportional zur Länge der Eingabezeichenkette, können kontextabhängige Sprachen erkannt werden.
• Besteht der Speicher nur aus einem Stapel, können kontextfreie Sprachen erkannt werden.
• Bei lediglich endlichem Speicher können nur Sprachen erkannt werden, die durch reguläre Ausdrücke definiert sind.

Damit zeigt die Hierarchie, wie die Art und Größe des verfügbaren Speichers bestimmt, welche Sprachklasse eine Maschine verarbeiten kann.

Quantencomputer und physikalische Berechnung

Richard Feynman stellte fest, dass klassische Computer Problemstellungen aus der Quantenmechanik nur schlecht berechnen können. In einem wichtigen Vortrag aus dem Jahr 1981 mit dem Titel „Can (quantum) physics be (efficiently) simulated by (classical) computers?“ fragte er, ob sich Quantenphysik effizient mit klassischen Computern simulieren lässt.

Da die Natur den Ausgang eines quantenmechanischen Experiments offenbar schneller „ausrechnen“ kann als ein klassischer Computer, schlug Feynman einen Quantenprozessor vor. Dessen Rechenwerk sollte quantenmechanische Prozesse nutzen, um quantenmechanische Probleme effizienter zu bearbeiten. Daraus entwickelte sich die Klasse der Quantencomputer.

Im Sinn der Berechenbarkeitstheorie sind Quantencomputer jedoch nicht mächtiger als Turingmaschinen: Beide können exakt dieselben Probleme lösen. Der mögliche Vorteil eines Quantencomputers liegt daher nicht in einer größeren Menge berechenbarer Probleme, sondern in einem eventuell erheblichen Geschwindigkeitsvorteil.