Turing Maschinen

Definition $$T=(Q,\Sigma ,\Gamma ,...)$$

T als partielle Funktion $$T:{\Sigma }^{\ast }\to {\Gamma }^{\ast }$$

Schreibweise wenn die Funktion F für den Input x nicht definier ist, d.h. keinen Wert annimt.

$$F(x)=\uparrow$$

Turing Berechenbarkeit

$$ T(w) = f(w), \str(falls f(w) definiiert ist) $$