Berechenbarkeit

aus Wikipedia, der freien Enzyklopädie

Wechseln zu: Navigation, Suche

Unter Berechenbarkeit einer Funktion versteht man in der Berechenbarkeitstheorie die Existenz einer eindeutig definierten Vorgehensweise, mit der zu jeder beliebigen Eingabe die Ausgabe der Funktion berechnet werden kann.

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. Elementare Beispiele dafür sind der Lambda-Kalkül und 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.

Ein dem Begriff der Berechenbarkeit eng verwandter Begriff ist der der Entscheidbarkeit, welcher eingefuehrt wurde um die "Berechenbarkeit" von Mengen (d. h. von Sprachen) anzugeben, die dann aber eben nicht "Berechenbarkeit" sondern "Entscheidbarkeit" genannt wird. (Dabei heißt eine Menge entscheidbar genau dann, wenn ihre charakteristische Funktion - welche immer eine totale Funktion ist - berechenbar ist).

Inhaltsverzeichnis

[Bearbeiten] Formale Definition

Eine Funktion f : T\rightarrow \mathbb{N} mit T\subseteq\mathbb{N}^k 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.

[Bearbeiten] Zahlenfunktionen

[Bearbeiten] 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 = fM gilt.

Z.B. ist die Funktion

f(x) = div

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

[Bearbeiten] 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 τ(P) die von P über die Semantik realisierte Maschinenfunktion.

[Bearbeiten] 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.

[Bearbeiten] Ü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.

[Bearbeiten] 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.

[Bearbeiten] 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.

[Bearbeiten] Siehe auch

Von „http://de.wikipedia.org/wiki/Berechenbarkeit“
Persönliche Werkzeuge