BuK-Übung09

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 3 Beweise demonstriert, welche allerdings jeweils eine Bedingung mit sich bringen.

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 und Turing-berechenbar ist, 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

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 lang 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.

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 Maschiene, 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:

Mit der Überführungsfunktion \delta welche definiert ist durch folgende Tabelle:

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 eine 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 0en die selbe Anzahl 1en folgt. Hierfür wird ein 2. Band verwendet, um wie in einem Kellerspeicher oder Stack die Anzahl der Nullen abzulegen.

Die Maschine ist wie folgt Definiert:

Mit der Überführungsfunktion \delta welche definiert ist durch folgende Tabelle: