Berechenbarkeit

Eine mathematische Funktion ist berechenbar (auch effektiv berechenbar oder rekursiv), wenn für sie eine Berechnungsanweisung (Algorithmus) formuliert werden kann (Berechenbarkeitstheorie). 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 eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann ist die Eingabe kein Element der Definitionsmenge.

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. In der Berechenbarkeitstheorie heißen genau die Funktionen berechenbar, die Turing-berechenbar sind.

Zu den Turing-mächtigen Berechnungsmodellen gehören neben der Turingmaschine beispielsweise Zweikellerautomaten, WHILE-Programme, μ-rekursive Funktionen, Registermaschinen und der Lambda-Kalkül.

Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, gehören zum Beispiel die LOOP-Programme. Diese können zum Beispiel die Turing-berechenbare Ackermannfunktion 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.

Formale Definition

Angenommen wird: der Algorithmus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} berechnet die Funktion Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \colon T\rightarrow \mathbb{N}} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T\subseteq\mathbb{N}^k} , wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} bei Eingabe von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left( n_1, \ldots, n_k \right) \in T} nach einer endlichen Zahl von Schritten den Wert Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \left( n_1, \ldots, n_k \right)} ausgibt und bei Eingabe von $\left(n_{1},\ldots ,n_{k}\right)\in \mathbb {N} ^{k}\setminus T$ 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\colon\mathbb{N}^k \rightsquigarrow \mathbb{N}} heißt berechenbar, wenn sie eingeschränkt auf ihren Definitionsbereich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f\colon\operatorname{Def}(f) \to \mathbb{N}} eine berechenbare Funktion ist.

Zahlenfunktionen

In der Berechenbarkeitstheorie werden meist nur Funktionen natürlicher Zahlen betrachtet.

Definition berechenbarer Funktionen mit Registermaschinen

Eine Funktion Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle f\colon \mathbb {N} ^{k}\rightarrow \mathbb {N} } ist berechenbar genau dann, wenn es eine $k$-stellige Registermaschine $M$ gibt, deren Maschinenfunktion mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} übereinstimmt, also Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = f_M} gilt.

Z. B. ist die Funktion

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} gibt mit

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = AC \circ \tau(P) \circ EC} .

Dabei ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle EC} die Eingabecodierung, Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle AC} die Ausgabecodierung und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \tau(P)} die von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle P} über die Semantik realisierte Maschinenfunktion.

Definition durch Rekursion

Seien Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu} , 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mu} -rekursiven Funktionen ist genau die Menge der berechenbaren Funktionen.

Übergang von einstelligen zu mehrstelligen Funktionen

Über die cantorsche Paarungsfunktion wird der Begriff der Berechenbarkeit einer k-stelligen Funktion auf den der Berechenbarkeit von einstelligen Funktionen zurückgeführt. Insbesondere wird damit in natürlicher Weise definiert ob Funktionen von rationalen Zahlen berechenbar sind.

Wortfunktionen

Die Berechenbarkeit von Wortfunktionen lässt sich etwa mit Hilfe von Turingmaschinen zeigen. Alternativ führt man eine Standardnummerierung über die Wörter über Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Sigma^*} ein und zeigt, dass die so erzeugten Zahlenfunktionen berechenbar sind.

Uniforme Berechenbarkeit

Eine zweistellige Funktion f(x,y) mit der Eigenschaft, dass für jeden festen Wert a die durch f_a(y) = f(a,y) definierte einstellige Funktion f_a berechenbar ist, muss selbst nicht unbedingt berechenbar sein; für jeden Wert a gibt es zwar einen Algorithmus (also etwa ein Programm für eine Turingmaschine) T_a, der f_a berechnet, aber die Abbildung a → T_a ist im Allgemeinen nicht berechenbar.

Eine Familie (f_a: a=0, 1, 2, …) von berechenbaren Funktionen heißt uniform berechenbar, wenn es einen Algorithmus gibt, der zu jedem a einen Algorithmus T_a liefert, welcher f_a berechnet. Man kann leicht zeigen, dass so eine Familie genau dann uniform berechenbar ist, wenn die zweistellige Funktion (x, y) → f_x(y) berechenbar ist.

Eigenschaften

• Die Komposition von berechenbaren Funktionen ist berechenbar.
• Der Definitionsbereich einer berechenbaren Funktion ist rekursiv aufzählbar (siehe Projektionssatz).
• Der Wertebereich einer berechenbaren Funktion ist rekursiv aufzählbar.
• Die universelle Funktion nimmt ihren ersten Parameter als Gödelnummer eines Algorithmus und wendet diesen Algorithmus an auf ihren zweiten Parameter. Die universelle Funktion ist berechenbar zum Beispiel durch eine universelle Turingmaschine.

Siehe auch

• Halteproblem
• Gödelscher Unvollständigkeitssatz
• Semi-entscheidbare Menge
• Berechenbare Folge
• Berechenbare Zahl

Literatur

• S. B. Cooper: Computability Theory. Chapman & Hall/CRC, 2004, ISBN 1-58488-237-9.
• Nigel Cutland: Computability, An introduction to recursive function theory. Cambridge University Press, 1980, ISBN 0-521-29465-7.
• Hans Hermes: Aufzählbarkeit – Entscheidbarkeit – Berechenbarkeit. Einführung in die Theorie der rekursiven Funktionen. Berlin – Göttingen – Heidelberg 1961, 2. Auflage. 1971 (als Heidelberger Taschenbuch).
• Stephen Kleene: Introduction to Metamathematics. North-Holland, 1952, ISBN 0-7204-2103-9.
• Piergiorgio Odifreddi: Classical Recursion Theory. North-Holland, 1989, ISBN 0-444-87295-7.
• Hartley Rogers, Jr.: Theory of recursive functions and effective computability. McGraw-Hill, 1967, ISBN 978-0-262-68052-3. 
• Dieter Rödding: Registermaschinen. In: Der Mathematikunterricht. Heft 18, 1972, ISSN 0025-5807, S. 32–41.
• J.C. Shepherdson, H.E. Sturgis: Computability of Recursive Functions. Journal of the ACM, Band 10, Heft 2, April 1963, ISSN 0004-5411, S. 217–255.

Weblinks

WiktionaryWiktionary: Berechenbarkeit – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen

• Eintrag in Edward N. Zalta (Hrsg.): Stanford Encyclopedia of Philosophy.Vorlage:SEP/Wartung/Parameter 1 und weder Parameter 2 noch Parameter 3