Berechenbare Funktion

In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. 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 überhaupt eine Ausgabe produziert. Wenn der Algorithmus nicht terminiert, dann liegt die Eingabe nicht im Definitionsbereich.

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.

Zu den Berechnungsmodellen, die schwächer sind als Turingmaschinen, 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. 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.

Inhaltsverzeichnis

Formale Definition

Man sagt, der Algorithmus P berechnet die Funktion f : T\rightarrow \mathbb{N} mit T\subseteq\mathbb{N}^k, wenn P bei Eingabe von \left( n_1, ..., n_k \right) \in T nach einer endlichen Zahl von Schritten den Wert f \left( n_1,... , n_k \right) ausgibt, und bei Eingabe von \left( n_1, ..., 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 f:\mathbb{N}^k \rightsquigarrow \mathbb{N} heißt berechenbar, wenn sie eingeschränkt auf ihren Definitionsbereich f:\mbox{Def}(f) \to \mathbb{N} eine berechenbare Funktion ist.

Zahlenfunktionen

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.

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.

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.

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

Wortfunktionen

Die Berechenbarkeit von Wortfunktionen lässt sich entweder 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

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 eine programm für eine Turingmaschine) Ta, der fa berechnet, aber die Abbildung aTa 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

Siehe auch


Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • berechenbare Funktion — I berechenbare Funktion,   Informatik, mathematische Logik: eine Funktion f : M → N, für die es einen Algorithmus gibt, der für jeden Eingabewert …   Universal-Lexikon

  • Berechenbare Menge — Als semi entscheidbare Menge (auch halb entscheidbare Menge) wird in der Berechenbarkeitstheorie eine Menge A bezüglich einer Grundmenge M bezeichnet, wenn ihre partielle charakteristische Funktion definiert durch berechenbar ist. Die Menge M… …   Deutsch Wikipedia

  • Berechenbare Folge — Eine Folge heißt genau dann berechenbar, wenn es eine berechenbare Funktion gibt mit f(i) = ai. Siehe auch: Rekursive Aufzählbarkeit, Berechenbarkeit Kategorie: Berechenbarkeitstheorie …   Deutsch Wikipedia

  • Berechenbare Zahl — Als berechenbare Zahl wird eine reelle Zahl bezeichnet, wenn es eine Berechnungsvorschrift gibt, die jede ihrer Dezimalstellen erzeugen kann. Insbesondere gibt es nicht berechenbare Zahlen. Inhaltsverzeichnis 1 Definition 2 Eigenschaften 3 Siehe… …   Deutsch Wikipedia

  • Ackermann-Funktion — Die Ackermannfunktion ist eine 1926 von Wilhelm Ackermann gefundene, extrem schnell wachsende mathematische Funktion, mit deren Hilfe in der theoretischen Informatik Grenzen von Computer und Berechnungsmodellen aufgezeigt werden können. Heute… …   Deutsch Wikipedia

  • Radó-Funktion — Fleißige Biber (auch engl. Busy Beaver) sind Turingmaschinen, die möglichst viele Einsen auf das Band schreiben, ohne in eine Endlosschleife zu geraten (d. h. die nach einer endlichen Anzahl Rechenschritte halten). Die Radó Funktion (auch… …   Deutsch Wikipedia

  • Berechenbar — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Turing-Berechenbarkeit — In der Berechenbarkeitstheorie nennt man eine Funktion berechenbar, wenn es einen Algorithmus gibt, der die Funktion berechnet. Die Funktion, die ein Algorithmus berechnet, ist gegeben durch die Ausgabe, mit der der Algorithmus auf eine Eingabe… …   Deutsch Wikipedia

  • Königslemma — Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das… …   Deutsch Wikipedia

  • Lemma von König — Das Lemma von König oder Königslemma ist ein Theorem der Graphentheorie von Dénes Kőnig (1936). Die Berechenbarkeit des Lemmas wurde gründlich in der Mathematischen Logik erforscht. Dénes Kőnig wird korrekterweise mit Doppelakut geschrieben. Das… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”