Berechenbarkeit

Unter Berechenbarkeit versteht man in der Berechenbarkeitstheorie eine Eigenschaft einer Funktion, mittels einer abstrakten und mechanischen Vorgehensweise zu gegebenen Eingaben ihre Ausgabe zu berechnen.

Die Vorgehensweise wird als Algorithmus bezeichnet und muss exakt definiert sein, da davon abhängt, welche Funktionen berechenbar sind und welche nicht. Es gibt eine ganze Reihe von Algorithmusbegriffen, die gleichmächtig sind und für die bisher noch keine sinnvolle Erweiterung im Sinne des Berechenbarkeitsbegriffs gefunden werden konnte. Ein Beispiel dafür ist die Turingmaschine. Die Church-Turing-These erklärt diese zu einem rechnenden Menschen gleichwertig.

Es gibt auch schwächere Algorithmusbegriffe als Turingmaschinen. Dazu gehören zum Beispiel die Loop-Programme. Diese können zum Beispiel die turing-berechenbare Ackermann-Funktion nicht berechnen.

Berechenbarkeit ist nicht mit Entscheidbarkeit zu verwechseln. Bei der Entscheidbarkeit ist gefragt, ob es zu einer Funktion einen Algorithmus gibt, der stets nach endlicher Bearbeitungszeit die Ausgabe der Funktion liefert. Bei einer partiellen Funktion können Ausgabewerte zu bestimmten Eingaben auch nicht definiert sein (vergleiche div-Funktion weiter unten). Der Algorithmus terminiert in solchen Fällen nicht. Dennoch ist die Funktion berechenbar, da das unendliche Weiterrechnen des Algorithmus einer nicht definierten Funktionsausgabe entspricht. Das Halteproblem zum Beispiel, ist daher zwar nicht entscheidbar, aber durchaus berechenbar.

Formale Definition

Eine Funktion $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ heißt berechenbar, wenn es einen Algorithmus gibt, der bei Eingabe von $\left(n_{1},...,n_{k}\right)\in \mathbb {N} ^{k}$ nach endlicher Zahl von Schritten $f\left(n_{1},...,n_{k}\right)$ berechnet, sofern $f\left(n_{1},...,n_{k}\right)$ definiert ist und andernfalls nicht terminiert.

Zahlenfunktionen

Definition berechenbarer Funktionen mit Registermaschinen

Eine Funktion $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ ist berechenbar genau dann, wenn es eine k-stellige Registermaschine $M$ gibt, deren Maschinenfunktion mit $f$ übereinstimmt, also $f=f_{M}$ gilt.

Z.B. ist die Funktion

f(x)={\mbox{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

f=AC\circ \tau (P)\circ EC

.

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

Definition durch Rekursion

Seien $\mu$ , Sub und Prk die Operationen der $\mu$ -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 $\mu$ -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 $\Sigma ^{*}$ ein und zeigt, dass die so erzeugten Zahlenfunktionen berechenbar sind.

Zudem lassen sich geeignete Wörter definieren, die eine schnell konvergierende Approximation von reellen Zahlen darstellen. Über solche Wörter lässt sich der Berechenbarkeitsbegriff auf die Menge der reellen Zahlen ergänzen.

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 berechenbar. Das gleiche gilt natürlich auch für Fragestellungen aus weniger esoterischen Bereichen.

Siehe auch