Berechenbarkeit
Heim

Berechenbarkeit

In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe reagiert. Der Definitionsbereich der Funktion ist die Menge der Eingaben, für die der Algorithmus überhaupt eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann liegt die Eingabe nicht im Definitionsbereich.

Dem Algorithmusbegriff liegt ein Berechnungsmodell zugrunde. Verschiedene Berechnungsmodelle sind entwickelt worden, es hat sich aber herausgestellt, dass die stärksten davon zum Modell der Turingmaschine gleich stark (Turing-mächtig) sind. Die Church-Turing-These behauptet daher, dass die Turingmaschinen den intuitiven Begriff der Berechenbarkeit wiedergeben.

Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, gehören zum Beispiel die Loop-Programme. Diese können zum Beispiel die Turing-berechenbare Ackermann-Funktion nicht berechnen.

Ein dem Begriff der Berechenbarkeit eng verwandter Begriff ist der der Entscheidbarkeit. Eine Teilmenge einer Menge (zum Beispiel eine Formale Sprache) heißt entscheidbar, wenn ihre charakteristische Funktion (im Wesentlichen das zugehörige Prädikat) berechenbar ist.

Inhaltsverzeichnis

Formale Definition

Man sagt, der Algorithmus P berechnet die Funktion mit , wenn P bei Eingabe von nach einer endlichen Zahl von Schritten den Wert ausgibt, und bei Eingabe von nicht terminiert.

Eine Funktion heißt berechenbar, wenn es einen Algorithmus gibt, der sie berechnet.

Den Berechenbarkeitsbegriff kann man gleichwertig auf partielle Funktionen übertragen. Eine partielle Funktion heißt berechenbar, wenn sie eingeschränkt auf ihren Definitionsbereich eine berechenbare Funktion ist.

Zahlenfunktionen

Definition berechenbarer Funktionen mit Registermaschinen

Eine Funktion ist berechenbar genau dann, wenn es eine k-stellige Registermaschine M gibt, deren Maschinenfunktion mit f übereinstimmt, also f = fM gilt.

Z.B. ist die Funktion

f(x) = div

(die für kein Argument terminiert) berechenbar, da es eine entsprechende Registermaschine gibt.

Definition mit WHILE-Programmen

Eine Funktion f (wie oben) ist berechenbar genau dann, wenn es ein WHILE-Programm P gibt, mit

.

Dabei ist EC die Eingabecodierung, AC die Ausgabecodierung und τ(P) die von P über die Semantik realisierte Maschinenfunktion.

Definition durch Rekursion

Seien μ, Sub und Prk die Operationen der µ-Rekursion, der Substitution und primitiven Rekursion. Funktionen, die sich aus der Menge der primitiv-rekursiven Grundfunktionen durch wiederholtes Anwenden dieser Operatoren erzeugen lassen, heißen µ-rekursiv. Die Menge der μ-rekursiven Funktionen ist genau die Menge der berechenbaren Funktionen.

Übergang von einstelligen zu mehrstelligen Funktionen

Über die cantorsche Paarungsfunktion führt man den Begriff der Berechenbarkeit einer k-stelligen Funktion auf den der Berechenbarkeit von einstelligen Funktionen zurück. Insbesondere kann man damit in natürlicher Weise definieren, welche Funktionen auf den rationalen Zahlen berechenbar sind.

Wortfunktionen

Die Berechenbarkeit von Wortfunktionen lässt sich entweder mit Hilfe von Turingmaschinen oder Bandmaschinen zeigen. Alternativ führt man eine Standardnummerierung über die Wörter über Σ * ein und zeigt, dass die so erzeugten Zahlenfunktionen berechenbar sind.

Spezielle Probleme

Eine Kuriosität ist, dass ein spezielles, also ein Problem mit nur einer Instanz, immer berechenbar ist. Man könnte auch sagen, dass es für jede Funktion die keine Parameter hat, einen Algorithmus gibt, der diese Funktion berechnet. Das klingt verwirrend, ist aber trivial. Angenommen, die Frage lautet "gibt es Gott", und die Definition von "Gott" sei in irgendeiner Form vorgegeben. Diese Frage repräsentieren wir durch die (parameterlose) Funktion g(). Die Antwort muss nun entweder ja oder nein lauten – und für beide Antworten lässt sich leicht ein Algorithmus konstruieren, der die korrekte Antwort ausgibt. Es gibt also immer einen solchen Algorithmus, wir wissen nur nicht, welcher es ist.

Würden wir das gleiche Problem allgemein stellen, so dass die Definition von Gott (nennen wir sie d) als Eingabe des Algorithmus verlangt ist (also ein Parameter der Funktion g wäre), so wäre die resultierende Aussage g(d) nicht unbedingt berechenbar. Das gleiche gilt natürlich auch für Fragestellungen aus weniger metaphysischen Bereichen.

Eigenschaften

Siehe auch