Turing Maschine

siehe:
Alan Turing
lntelligent_Machinery_1948-2.pdf

Church-Turing These

Church-Turing These

Die Klasse der Turing-berechenbaren Funktionen stimmt mit der Klasse der intuitiv berechenbaren Funktionen überein.

siehe: entscheidbar
Link to original

Definition

$M = (Q, Σ, Γ, [, δ, q_{s}, q_{a}, q_{r})$
$Q$ endliche Menge an Zuständen
$Σ$ das Eingabealphabet
$Γ$ das Arbeitsalphabet
$[\in Γ\Σ$ der linke Endmarker
$\textvisiblespace \in Γ\Σ$ das Blanksymbol
$δ : Q \times Γ \to Q \times Γ \times {- 1, 0, + 1}$ die Übergangsfunktion ist wobei gilt:

für alle $p \in Q$ ein $q \in Q$ und $d \in {0, + 1}$ existieren, so dass $δ (p, [) = (q, [, d]$ und

für alle $a \in Γ$ gilt $δ (q_{a}, a) = (q_{a}, a, 0)$ und $δ (q_{r}, a) = (q_{r}, a, 0)$

$q_{s} \in Q$ der Anfangszustand
$q_{a} \in Q$ der akzeptierende Zustand
$q_{r} \in Q$ der verwerfende Zustand mit $q_{a} \neq = q_{r}$