Zu dieser Karteikarte gibt es einen kompletten Satz an Karteikarten. Kostenlos!
26
Simulation RAM durch TM
Simulation der RAM als 2-Band-TM
- ein Band für den Speicher der RAM
- das andere ist Arbeitsband für die TM in den Unterprgrammen
- pro Programmzeile der RAM (p-Stück) ein TM-Unterprogramm
=>
ist Unterprogramm für Programmzeile i
-
ist Unterprogramm zur Initialisierung der TM
-
ist Unterprogramm zur Ergebnisaufbereitung
- den Befehlszähler b kann die TM im Zustandsraum abspeichern, da es nur konstant viele Zeilen gibt
- Inhalt der Registern ist allerdings unbeschränkt
=> mit Speicher, Befehlszähler und Unterprogrammen ist die RAM vollständig erfasst.
Rechenschritte:
Rufe durch Befehlszähler b beschriebenes Unterprogramm
auf
1.)
kopiert die in Programmzeile b angesprochenen Register auf Band 1
2.) führt notwendige Operationen auf Registerinhalten aus
3.) kopiert das Ergebnis des in Programmzeile b angegebenen Registers zurück auf Band 2
4.) aktualisiert Programmzähler
Laufzeit: Länge des Speicherinhalts auf Band 2 ist durch O(n+t(n)) beschränkt, weil die RAM für jedes neue Bit, das sie erzeugt, mindestens eine Zeiteinheit benötigt. Initialisierung benötigt O(n). Laufzeit der Unterprogramme ist polynomiell in Länge der Bandinschrift auf Band 2 beschränkt, also in n+t(n). Gesatmlaufzeit ist also polynomiell in n+t(n) beschränkt.
- ein Band für den Speicher der RAM
- das andere ist Arbeitsband für die TM in den Unterprgrammen
- pro Programmzeile der RAM (p-Stück) ein TM-Unterprogramm
=>
![](/pool/data/tex/164f4ec8743ae6c1ba707c618b76ff61.gif)
-
![](/pool/data/tex/c799681b2a0fb7c2094ebe82855ed99c.gif)
-
![](/pool/data/tex/0fe4d61cec0378a29e4a911a252b078f.gif)
- den Befehlszähler b kann die TM im Zustandsraum abspeichern, da es nur konstant viele Zeilen gibt
- Inhalt der Registern ist allerdings unbeschränkt
=> mit Speicher, Befehlszähler und Unterprogrammen ist die RAM vollständig erfasst.
Rechenschritte:
Rufe durch Befehlszähler b beschriebenes Unterprogramm
![](/pool/data/tex/06154eca89935c16391249e30b659550.gif)
1.)
![](/pool/data/tex/06154eca89935c16391249e30b659550.gif)
2.) führt notwendige Operationen auf Registerinhalten aus
3.) kopiert das Ergebnis des in Programmzeile b angegebenen Registers zurück auf Band 2
4.) aktualisiert Programmzähler
Laufzeit: Länge des Speicherinhalts auf Band 2 ist durch O(n+t(n)) beschränkt, weil die RAM für jedes neue Bit, das sie erzeugt, mindestens eine Zeiteinheit benötigt. Initialisierung benötigt O(n). Laufzeit der Unterprogramme ist polynomiell in Länge der Bandinschrift auf Band 2 beschränkt, also in n+t(n). Gesatmlaufzeit ist also polynomiell in n+t(n) beschränkt.