This flashcard is just one of a free flashcard set. See all flashcards!
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
=>
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
auf1.)
kopiert die in Programmzeile b angesprochenen Register auf Band 12.) 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.
