Additive Register Maschinen Einfache k-Register

4.12.2015
"Satz:" Alles, was von einer Turingmaschine berechnet werden
kann, kann auch von einer 3-Register-Maschine
berechnet werden.
Beweisidee: schrittweise Simulation von M durch ΠM
Konfiguration von M:
L | 0 | 0 | 0 | bl | bl-1 | L L | b1 | b0 | a0 | a1 | a2 | L L | ar-1 | ar | 0 | 0 | L
Genauer Satz: Es sei M = (Σ, Γ, Q, s, F, 0 , ∆) eine TM, mit
Γ = { 0 , L , t-1}, die bei Eingabe w∈Σ*, falls sie hält, dies mit
Bandinhalt fM(w) ∈ Γ* und Kopf auf dem linken Ende des
Bandinhaltes tut.
Kontrolle
Es gibt eine Program ΠM für eine 3-Register-Maschine, das bei
Eingabe w t genau dann hält, wenn M dies bei Eingabe w tut, und
die als Ausgabe fM(w) t berechnet.
Entsprechende Register-Inhalte der 3-Register-Maschine :
x0 = a0a1 L ar t
a0a1L an t = ∑0 i n ai ti
x1 = b0b1 L bl t
4.12.2015
1
4.12.2015
x3 für Zwischenergebnisse
Additive Register Maschinen
k-Register Maschine:
Speicher: x1, L , xk
Operationen: xi = xj op xk
xi = xj op c
xi = c
(tunix)
Prädikate:
Einfache k-Register-Maschinen
Speicher: x1, L , xk
k "Register", jeder speichert eine
natürliche Zahl
k "Register", jeder speichert eine
natürliche Zahl
Operationen: xi = xi + 1 (inkrementieren)
xi = xi 1 (dekrementieren)
mit op ∈ { + , , * , div , mod }
ab
2
(tunix)
= max{a-b,0}
a div b = ⌊ a/b ⌋
Prädikate:
c Konstante
xi =? 0
xi =? 0
mit der üblichen Semantik
mit der üblichen Semantik
4.12.2015
3
4.12.2015
4
1
4.12.2015
"Satz:" Alles, was von einer k-Register-Maschine berechnet
werden kann, kann auch von einer additiven
(k+3)-Register-Maschine berechnet werden.
"Satz:" Alles, was von einer k-Register-Maschine berechnet
werden kann, kann auch von einer additiven
(k+3)-Register-Maschine berechnet werden.
"Satz:" Alles, was von einer additiven
m-Register-Maschine berechnet
werden kann, kann auch von einer einfachen
(m+3)-Register-Maschine berechnet werden.
4.12.2015
5
4.12.2015
6
2

Download Report