Home -> Themen -> Funktionen

Turing-Werkstatt

Theoretische Informatik am PC

Berechenbare Funktionen

Eine Funktion f : A -> B heißt berechenbar, wenn es eine Turing-Maschine M gibt, die zu jedem a aus A den Funktionswert f(a) berechnet.

Beispiele :

1. f : N -> N mit f(n) = 2n     Mal2.tm
2. f : N x N -> N mit f(a,b) = a - b     Minus.tm
3. f ordnet jedem Wort das gespiegelte Wort zu.    Reverse.tm

Download aller Beispiele

Man kann Funktionen definieren, die nicht berechenbar sind.
Im Thema Halteprobleme wird eine solche Funktion angegeben.