Turing-Berechenbarkeit

• Für Zahlen: Eine (partielle) Funktion $f:{\mathbb{N}}^k\to \mathbb{N}$ heißt Turing-berechenbar, wenn es eine DTM $M$ gibt, die bei der Eingabe der Binärdarstellungen der Zahlen (getrennt durch #) nach endlicher Zeit im akzeptierenden Zustand hält und die Binärdarstellung des Ergebnisses auf dem Band stehen hat. Formal:
  $f(n_1,\dots ,n_k)=m⟺\mathrm{\exists }{z}_e\in E:z_0\text{BIN}(n_1)\mathrm{\#}\dots \mathrm{\#}\text{BIN}(n_k){⊢}_M^{\ast }{z}_e\text{BIN}(m)$
• Für Sprachen (Entscheidbarkeit): Eine Sprache $L\subseteq {\mathrm{\Sigma }}^{\ast }$ ist entscheidbar, wenn ihre charakteristische Funktion ${\chi }_L$ Turing-berechenbar ist.

Die TM muss für jede Eingabe $x\in {\mathrm{\Sigma }}^{\ast }$ halten und entweder 1 oder 0 ausgeben.