BuK/IIm12/BuK-Übung09

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
== 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.

<code id="simareic_ap_funktion" rows="9">
(define AP
  (lambda (x y)
  (if (= x 0)
      (+ y 1) 
      (if (= y 0)
          (AP (- x 1)1) 
          (AP (- x 1) (AP x (- y 1)))
          )
      )))
</code>

<run id="simareic_ap_funktion">
(AP 3 2)
</run>

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

Diese Funktionen lassen sich in einem WHILE-Programm implementieren und stehen daher für den späten 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 = e(c(n_k, n))$$

==== AP-Funktion mit Stack ====

Nun kann man einen Stack verwenden um die AP-Funktion in einem WHILE-Programm zu implementieren. 

<code id="simareic_ap_funktion2" rows="4">
INIT;
PUSH(x);
PUSH(y);
WHILE size != 1 DO
  y = POP;
  x = POP;
  IF x = 0 THEN
    PUSH(y+1);
  ELSE IF y = 0 THEN
    PUSH(x-1); PUSH(1);
  ELSE
    PUSH(x-1); PUSH(x); PUSH(y-1);
  END
END
x0 = POP;
</code>

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.
<code id="simareic_ap_aufschrieb" rows="10">
AP(2, 2)
AP(1, AP(2, 1))
AP(1, AP(1, AP(2, 0)))
AP(1, AP(1, AP(1, 1)))
AP(1, AP(1, AP(0, AP(1, 0))))
AP(1, AP(1, AP(0, AP(0, 1))))
AP(1, AP(1, AP(0, 2)))
AP(1, AP(1, 3))
AP(1, AP(0, AP(1, 2)))
AP(1, AP(0, AP(0, AP(1, 1))))
AP(1, AP(0, AP(0, AP(0, AP(1, 0)))))
AP(1, AP(0, AP(0, AP(0, AP(0, 1)))))
AP(1, AP(0, AP(0, AP(0, 2))))
AP(1, AP(0, AP(0, 3)))
AP(1, AP(0, 4))
AP(1, 5)
AP(0, AP(1, 4))
AP(0, AP(0, AP(1, 3)))
AP(0, AP(0, AP(0, AP(1, 2))))
AP(0, AP(0, AP(0, AP(0, AP(1, 1)))))
AP(0, AP(0, AP(0, AP(0, AP(0, AP(1, 0))))))
AP(0, AP(0, AP(0, AP(0, AP(0, AP(0, 1))))))
AP(0, AP(0, AP(0, AP(0, AP(0, 2)))))
AP(0, AP(0, AP(0, AP(0, 3))))
AP(0, AP(0, AP(0, 4)))
AP(0, AP(0, 5))
AP(0, 6)
 = 7
</code>

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:
$$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:

{| class="wikitable"
|-
| $\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$ 
|style="text-align:center"|	        -   
|style="text-align:center"|             -	 
|style="text-align:center"|             -	 
|style="text-align:center"|             -	 
|style="text-align:center"|             -
|}

$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:
{| class="wikitable"
|-
| $\delta$ || $0;\$$          ||          $1;\$$	||        $1;0$      ||	$\$;\$$
|-
| $q_0$ 
||	$(q_0;0;0;R;R)$  
||  $(q_1;1;\$;N;L)$ 
|style="text-align:center"|	- 
|style="text-align:center"|     -
|-
| $q_1$ 
|style="text-align:center"|	- 
|style="text-align:center"|	- 
||	$(q_2;1;\$;R;L)$ 
|style="text-align:center"|     -
|-
| $q_2$ 
|style="text-align:center"|	- 
|style="text-align:center"|	- 
||	$(q_2;1;\$;R;L)$ 
||	$(q_3;\$;\$;N;N)$
|-
| $q_3$
|style="text-align:center"|	     -   
|style="text-align:center"|             -	 
|style="text-align:center"|             -	 
|style="text-align:center"|             -
|}

In Zustand 1 werden zunächst auf das 2. Band genau so viele 0en geschrieben, wie sich auf Band 1 befinden. Dies wird so lang 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 lang 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.