Loading AI tools
Möglichkeit, ein Problem mittels einer Berechnungsanweisung auf eine effektive Weise zu lösen Aus Wikipedia, der freien Enzyklopädie
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.
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.
In der Berechenbarkeitstheorie werden meist nur Funktionen natürlicher Zahlen betrachtet.
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.
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.
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.
Ü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.
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.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.