Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
73
Beweis: WHILE ist Turing-mächtig
Jede TM kann durch RAM mit konstant vielen Registern mit eingeschränktem Befehlssatz simuliert werden(LOAD,CLOAD,STORE,CADD,CSUB,GOTO, if c(0)!=0 GOTO, END)
Sei
ein RAM-Programm, dass aus l Zeilen und k Registern für natürliche Zahlen besteht
1.) Jede Zeile des RAM-Programms wird in eine WHILE Programm transformiert (Zeile i ist im WHILE Programm
)
dazu: Inhalt von Register c(i) in Variable
- bei k Registern also
- Befehlszähler in Variable
realisiert
-
Variable mit initialem Wert 0
2.) Füge WHILE-Programme Pi' zu einem großen Programm P zusammen:
WHILE
DO
END Semantik: Falls
führe aus.
Das WHILE-Programm berechnet also dieselbe Funktion wie
Sei
ein RAM-Programm, dass aus l Zeilen und k Registern für natürliche Zahlen besteht1.) Jede Zeile des RAM-Programms wird in eine WHILE Programm transformiert (Zeile i ist im WHILE Programm
)dazu: Inhalt von Register c(i) in Variable
- bei k Registern also
- Befehlszähler in Variable
realisiert-
Variable mit initialem Wert 02.) Füge WHILE-Programme Pi' zu einem großen Programm P zusammen:
WHILE
DOEND Semantik: Falls
führe aus. Das WHILE-Programm berechnet also dieselbe Funktion wie
