VL-02 Turing Maschinen Flashcards
Was sind die 3 Arten wie ein Berechnungsproblem dargestellt werden kann?
Relation, Funktion oder Sprache
Was ist eine K-Band TM und wie unterscheidet sie sich zur k-spurigen TM?
Ein k-Band TM ist eine Verallgemeinerung der TM mit k Arbeitsbändern, welche über einen unabhängigen Kopf verfügen.
δ : (Q \ {¯q}) × Γ^k → Q × Γk × {L, R, N}^k
Die k-spruige TM hat nur einen Kopf
Wie kann eine k-Band TM durch eine 1-Band TM simuliert werden?
Eine k-Band-TM M mit Zeitbedarf t(n) und Platzbedarf s(n) kann von einer 1-Band-TM M′ mit Zeitbedarf O(t2(n)) und Platzbedarf O(s(n)) simuliert werden.
Wie funktioniert die universelle TM?
Die universelle TM liest als Eingabe die kodierte TM (Gödelnummer) <M> und die Eingabe w ein und simuliert das Verhalten von M unter w.</M>
Was sind die Eigenschaften einer Gödelnummer?
- Präfixfrei: Keine Gödelnummer ist Teil einer anderen Gödelnummer
- Kodierung der Übergänge
Der Übergang δ(qi , Xj ) = (qk , Xℓ, Dm) wird kodiert durch den
Binärstring
0^i 10^j 10^k 10^ℓ 10^m
⟨M⟩ = 111 code(1) 11 code(2) 11 . . . code(s) 111
Was besagt die Church-Turing These?
Die Klasse der TM-berechenbaren Funktionen stimmt mit der Klasse der “intuitiv berechenbaren” Funktionen überein.
