Berechenbare Funktion
Einfache Sprache
Durch TM berechenbare Funktion
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.
Durch Sequenzielle Maschine berechenbare Funktion
Def. Durch Sequenzielle Maschine berechenbare Funktion
Sei $M=(Q,A,B,\delta,\alpha,q_I,\iota,\omega)$ eine sequentielle Maschine. Dann ist die von $M$ berechnete Funktion $f_M$ die Partielle Funktion $A^*\rightharpoonup B^*$ mit
$$f_M=\left\{\begin{array}{cc} & \begin{array}{ll}\iota\hat\delta(q_I,w)\omega(\hat\delta(q_I,w))& \text{falls $w$ auf $\hat\delta(q_I,w)$definiertist}\\\text{undefiniert}&\text{sonst}\end{array}\end{array}\right.$$Diese Funktion ist eine Sequenzielle Funktion.