Aus Kefk.
| <imagemap>-Fehler: Bild ist ungültig oder nicht vorhanden
| Die Artikel Berechenbare Funktion und Berechenbarkeit überschneiden sich thematisch. Hilf mit, die Artikel besser voneinander abzugrenzen oder zu vereinigen. Die Diskussion über diese Überschneidungen findet hier statt. Bitte äußere dich dort, bevor du den Baustein entfernst. Wuzel 20:27, 6. Mär. 2007 (CET)
|
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 f(n) 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.
