Probleme und Funktionen

• Probleme sind Teilmengen von $\Sigma^*$, wobei $\Sigma$ endliches Alphabet ist.
• Berechnung von Funktionen:

  Definition: Seien $\Sigma,\ \Gamma$ Alphabete. Eine TM (bzw. RAM) M berechnet eine (partielle) Funktion $\text{f}: \Sigma^* \rightarrow \Gamma^*$ gdw. $(\forall x \in \Sigma^*)$ [falls M mit Eingabe x hält, dann ist die Ausgabe von M gleich f$(x), x \in$ Definitionsbereich von f].