Berechenbare Funktionen stellen einen zentralen Begriff in der Theoretischen Informatik dar. Ausführlich werden die Zusammenhänge in der Berechenbarkeit erläutert. Für den Begriff des Rechnens sind dort verschiedene Vorschläge dargestellt. Wir verwenden hier die Turingmaschine als Berechenbarkeitsbegriff. Man könnte genau so gut Registermaschinen verwenden (man hätte dann Maschinenfunktionen auf den natürlichen Zahlen erklärt, statt auf den endlichen Zeichenketten).

Definition

1. Eine Funktion $f:\; A\backslash to\; B$ heißt genau dann total berechenbar, wenn es eine Turingmaschine gibt, die für jede Eingabe $n\backslash in\; A$ den dazugehörigen Funktionswert $f(n)\backslash in\; B$ ausgibt.
2. Eine Funktion $f:\; A\backslash to\; B$ heißt genau dann partiell berechenbar, wenn es eine Turingmaschine gibt, die für jede Eingabe $n\backslash in\; A$, für die $f(n)$ definiert ist, den dazugehörigen Funktionswert $f(n)\backslash in\; B$ ausgibt.

Eigenschaften

• Die Komposition von totalen berechenbaren Funktionen ist total berechenbar.
• Der Definitionsbereich einer partiell berechenbaren Funktion ist rekursiv aufzählbar. Er muss nicht rekursiv entscheidbar sein.
• Der Wertebereich einer partiell berechenbaren Funktion ist rekursiv aufzählbar. Er muss nicht rekursiv entscheidbar sein.
• Die universelle Funktion ist partiell berechenbar; universell heißt, es ist für jede partiell berechenbare Funktion und jeden möglichen Eingabewert der Wert zu berechnen.
• Die universelle Funktion ist nicht total berechenbar.

Rekursionstheorie

Částečně rekurzivní funkce | Recursive function | Función recursiva | Fonction récursive | Endurkvæmt fall | Funzione ricorsiva | Funkcja rekurencyjna | Recursividade | Рекурсивная функция | 递归函数