Registermaschine ↔ Turingmaschine ::: Theoretische Informatik

Informatik » Bachelor » Theoretische Informatik » Berechenbarkeit » Registermaschine ↔ Turingmaschine

Turingmaschinen (kurz: DTM oder NTM) Berechenbarkeit Entscheidbarkeit

Registermaschine ↔ Turingmaschine

Man kann eine Registermaschine mit einer Turingmaschine simulieren und umgekehrt. Hiermit führt man auch den Beweis, daß eine Registermaschine mit indirekter Adressierung die gleiche Mächtigkeit wie eine Registermaschine mit direkter Adressierung hat.

Simulation von Registermaschinen durch Turingmaschinen

Die Zustandsmenge ist: $Q=Q_{0}\cup Q_{1}\cup\ldots\cup Q_{p}\cup Q_{p+1}$ , wobei

die Anzahl der Programmzeilen der Registermaschine ist. Die Zustandsmenge $Q_{0}$ erzeugt die Ausgangskonfiguration auf den Bandzellen, die Zustandsmenge $Q_{p+1}$ stellt die Ausgabe zur Verfügung.
Die Turingmaschine verwendet nun 4 Bänder:

1.Band	Eingabe
2.Band	Registerbelegung der Form
	$\char93 \char93 \char93 0\char93 bin(c(0))\char93 \char93 1\char93 bin(c(1))\char93 \char93 \ldots$
3.Band	Ausgabe
4.Band	Nebenrechnungen

Wird nun ein Befehl, der in einer Programmzeile steht, abgearbeitet, wird folgendes gemacht (Am Beispiel von add $\ast$ 24):

Auf Band 2 wird zuerst an die Stelle 24 gespult, dann wird an die Stelle gespult, wo der Wert aus der Registerzelle 24 hinzeigt. Dieser Wert wird ausgelesen und auf das Nebenrechnungsband (Band 4) gelegt.
Der Akkumulator auf Band 2 wird mit dem Nebenrechnungsband bitweise addiert.
Das Ergebnis wird zurück in den Akkumulator kopiert. Die Zustandsmenge wechselt in die nächste Zustandsmenge⁷: $Q_{neu}=Q_{p_{\,aktuell}+1}$ .

Kosten
Jeder Befehl benötigt eine konstante Anzahl an Suchoperationen bzw. arithmetischen Operationen, die ausgeführt werden müssen. Diese laufen in polynomieller Zeit.
Es gilt

$\begin{displaymath}O(poly(N))\end{displaymath}$

Für

gilt

$\begin{displaymath}N=O(t_{R}(n_{1},\ldots,n_{k})+\sum^{k}_{i=1}L(n_{i}))\end{displaymath}$

was darauf zurückzuführen ist, daß die Registermaschine $t_{R}(n_{1},\cdot,n_{k})$ Zeit braucht und die Länge des Bandes $\sum^{k}_{i=1}L(N_{i})$ ist, über welches gespult wird.
Insgesamt erhalten wir als Laufzeit der Simulation

$\begin{displaymath}O(poly (t_{R}(n_{1},\cdots,n_{k})+\sum^{k}_{i=1}L(n_{i})))\end{displaymath}$

Insbesondere, wenn die Laufzeit der Registermaschine polynomiell beschränkt ist, gilt für die gesamte Simulation

$\begin{displaymath}O(poly(m)).\end{displaymath}$

Simulation von Turingmaschinen durch Registermaschinen

Allgemeiner Teil
Die Übergangsfunktion wird simuliert, indem wir für jede partielle Funktion eine IF-Abfrage programmieren:
Wenn(Zustand=... und Zeichen=...)
dann{Zustand=...; Zeichen=...; Zeigerbewegung=...;}

1. Möglichkeit: Durch indirekte Adressierung
Man benutzt eine linksseitig beschränkte DTM. Diese ist äquivalent zu der unbeschränkten DTM.

Register 1:	aktueller Zustand
Register 2:	Nummer des jeweils gelesenen Zeichens ( ist $\Box$ ,
	dann geht es für das Bandalphabet $\Gamma$ mit weiter)
Register 3:	Position des Zeigers auf dem simulierten Band
Register 4:	Wird freigehalten für Nebenrechnungen
Register 5 und höher:	Das Band der Turingmaschine⁸

Man kann nun die DTM mit Hilfe des ,,Semibandes'' simulieren.

Kosten:
Die Rechenzeit der DTM ansich ist $t_{\tau}(w)$ . Dabei werden maximal $t_{\tau}(w)+1$ Bandquadrate besucht. Die Operanden der Registermaschinen-Befehle sind deshalb aus dem Bereich $\{0,\ldots,N_{w}\}$ , wobei

$\begin{displaymath}N_{w}=\max{\{t_{\tau}(w)+6,\vert\Gamma\vert,\vert Q\vert\}}\end{displaymath}$

Somit kostet jeder Konfiguartionswechsel

$\begin{displaymath}O(\log{N_{w}})=O(\log{\vert Q\vert}+\log{\vert\Gamma\vert}+\log{t_{\tau}(w)})=O(\log{t_{\tau}(w)})\end{displaymath}$

Es werden $t_{\tau}(w)$ Konfigurationswechsel ausgeführt. Deshalb sind die Gesamtkosten für das logarithmische Kostenmaß:

$\begin{displaymath}O(t_{\tau}(w)\cdot \log{t_{\tau}(w)})\end{displaymath}$

unter dem uniformen:

$\begin{displaymath}O(t_{\tau}(w)\cdot 1)\end{displaymath}$

Hinzu kommen unter dem uniformen Kostenmaß

$\begin{displaymath}O\left(\sum^{k}_{i=1}L(n_{i})\right)=O(\vert w\vert)\end{displaymath}$

und unter dem logarithmischen Kostenmaß

$\begin{displaymath}O\left(\sum^{k}_{i=1}L(n_{i})^{2}\right)=O(\vert w\vert^{2})\end{displaymath}$

Schritte zur Erstellung der Ausgangskonfiguration.

Daraus folgt: Die gesamte Simulation läuft unter:

$\begin{displaymath}O(poly(t_{\tau}(w)+\vert w\vert))\end{displaymath}$

2. Möglichkeit: Mit zwei Stacks
Wir benutzen zwei Keller. Auf den einen tun wir den linken Teil des Bandes, der links vom Schreib/Lesekopf zu finden ist, auf den anderen den rechten Teil. Weiterhin benutzen wir eine Variable für die aktuelle Bandzelle⁹.
Wir können die Keller implementieren, indem wir Bitverschiebungen¹⁰ machen. Wir können einen Wert des Stacks durch die Basis mit Rest teilen und erhalten die oberste Zelle oder aber wir können eine Zelle auf den Stack schieben, indem wir den Wert des Stacks mit der Basis multiplizieren und den Wert der Zelle addieren:
Rauf:

$\begin{displaymath}stack=stack\cdot basis + wert\end{displaymath}$

Runter:

$\begin{displaymath}wert= stack\, mod\, basis\end{displaymath}$

Simulation von Turingmaschinen mit Turingmaschinen - Universelle Turingmaschinen

Eine Turingmaschine kann man als ein einzelnes Wort kodieren. Universelle Turingmaschinen benutzen als Eingabe eine Turingmaschine, die sie simulieren.
Auf Band 1 der universellen Turingmaschine steht die kodierte Turingmaschine und das darauf angewandte Eingabewort. Folgendermaßen kann man die Übergangsfunktion kodieren:

$\begin{displaymath}\char93 \char93 bin(i)\char93 bin(j)\char93 bin(I)\char93 bin(J)\char93 bin(X)\char93 \char93 \ldots\end{displaymath}$

Auf Band 2 speichern wir den aktuellen Zustand. Auf Band 3 wird der aktuelle Bandinhalt gespeichert. Band 4 benutzen wir für Nebenrechnungen. Eine solche universelle Turingmaschine kann die eingegebene Turingmaschine simulieren.

Fußnoten

... Zustandsmenge ⁷: Sofern wir keine Gotobefehle haben
... Turingmaschine ⁸: Das Register enthält die te Bandzelle
... Bandzelle ⁹: Alternativ kann man auch auf diese verzichten. Es gibt Implementierungen, die direkt mit der Variable vom Stack arbeiten.
... Bitverschiebungen ¹⁰: Im Binärsystem. In anderen Systemen verschieben wir um andere Basen.

Turingmaschinen (kurz: DTM oder NTM) Berechenbarkeit Entscheidbarkeit

Ψ Die Informatikseite