www.wikidata.de-de.nina.az

Berechenbarkeit Eine mathematische Funktion ist berechenbar auch effektiv berechenbar oder rekursiv wenn für sie eine Be

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 Bearbeiten

Angenommen wird: der Algorithmus berechnet die Funktion mit , wenn 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 Bearbeiten

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

Definition berechenbarer Funktionen mit Registermaschinen Bearbeiten

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

Z. B. ist die Funktion

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

Definition mit WHILE-Programmen Bearbeiten

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

Dabei ist die Eingabecodierung, die Ausgabecodierung und die von über die Semantik realisierte Maschinenfunktion.

Definition durch Rekursion Bearbeiten

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 Bearbeiten

Ü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 Bearbeiten

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

Uniforme Berechenbarkeit Bearbeiten

Eine zweistellige Funktion f(x,y) mit der Eigenschaft, dass für jeden festen Wert a die durch fa(y) = f(a,y) definierte einstellige Funktion fa 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 fa berechnet, aber die Abbildung a → Ta ist im Allgemeinen nicht berechenbar.

Eine Familie (fa: 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 fa berechnet. Man kann leicht zeigen, dass so eine Familie genau dann uniform berechenbar ist, wenn die zweistellige Funktion (x, y) → fx(y) berechenbar ist.

Eigenschaften Bearbeiten

Siehe auch Bearbeiten

Literatur Bearbeiten

  • 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 Bearbeiten

Wiktionary: Berechenbarkeit – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine mathematische Funktion ist berechenbar auch effektiv berechenbar oder rekursiv wenn fur 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 fur 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 starksten davon zum Modell der Turingmaschine gleich stark Turing machtig sind Die Church Turing These behauptet daher dass die Turingmaschinen den intuitiven Begriff der Berechenbarkeit wiedergeben In der Berechenbarkeitstheorie heissen genau die Funktionen berechenbar die Turing berechenbar sind Zu den Turing machtigen Berechnungsmodellen gehoren neben der Turingmaschine beispielsweise Zweikellerautomaten WHILE Programme m rekursive Funktionen Registermaschinen und der Lambda Kalkul Zu den Berechnungsmodellen die schwacher sind als Turingmaschinen gehoren zum Beispiel die LOOP Programme Diese konnen 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 heisst entscheidbar wenn ihre charakteristische Funktion im Wesentlichen das zugehorige Pradikat berechenbar ist Inhaltsverzeichnis 1 Formale Definition 1 1 Zahlenfunktionen 1 1 1 Definition berechenbarer Funktionen mit Registermaschinen 1 1 2 Definition mit WHILE Programmen 1 1 3 Definition durch Rekursion 1 1 4 Ubergang von einstelligen zu mehrstelligen Funktionen 1 2 Wortfunktionen 2 Uniforme Berechenbarkeit 3 Eigenschaften 4 Siehe auch 5 Literatur 6 WeblinksFormale Definition BearbeitenAngenommen wird der Algorithmus P displaystyle P nbsp berechnet die Funktion f T N displaystyle f colon T rightarrow mathbb N nbsp mit T N k displaystyle T subseteq mathbb N k nbsp wenn P displaystyle P nbsp bei Eingabe von n 1 n k T displaystyle left n 1 ldots n k right in T nbsp nach einer endlichen Zahl von Schritten den Wert f n 1 n k displaystyle f left n 1 ldots n k right nbsp ausgibt und bei Eingabe von n 1 n k N k T displaystyle left n 1 ldots n k right in mathbb N k setminus T nbsp nicht terminiert Eine Funktion heisst berechenbar wenn es einen Algorithmus gibt der sie berechnet Den Berechenbarkeitsbegriff kann man gleichwertig auf partielle Funktionen ubertragen Eine partielle Funktion f N k N displaystyle f colon mathbb N k rightsquigarrow mathbb N nbsp heisst berechenbar wenn sie eingeschrankt auf ihren Definitionsbereich f Def f N displaystyle f colon operatorname Def f to mathbb N nbsp eine berechenbare Funktion ist Zahlenfunktionen Bearbeiten In der Berechenbarkeitstheorie werden meist nur Funktionen naturlicher Zahlen betrachtet Definition berechenbarer Funktionen mit Registermaschinen Bearbeiten Eine Funktion f N k N displaystyle f colon mathbb N k rightarrow mathbb N nbsp ist berechenbar genau dann wenn es eine k displaystyle k nbsp stellige Registermaschine M displaystyle M nbsp gibt deren Maschinenfunktion mit f displaystyle f nbsp ubereinstimmt also f f M displaystyle f f M nbsp gilt Z B ist die Funktion f x div displaystyle f x mbox div nbsp die fur kein Argument terminiert berechenbar da es eine entsprechende Registermaschine gibt Definition mit WHILE Programmen Bearbeiten Eine Funktion f displaystyle f nbsp wie oben ist berechenbar genau dann wenn es ein WHILE Programm P displaystyle P nbsp gibt mit f A C t P E C displaystyle f AC circ tau P circ EC nbsp Dabei ist E C displaystyle EC nbsp die Eingabecodierung A C displaystyle AC nbsp die Ausgabecodierung und t P displaystyle tau P nbsp die von P displaystyle P nbsp uber die Semantik realisierte Maschinenfunktion Definition durch Rekursion Bearbeiten Seien m displaystyle mu nbsp 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 heissen µ rekursiv Die Menge der m displaystyle mu nbsp rekursiven Funktionen ist genau die Menge der berechenbaren Funktionen Ubergang von einstelligen zu mehrstelligen Funktionen Bearbeiten Uber die cantorsche Paarungsfunktion wird der Begriff der Berechenbarkeit einer k stelligen Funktion auf den der Berechenbarkeit von einstelligen Funktionen zuruckgefuhrt Insbesondere wird damit in naturlicher Weise definiert ob Funktionen von rationalen Zahlen berechenbar sind Wortfunktionen Bearbeiten Die Berechenbarkeit von Wortfunktionen lasst sich etwa mit Hilfe von Turingmaschinen zeigen Alternativ fuhrt man eine Standardnummerierung uber die Worter uber S displaystyle Sigma nbsp ein und zeigt dass die so erzeugten Zahlenfunktionen berechenbar sind Uniforme Berechenbarkeit BearbeitenEine zweistellige Funktion f x y mit der Eigenschaft dass fur jeden festen Wert a die durch fa y f a y definierte einstellige Funktion fa berechenbar ist muss selbst nicht unbedingt berechenbar sein fur jeden Wert a gibt es zwar einen Algorithmus also etwa ein Programm fur eine Turingmaschine Ta der fa berechnet aber die Abbildung a Ta ist im Allgemeinen nicht berechenbar Eine Familie fa a 0 1 2 von berechenbaren Funktionen heisst uniform berechenbar wenn es einen Algorithmus gibt der zu jedem a einen Algorithmus Ta liefert welcher fa berechnet Man kann leicht zeigen dass so eine Familie genau dann uniform berechenbar ist wenn die zweistellige Funktion x y fx y berechenbar ist Eigenschaften BearbeitenDie Komposition von berechenbaren Funktionen ist berechenbar Der Definitionsbereich einer berechenbaren Funktion ist rekursiv aufzahlbar siehe Projektionssatz Der Wertebereich einer berechenbaren Funktion ist rekursiv aufzahlbar Die universelle Funktion nimmt ihren ersten Parameter als Godelnummer eines Algorithmus und wendet diesen Algorithmus an auf ihren zweiten Parameter Die universelle Funktion ist berechenbar zum Beispiel durch eine universelle Turingmaschine Siehe auch BearbeitenHalteproblem Godelscher Unvollstandigkeitssatz Semi entscheidbare Menge Berechenbare Folge Berechenbare ZahlLiteratur BearbeitenS B Cooper Computability Theory Chapman amp 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 Aufzahlbarkeit Entscheidbarkeit Berechenbarkeit Einfuhrung in die Theorie der rekursiven Funktionen Berlin Gottingen 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 Rodding 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 Bearbeiten nbsp Wiktionary Berechenbarkeit Bedeutungserklarungen Wortherkunft Synonyme Ubersetzungen Eintrag in Edward N Zalta Hrsg Stanford Encyclopedia of Philosophy Vorlage SEP Wartung Parameter 1 und weder Parameter 2 noch Parameter 3 Abgerufen von https de wikipedia org w index php title Berechenbarkeit amp oldid 218728753