Berechenbare Funktion
Einfache Sprache
Def. Berechenbare Funktion
Eine Funktion $f:\Sigma^*\to\Sigma^*$ ist eine berechenbare Funktion wenn eine Turingmaschine $M$ existiert so, dass für jede Eingabe $w$ terminiert $M$ mit nur $f(w)$ auf dem Ausgabeband.