BuK-Übung09
Aus ProgrammingWiki
$WHILE$-, $LOOP$- und $GOTO$-berechenbare Programme stellen einen, wie der Name schon sagt, programmatischen Ansatz der Problemlösung dar. Ihnen gegenüber stehen handfeste bzw. hardwarenahe Ansätze wie Registermaschinen und Mehrband-Turing-Maschinen. Im Folgenden wird auf diese 3 Modelle mit je einem Beispiel und einem Fazit eingegangen.
In der Vorlesung wurde als Übungsaufgabe nach einen Nachweis gesucht, das die Ackermann-Peter-Funktion $WHILE$-berechenbar ist. Diese Aufgabe wird bei der Vorstellung der $WHILE$-Programme gelöst.
Inhaltsverzeichnis |
$WHILE$-berechenbarkeit der Ackermann-Peter-Funktion
Weisen sie nach, dass die Ackermann-Peter-Funktion (AP-Funktion) $WHILE$-berechenbar ist.
Die AP-Funktion ist definiert durch:
AP(0, y) = y + 1 AP(x, 0) = AP(x - 1, 1); x > 0 AP(x, y) = AP(x - 1, AP(x, y - 1)); x, y > 0
Im folgenden werden 2 Beweise demonstriert.
Beweis 1:
Der erste konstruktive Beweise setzt zunächst voraus, das die AP-Funktion in einer Turing-vollständigen Sprache implementiert wird. Da Racket eine Turing-Vollständigen Sprache ist, kann diese hierfür verwendet werden.
Wenn man nun den Satz zu Grunde legt, wonach jede Turing-berechenbare Funktion auch $WHILE$-berechenbar und jede $WHILE$-berechenbare Funktion auch Turing-berechenbar ist, so ist auch die AP-Funktion $WHILE$-berechenbar.
Beweis 2:
Für den zweiten Beweis bedient man sich der Möglichkeit, das für ein $WHILE$-Programm Stacks zur Verfügung stehen. Diese sind durch die folgenden 3 Befehle definiert.
- INIT
- initialisiert einen leeren Stack
- PUSH(x)
- legt den Wert x auf dem Stack ab so das er an der obersten Position ist
- POP
- liest verbrauchend den Wert auf der obersten Position und gibt diesen zurück
Diese Funktionen lassen sich in einem $WHILE$-Programm implementieren und stehen daher für den späteren Beweis zur Verfügung.
Stack in einem $WHILE$-Programm
Angenommen man speichert den Inhalt eines Stacks der Form $(n_1, n_2, n_3, ... n_i)$ mit $n_1$ als oberstes Element in einer einzelnen Zahl, welche sich durch eine Funktion $c$ berechnen lässt, so kann man diese Zahl aus $n = c(n_1, c(n_2, c(n_3, ... c(n_i, 0))))$ errechnen. Zudem benötigt man für die Funktion $c: \N^2\rightarrow\N$ zwei Umkehrfunktionen $e$ und $f$, welche die ursprünglichen Parameter von $c$ errechnen. $e$ liefert dabei das erste Argument, das zuletzt zum Stack hinzugefügte Element, zurück wohingegen $f$ den vorherigen Wert des Stacks ermittelt.
$$ n = c(n_k, n)$$ $$ n_k = e(c(n_k, n))$$ $$ n = f(c(n_k, n))$$
Diese Funktionen kann man in $LOOP$-Programmen angeben, da sie primitiv rekursiv sind. Da $LOOP$-berechenbare Funktionen eine Teilmenge der $WHILE$-berechenbaren sind, ist zwangsläufig auch von der $WHILE$-berechenbarkeit der Funktionen $c$, $e$ und $f$ aus zu gehen.
Nun kann man die Stack Operationen wie folgt definieren:
- INIT
- Durch Initialisieren von n mit 0 wird ein leerer Stack bereit gestellt.
- PUSH(x)
- Die Funktion $n = c(x, n)$ lässt sich mit folgendem $LOOP$-Programm implementieren:
- POP
- Mit Hilfe von $e$ und $f$ wird der oberste Wert des Stacks zurück gegeben und der vorherige Wert des Stacks selbst errechnet.
- Die Funktion $e(x)$ ist implementiert durch:
- Die Funktion $f(x)$ ist implementiert durch:
AP-Funktion mit Stack
Nun kann man einen Stack verwenden um die AP-Funktion in einem $WHILE$-Programm zu implementieren.
Wenn man sich die Visualisierung des Stacks über den Programmverlauf hinweg vor Augen hält, ist diese Lösung sogar recht intuitiv. Hierzu hilft es zunächst diesen auf zu schreiben. Im folgenden Beispiel wird das Ergebnis für $AP(2, 2)$ errechnet.
Dieser Aufschrieb stellt nun auch die Arbeitsweise des $WHILE$-Programms dar. Die Zahlen, welche jeweils auf einer Zeile sind, liegen in genau jener Reihenfolge auf dem Stack vor. Die oberste Zahl befindet sich dabei auf der rechten Position. Zum Start sind es die beiden Werte, welche in Programmzeile 2 und 3 auf dem Stack abgelegt werden. Das Programm wird anschließend so lange ausgeführt, bis nur noch ein Wert, das Endergebnis, auf dem Stack liegt und dieser Wert in Variable $x_0$ zurück gegeben werden kann.
Nun wird in jedem Schleifendurchlauf eine Regel der AP-Funktion auf die oberen beiden Werte im Stack angewendet. Meist ist dies die dritte und letzte Regel. Zum Beispiel geht $AP(2, 1)$ über in $AP(1, AP(2, 0))$. Dies wird ebenfalls in der Programmzeile 12 realisiert, welche die Werte 2 und 1 des Stacks durch die Werte 1, 2 und 0, in genau dieser Reihenfolge, ersetzt. Im Falle von 2 und 0 wird mit der Programmzeile 10 die zweite Regel angewendet und $AP(2, 0)$ in $AP(1, 1)$ überführt. Die erste Regel, und somit Programmzeile 8, findet Anwendung wenn der vorletzte Wert 0 ist. In diesem Fall wird nur der letzte Wert plus 1 auf den Stack abgelegt.
Auch wenn $WHILE$-berechenbare Programme keine rekursiven Funktionsaufrufe zulassen, kann so die Rekursion simuliert werden. Anstatt die Funktion mit den entsprechenden Parametern neu aufzurufen, wird der bisherige Rechenfortschritt in einem Stack persistiert und der selbe Algorithmus nochmals durchlaufen.
Fazit
$WHILE$-Programme stellen trotz ihrer Einschränkungen eine gute Möglichkeit dar Turing-berechenbare Funktionen zu lösen. Die fehlende Rekursion kann relativ einfach durch einen Stack implementiert werden. Zudem sind $WHILE$-Programme gegenüber dem formellastigen Modell der Turing-Maschine sehr übersichtlich. Der Quellcode wirkt dabei eher selbsterklärend.
Mehrband-Turing-Maschinen
Das Modell der Mehrband-Turing-Maschinen ist ein weiteres im Unterricht behandeltes Berechnungsmodell der theoretischen Informatik. Dies erweitert sozusagen die "simplen" Turing-Maschinen um weitere Bänder. Für die Verarbeitung steht hier nicht ein, sondern mehrere Bänder zur Verfügung. Bei der Abarbeitung der Maschine werden alle Bänder eingelesen und entsprechend des Überganges auf jedes Band geschrieben. Der Lesekopf jedes Bandes kann sich nach dem Schreiben unabhängig voneinander nach links oder rechts bewegen beziehungsweise auf der Position verharre.
Dieses Modell ist relativ ähnlich zu den Mehrspur-Turing-Maschinen. Der Unterschied ist lediglich, das sich bei Mehrspur-Turing-Maschinen nur ein Lesekopf über ein Band bewegt, dieser aber von allen Spuren auf seiner Position liest beziehungsweise auf alle Spuren schreiben kann. Im folgenden wird das Prinzip der Mehrspur-Turing-Maschine an einem Übungsbeispiel erläutert.
binäre Addition durch Mehrspur-Turing-Maschine
Als einfache Aufgabe soll eine Mehrspur-Turing-Maschine implementiert werden, welche 2 binäre Zahlen addiert und das Ergebnis dabei auf die erste Spur schreibt. Für diese Aufgabe müssen nicht mehrere separate Bänder Verwendung finden, da sowieso immer die übereinander stehenden Stellen addiert werden. Ein Übertrag auf die nächste Stelle kann durch den Wechsel in einen entsprechenden Zustand vermerkt werden. Zudem rechnet die Maschine, da wir von der niedrigsten Stelle auf der linken Seite ausgehen, von links nach rechts. Um dies zu ändern muss aber nur die Startposition und die Richtung in den Übergängen geändert werden.
Die Maschine ist dafür wie folgt definiert: $$M = (\{q_0, q_1, q_2, q_3\}, \{0, 1\}, \{$, 0, 1\}, \delta, q_0, $, \{q_3\}) $$
Mit der Überführungsfunktion $\delta$ welche definiert ist durch folgende Tabelle:
| $\delta$ | $0;0$ | $0;1$ | $1;0$ | $1;1$ | $\$;\$$ |
| $q_0$ | $(q_1;0;0;R)$ | $(q_1;1;0;R)$ | $(q_1;1;0;R)$ | $(q_2;0;0;R)$ | $(q_3;\$;\$;N)$ |
| $q_1$ | $(q_1;0;0;R)$ | $(q_1;1;0;R)$ | $(q_1;1;0;R)$ | $(q_2;0;0;R)$ | $(q_3;\$;\$;N)$ |
| $q_2$ | $(q_1;1;0;R)$ | $(q_2;0;0;R)$ | $(q_2;0;0;R)$ | $(q_2;1;0;R)$ | $(q_3;1;\$;N)$ |
| $q_3$ | - | - | - | - | - |
$q_0$ repräsentiert dabei den Startzustand. In $q_1$ und $q_2$ werden die Stellen bei jedem Schritt addiert, wobei der Zustand $q_2$ bedeutet, das ein Übertrag entstand und sobald als möglich mit verrechnet werden muss. Die Maschine ist prinzipiell nach diesem Schema auch für größere Zahlensysteme anwendbar, wenn sie um die entsprechenden Zustände erweitert wird.
Akzeptanz einer Sprache durch Mehrband-Turing-Maschine
Im nächsten Beispiel sollen Worte der Sprache $L$ akzeptiert werden. Diese ist definiert durch $L = \{ w | w = 0^m 1^m, m \in \N \}$. Das heißt nichts anderes als das die Maschine in einem Endzustand stoppen soll, wenn auf dem Eingabeband einer bestimmten Anzahl Nullen die selbe Anzahl Einsen folgt. Hierfür wird ein 2. Band verwendet, um, wie in einem Kellerspeicher oder auch Stack, die Anzahl der Nullen abzulegen.
Die Maschine ist wie folgt Definiert:
$$M = (\{q_0, q_1, q_2, q_3\}, \{0, 1\}, \{$, 0, 1\}, \delta, q_0, $, \{q_3\}) $$
Mit der Überführungsfunktion $\delta$ welche definiert ist durch folgende Tabelle:
| $\delta$ | $0;\$$ | $1;\$$ | $1;0$ | $\$;\$$ |
| $q_0$ | $(q_0;0;0;R;R)$ | $(q_1;1;\$;N;L)$ | - | - |
| $q_1$ | - | - | $(q_2;1;\$;R;L)$ | - |
| $q_2$ | - | - | $(q_2;1;\$;R;L)$ | $(q_3;\$;\$;N;N)$ |
| $q_3$ | - | - | - | - |
In Zustand 1 werden zunächst auf das 2. Band genau so viele Nullen geschrieben, wie sich auf Band 1 befinden. Dies wird so lange gemacht, bis die erste 1 erreicht ist. Von nun an geht der Kopf auf Band 1 weiter nach rechts und liest die aufeinander folgenden Einsen ein, während der Kopf auf Band 2 zurück geht und wieder alle Nullen mit dem Vorbelegungszeichen überschreibt. Dies wird so lange wiederholt, bis auf Band 1 das Vorbelegungszeichen erreicht und auf Band 2 alle Nullen entfernt sind. Falls das Eingabewort keine valide Form hat, stoppt die Maschine in keinem Endzustand.
Fazit
Mehrband- und Mehrspur-Turing-Maschinen stellen neben den normalen Turing-Maschinen eine große Vereinfachung dar. So kann man viele Aufgaben in weniger Schritten erledigen und muss nicht das Eingabewort verändern. Auch zum Zwischenspeichern von Werten sind weitere Bänder gut. Da sie die selbe Menge von Funktionen beschreiben können, ist es in manchen Fällen praktisch eine solche Maschine zu entwerfen um für ein Problem die Turing-berechenbarkeit nachzuweisen. Zudem lassen sich auch Mehrband- und Mehrspur-Turing-Maschinen direkt ineinander umwandeln.
Registermaschinen
Registermaschinen kommen den heutigen PC's und damit der Von-Neumann-Architektur am nächsten. Diese beinhalten folgenden Komponenten
- Speicher
- Der Speicher der Registermaschinen wird durch eine unbegrenzte Anzahl von durchnummerierten Registern dargestellt. Auf diese kann wahlfrei zugegriffen werden. Die Register sind definiert durch $c(i)$ wobei $i$ die Nummer des Registers ist. Das erste Register $c(0)$ wird bei Rechen- und Vergleichsoperationen verwendet und übernimmt damit die Funktion eines Akkumulators. Zum Start der Maschine sind alle Registerinhalte nicht definiert.
- Befehlszähler
- Die Variable $b$, meist dargestellt als ein Register, beinhaltet die aktuelle Position im Programmablauf. Bei jedem Befehl wird diese Variable inkrementiert. Eine Ausnahme sind Wertzuweisungen in dieses Register (GOTO Programmzeile).
- Programm
- Dies ist die eigentliche Befehlsfolge, welche durch die Maschine abgearbeitet wird. Es ist eine endliche, über $b$ durchnummerierte Folge von Anweisungen. Beim Starten der Maschine wird mit dem ersten Befehl begonnen und die Abarbeitung endet erst wenn ein END Befehl erreicht wird. Die Menge der Befehle ist relativ minimalistisch gehalten, aber je nach Publikation immer noch recht unterschiedlich. Allerdings lässt sich die Menge auf ein Minimum herunter brechen. Falls für einen besseren Komfort weitere Befehle benötigt werden, können diese aus den Grundbefehlen leicht gebildet werden.
- Ein- und Ausgabeband
- In diesen 2 Bändern ($e$ und $a$) wird, wie der Name schon sagt, die Ein- und Ausgabe abgelegt. Diese können jeweils nur, Zelle für Zelle, gelesen beziehungsweise geschrieben werden. Zudem kann der Schreib- und Lesekopf nur in einer Richtung bewegt werden. In manchen Beschreibungen dieses Modells ist dieser Teil nicht enthalten. Bei Ihnen sind die Parameter in den Registern abgelegt, beginnend mit $c(1)$, und das Ergebnis wird in $c(0)$ abgelegt. Allerdings wird im folgenden auf Registermaschinen mit Ein- und Ausgabeband eingegangen da diese auch der Von-Neumann-Architektur und damit den PC's näher sind.
- Konfiguration
- Alle Zustände einer Registermaschine sind in Konfigurationen $K$ hinterlegt. Diese beinhaltet ein Tupel aus $(b, c, e, a)$ wobei $b$ die aktuelle Position im Programm, $c$ eine partielle Abbildung der Register mit $c:\N\rightarrow\N$, $e$ das Eingabeband mit der aktuellen Lesekopfposition und $a$ das Ausgabeband mit der aktuellen Schreibkopfposition ist.
Jede Registermaschine hat zudem einen Startzustand $S$ mit $(1, n.d., e, \varepsilon), e \in \{1, 2, ..., 0\}^*$ sowie einen Endzustand bei welchem b auf ein END zeigt und $a$ die Ausgabe beinhaltet.
| Befehl | Erläuterung |
|---|---|
| read | liest den Wert von $e_i$ in $c(0)$ und rückt den Lesekopf auf Position $i+1$ |
| write | schreibt den Wert von $c(0)$ auf $a_j$ und rückt den Schreibkopf auf Position $j+1$ |
| load $k$ | schreibt den Wert aus Register $c(k)$ in das Register $c(0)$ |
| store $k$ | schreibt den Wert von Register $c(0)$ in das Register $c(k)$ |
| cload $k$ | schreibt den Wert $k$ in das Register $c(0)$ |
| add $k$ | $c(0) = c(0) + c(k)$ |
| sub $k$ | $c(0) = max\{c(0) - c(k), 0\}$ss |
| goto $k$ | Schreibt den Wert k in den Befehlszähler und springt in die entsprechende Programmzeile |
| jumpzero $k$ | IF $c(0)==0$ THEN $b = k$ ELSE $b = b + 1$ |
| end | beendet den Programmablauf beziehungsweise stoppt die Maschine |
Multiplikation mit einer Registermaschine
Mit der folgenden Registermaschine sollen 2 Werte des Eingabebandes miteinander multipliziert werden.
1 cload 1 2 store 4 3 read 4 store 1 5 read 6 jumpzero 12 7 store 2 8 load 3 9 add 1 10 store 3 11 load 2 12 sub 1 13 goto 4 14 load 3 15 write 16 end
Zunächst wird in das Register 4 der Wert 1 geschrieben. Dieser wird später zum dekrementieren des Zählers benötigt. Der erste Parameter wird vom Eingabeband als Multiplikand in das Register 1 geladen. Der zweite Parameter verbleibt zunächst als Zählervariable im Akkumulator. Im folgenden wird nun bei jedem Schleifendurchlauf der Zähler minus 1 gerechnet und der Multiplikand zum bisherigen Produkt addiert. Dies geschieht so lang, bis der Zähler 0 ist. Während der Abarbeitung stehen im Register 2 die Zählervariable und in Register 3 das bisherige Zwischenergebnis.
Fazit
Wer schon ein mal Assembler programmiert hat, benötigt nicht lange um sich in diese Darstellungsform einzuarbeiten. Sie ist an der Programmierung eines PC's am nächsten. Zudem steht sie eher zwischen dem hardwarenahen und programmatischen Ansatz. Ein Nachteil dieses Modells ist sicherlich, das nur mit dem Akkumulator gearbeitet werden kann. Durch geschicktes Arbeiten mit den Registern und eine übersichtliche Arbeitsweise kann man dem allerdings gut entgegenwirken. Zudem kann man sich Hilfsfunktionen, den Makros in Assembler ähnlich, definieren, welche beim erstellen eines Modells helfen.
