Berechnung einer TM

Einfache Sprache

Def. Berechnung einer TM

Sei $\mathcal{M}=(Q,A,\Gamma,\delta,q_0,\textvisiblespace,q_{acc},q_{rej})$ TM. Eine Berechnung von $\mathcal{M}$ auf $w\in A^*$ eine Folge $\kappa_0\kappa_1\ldots$ mit $\kappa_i\in\Gamma^*\times Q\times\Gamma^+$ von Konfiguration. Weiter müssen folgende Eigenschaften gelten:

1. $\kappa_0=q_0w\textvisiblespace$ ist Anfangskonfiguration,
2. für alle $i\in\mathbb{N}$ gilt $\kappa_{i+1}$ ist Folgekonfiguration von $\kappa_i$ und
3. falls Berechnung endlich ist, besitzt die letzte Konfiguration keine Folgekonfiguration

Bemerke: Eine Berechnung heißt akzeptiert, falls $q_m\in F$.