Turing Maschinen 2 Flashcards
k-Band-TM Beschreibung
- Verallgemeinerung der TM
- k Arbeitsbänder mit jeweils einem unabhängigen Kopf
- Zustandsüberführungsfunktion ist von der Form:
δ : (Q \ {q-}) x Γ^k -> Q x Γ^k x {R,L,N}^k - Band 1 funktioniert als Ein-/Ausgabeband
- Die Zellen der anderen Bänder sind anfangs leer
k-Band-TM Zustandsüberführungsfunktion
δ : (Q \ {q-}) x Γ^k -> Q x Γ^k x {R,L,N}^k
Satz Simulation k-Band-TM durch 1-Band-TM
Eine k-Band-TM M mit Zeitbedarf t(n) und Platzbedarf s(n) kann von einer 1-Band-TM M’ mit Zeitbedarf O(t^2(n)) und Platzbedarf O(s(n)) simuliert werden.
Gödelnummer
eindeutige präfixfreie Kodierung, die jeder Turingmaschine M ein Wort über dem Alphabet {0,1} zuordnet
TM-en die Kodierung haben können
Turingmaschinen der Form:
- minim 2 Zustände: Anfangszustand: q1, Endzustand: q2
- Γ = {0, 1, B}
Gödelnummer einer TM M mit s Übergängen
= 111 code(1) 11 code(2) 11 … 11 code(s) 111
wobei code(t) = Kodierung des t-ten Übergängs.
Der Übergang δ(q_i, X_j) = (q_k, X_l, D_m) wird kodiert durch den Binärstring 0^(i) 1 0^(j) 1 0^(k) 1 0^(l) 1 0^(m).
Kodierung der Bewegungsrichtungen in Gödelnummer
Left(L) = 1, Neutral(N)= 2, Right(R)=3
Implementierung der universellen TM U
3-Band-TM:
Band 1 - simuliert das Band der TM M
Band 2 - Gödelnummer von M
Band 3 - aktueller Zustand von M
Universellen TM U - Laufzeit
U simuliert M mit konstanten Zeitverlust
Was für eine Zeitverlust hat die universelle 1-Band-TM? Wir erhält man eine universelle 1-Band-TM mit konstantem Zeitverlust?
Quadratische Zeitverlust. Wenn wir die Gödelnummer auf Spur 2 und den Zustand auf Spur 3 mit dem Kopf der TM M mitführen.
Church-Turing These
Die Klasse der TM-berechenbaren Funktionen stimmt mit der Klasse der “intuitiv berechenbaren” Funktionen überein.
rekursive Funktion
TM-berechenbare Funktion
rekursive Sprache
TM-entscheidbare Sprache
Rechnermodelle gleich mächtig wie TM
Lambda-Kalkül, μ-rekursive Funktionen
