Berechenbare Funktion
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
# Eine Funktion heißt genau dann total berechenbar, wenn es eine Turingmaschine gibt, die für jede Eingabe den dazugehörigen Funktionswert ausgibt.
# Eine Funktion heißt genau dann partiell berechenbar, wenn es eine Turingmaschine gibt, die für jede Eingabe , für die definiert ist, anhält und den dazugehörigen Funktionswert ausgibt und sonst nicht hält.
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.
