imported>Luckywiki1234: Änderung 255469015 von 2003:C3:670D:CA00:D96A:CD15:37AD:380D rückgängig gemacht;

2025-04-25T20:33:48Z

Änderung 255469015 von 2003:C3:670D:CA00:D96A:CD15:37AD:380D rückgängig gemacht;

Neue Seite

Eine [[Funktion (Mathematik)|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 (Computer)|Ausgabe]], mit der der Algorithmus auf eine [[Eingabe (Computer)|Eingabe]] reagiert. Der [[Definitionsmenge|Definitionsbereich]] der Funktion ist die Menge der Eingaben, für die der Algorithmus eine Ausgabe produziert. Wenn der Algorithmus nicht [[Terminiertheit|terminiert]], dann ist die Eingabe kein [[Element (Mathematik)|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 [[Zweikellerautomat]]en, [[WHILE-Programm]]e, [[Μ-Rekursion|μ-rekursive Funktionen]], [[Registermaschine]]n und der [[Lambda-Kalkül]].

Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, gehören zum Beispiel die [[LOOP-Programm]]e. Diese können zum Beispiel die Turing-berechenbare [[Ackermannfunktion]] nicht berechnen.

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

== Formale Definition ==
Angenommen wird: der Algorithmus <math>P</math> ''berechnet'' die Funktion <math>f \colon T\rightarrow \mathbb{N}</math> mit <math>T\subseteq\mathbb{N}^k</math>, wenn <math>P</math> bei Eingabe von <math>\left( n_1, \ldots, n_k \right) \in T</math> nach einer endlichen Zahl von Schritten den Wert <math>f \left( n_1, \ldots, n_k \right)</math> ausgibt
und bei Eingabe von <math>\left( n_1, \ldots, n_k \right) \in \mathbb{N}^k \setminus T</math> nicht [[Terminiertheit|terminiert]].

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

Den Berechenbarkeitsbegriff kann man gleichwertig auf [[partielle Funktion]]en übertragen. Eine partielle Funktion <math>f\colon\mathbb{N}^k \rightsquigarrow \mathbb{N}</math> heißt berechenbar, wenn sie eingeschränkt auf ihren [[Definitionsbereich]] <math>f\colon\operatorname{Def}(f) \to \mathbb{N}</math> eine berechenbare Funktion ist.

=== Zahlenfunktionen ===
In der Berechenbarkeitstheorie werden meist nur Funktionen [[Natürliche Zahl|natürlicher Zahlen]] betrachtet.

==== Definition berechenbarer Funktionen mit Registermaschinen ====
Eine Funktion
<math>f \colon \mathbb{N}^k \rightarrow \mathbb{N}</math>
ist berechenbar genau dann, wenn es eine <math>k</math>-stellige [[Registermaschine]]
<math>M</math>
gibt, deren [[Maschinenfunktion]] mit
<math>f</math>
übereinstimmt, also
<math>f = f_M</math>
gilt.

Z. B. ist die Funktion
:<math>f(x) = \mbox{div}</math>
(die für kein Argument terminiert) berechenbar, da es eine entsprechende Registermaschine gibt.

==== Definition mit WHILE-Programmen ====
Eine Funktion <math>f</math> (wie oben) ist berechenbar genau dann, wenn es ein [[WHILE-Programm]] <math>P</math> gibt mit
:<math> f = AC \circ \tau(P) \circ EC</math>.

Dabei ist <math>EC</math> die Eingabecodierung, <math>AC</math> die Ausgabecodierung und <math>\tau(P)</math> die von <math>P</math> über die [[Semantik]] realisierte Maschinenfunktion.

==== Definition durch Rekursion ====
Seien <math>\mu</math>, Sub und Prk die Operationen der [[µ-Rekursion]], der Substitution und [[Primitive Rekursion|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 <math>\mu</math>-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 [[Rationale Zahl|rationalen Zahlen]] berechenbar sind.

=== Wortfunktionen ===
Die Berechenbarkeit von Wortfunktionen lässt sich etwa mit Hilfe von [[Turingmaschine]]n zeigen. Alternativ führt man eine [[Standardnummerierung]] über die Wörter über <math>\Sigma^*</math> 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) ''Ta'', 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 ''Ta'' 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 (Mathematik)|Komposition]] von berechenbaren Funktionen ist berechenbar.
* Der [[Definitionsbereich]] einer berechenbaren Funktion ist [[Rekursive Aufzählbarkeit|rekursiv aufzählbar]] (siehe [[Projektionssatz (Informatik)|Projektionssatz]]).
* Der [[Bild (Mathematik)|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.
* {{Literatur | Autor= [[Hartley Rogers]], Jr.| Titel= Theory of recursive functions and effective computability| Verlag= McGraw-Hill| Jahr=1967| ISBN= 9780262680523 }}
* 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 ==
{{Wiktionary}}
* {{SEP|https://plato.stanford.edu/entries/computability/}}

[[Kategorie:Berechenbarkeitstheorie]]

Berechenbarkeit - Versionsgeschichte

imported>Luckywiki1234: Änderung 255469015 von 2003:C3:670D:CA00:D96A:CD15:37AD:380D rückgängig gemacht;