[ Inhalt ] [ Index ]

Berechenbare Funktionen

     

Man kann nun Algorithmen als Funktionen betrachten, die Eingabedaten auf Ausgabedaten abbilden.

Umgekehrt stellt sich die Frage, ob zu einer gegebenen Funktion immer ein Algorithmus existiert, der diese Funktion realisiert:

Definition: (berechenbare Funktion [9])
Es sei E ein Alphabet und .

Eine Funktion heißt berechenbar, falls es einen Algorithmus gibt, mit .

Zu jedem Argument läßt sich also f(w) in endlich vielen Schritten berechnen.

Beispiel:
. Wir interpretieren Worte aus als natürliche Zahlen. Dann ist und für und ist

mit f(n) = n + 1

eine berechenbare Funktion, da es trivialerweise für diese Funktion einen Algorithmus gibt.

Wir werden aber gleich sehen, daß keineswegs zu jeder Funktion ein Algorithmus existiert.