TI: Beweis der Addition zweier Register mit einer Registermaschine

Um zu zeigen, dass eine Zahlenfunktion berechenbar ist muss man nachweisen, dass man die Funktion mit der allgemeinen Maschine berechnen und die komplexen Funktionen und Tests der allgemeine Registermaschine dann durch eine normale Registermaschine  ausdrücken kann (die korrekte Funktion dieser vorausgesetzt bzw. bewiesen). Auch müssen die im Flussdiagramm vorkommenden Tests rekursiv, d.h. entscheidbar sein. Wir kümmern uns hier um Ersteres. Der Umweg über die allgemeine Registermaschine wird gegangen um sich die Schreibarbeit der komplexen Funktionen nur einmal machen zu müssen. Hat man z.B. die Multiplikation als komplexe Operation mit einer normalen Registermaschine (nur mit den Operationen Addition/Subtraktion, arithmetische Differenz und Test auf 0) bewiesen, kann man diese ab sofort in seiner allgemeinen Registermaschine nutzen.

Formal definiert bedeutet es, dass eine Funktion $f : \subseteq \mathbb{N}^k \rightarrow \mathbb{N}$ dann berechenbar ist, genau dann wenn es eine k-stellige Registermaschine gibt mit $f = f_M$.Bei  $f_M(Eingabe) = x$ ist x hierbei das Ergebnis welches nach einem Durchlauf (man ist bei HALT gelandet oder wenn es kein Ende gibt bei $div$) der Registermaschine (das als Flussdiagramm dargestellt ist) in Register $R_0$ steht. Informal ausgedrückt bedeutet es, dass die Funktion $f$ durch Maschine $M$ berechnet werden kann und die Ergebnisse für jede Eingabe für $f$ und $f_M$ gleich sind: eben $f = f_M$.

Nehmen wir als Beispiel die Addition von zwei Registern $R_1$ und $R_2$ durch eine allgemeine Registermachine. Sie berechnet das Ergebnis und legt es dann im Ergebnisregister $R_0$ ab. Hier das zugehörige und unglaublich komplexe Flussdiagramm dazu.

Da es eine komplexe Funktion ist müssen wir sie jedoch mit einer normalen Registermaschine und den drei erlaubten Operationen (Addition und Subtraktion von$1$, sowie Test auf $0$) abbilden und zeichnen uns hierzu ein passendes Flussdiagramm. Dieses ist nur unwesentlich komplexer.

Umgangssprachlich macht die normale Registermaschine folgendes: die inkrementiert das Register $R_0$ zunächst genau $R_1$ mal und dekrementiert $R_1$ bei jedem Durchlauf der ersten Schleife ($p \rightarrow q \rightarrow e$). Anschließend wird es in Block $p$ wieder auf 0 geprüft. Sollte das Register $R_1$ tatsächlich 0 sein, bewegen wir uns dann zum Block $s$ um in der zweiten Schleife ($s \rightarrow t \rightarrow u$) das Selbe nochmal mit Register $R_2$ zu veranstalten und $R_0$ weitere $R_2$ Mal zu inkrementieren. Damit wird $R_0$ genau $R_1 + R_2$ Mal inkrementiert und so die Addition von Register $R_1$ und $R_2$ bewerkstelligt. Einfach, nicht? Jetzt stellt sich nur die Frage, wie wollen wir die korrekte Funktionalität unserer normalen Registermaschine beweisen. Alle $\mathbb{N}$ durchtesten? Ne, lieber nicht.

Der Beweis

Der Beweis, dass die Funktion $f(x,y) = f_M(x,y) = x+y$ berechenbar ist gliedert sich selbst in folgende Schritte:

1. allgemeine Registermaschine als Flussdiagramm zeichnen, die die Funktion berechnet. Ggf. die korrekte Funktion auch mit vollständiger Induktion beweisen. Hier verzichten wir darauf, da es für das kleine Flussdiagramm oben offensichtlich ist. Ebenso ist hier darauf zu achten, dass jeder vorkommende Test entscheidbar ist.
2. alle komplexen Operationen der allgemeinen Registermaschine durch eine normale Registermaschine als Flussdiagramm ausdrücken, wo man nur die aus der Definition für normale Registermaschinen erlaubten Funktionen Addition und Subtraktion von $1$, sowie Test auf $0$ durchführen darf. Auch hier bitte auf entscheidbare Tests achten.
3. nun hat man für jede komplexe Operation ein Flussdiagramm, deren korrekte Funktion man mit vollständiger Induktion beweisen muss.

Das Flussdiagramm aus Schritt 2 ist oben dargestellt. Da wir nur eine komplexe Operation (die Addition) haben, haben wir nur ein Flussdiagramm für eine normale Registermaschine. Man überzeuge sich, dass nur die erlaubten 3 Operationen benutzt werden. Überzeugt? Gut! Fangen wir mit dem Induktionsbeweis an.

Wir prüfen zunächst de Fälle, die wir als Eingabe haben und leiten hieraus die Induktionsbehauptungen ab:

Wir möchten jede natürliche Zahl ($\mathbb{N}$) addieren können. Im Endeffekt sind diese dann fest und wir haben nur eine unterschiedliche Anzahl an Einzelschritten, die wir durch das Programm gehen müssen bis das Ergebnis im Register $R_0$ steht. Abhängig von den Eingabewerten. Da wir zwei Schleifen haben, können wir für diese auch zwei Induktionsbehauptungen aufstellen.

Man sieht leicht, dass wir die erste Schleife genau $R_1$ Mal durchlaufen und wieder in Block $p$ landen. Ist z.B. $R_1 := 1$, so sind 3 Einzelschritte notwendig bis wir $R_1 = x$ erneut auf 0 testen und die Schleife verlassen. Das als Registerbelegung erwartete Gesamtergebnis ist also $(p,(i,x-i,y,0,...)$, wobei $i$ die Anzahl der Schleifendurchläufe und somit auch die Anzahl der Inkrementierungen von $R_0$ (eben $i$ im Ergebnis) und Dekrementierungen von $R_1$ (eben $x-i$ im Ergebnis) ist. Der Rest bleibt unangetastet ($y$ und $0$) Damit ergibt sich schon die erste Induktionsannahme in Abhängigkeit von x:

$ES^{3i}(p,(0,x,y,0,...) = (p,(i,x-i,y,0,...)$

Das Ergebnis ist so wie wir gewollt haben: ist $x := 1$, so haben wir nur einen Schleifendurchlauf, genau 3 Einzelschritte und am Ende die Registerbelegung $(i,x-i,y,0,...)$ und wir landen wieder im Block $p$. Ist $i = 2$, so haben wir zwei Schleifendurchläfe, somit 6 Einzelschritte und landen wieder bei $p$. Die Behauptung scheint also korrekt. Fehlt nur noch der Induktionsbeweis für den Dominoeffekt damit wir nicht unendlich viele Fälle durchtesten müssten.

Wir führen für die oben aufgestellte

Annahme: $ES^{3i}(p,(0,x,y,0,...)$ = $(p,(i,x-i,y,0,...))$

einen Induktionsbeweis über $i$ durch. Zu beweisen ist:

Behauptung: $ES^{3(i+1)}(p,(0,x,y,0,...) = (p,((i+1),x-(i+1),y,0,...)$

der Einfachheit halber ausrechnen:

$ES^{3i+3}(p,(0,x,y,0,...) = (p,(i+1,x-i-1,y,0,...)$

D.h. am Ende unseres Beweises muss $(p,(i+1,x-i-1,y,0,...))$ rauskommen. Wir fangen also an:

$ES^{3i+3}(p,(0,x,y,0,...) = ES^{3}$$(p,(i,x-i,y,0,...)$ (wir setzen hier den rechten Teil der Annahme von oben als "Induktionsschritt" ein, mit $ES^3$ haben wir unser "+1" um es mal nicht unbedingt formal korrekt auszudrücken und spielen jetzt das Flussdiagramm durch)

= $ES^2(q,(i,x-i,y,0,...))$ (nun sind wir in Block q)

= $ES(r,(i+1,x-i,y,0,...))$ (nun sind wir in Block r)

= $(p,(i+1,x-i-1,y,0,...))$ (am Ende sind wir in Block p)

Und siehe da: das Ergebnis entspricht dem rechten Teil der Behauptung. Damit haben wir die Schleife bewiesen.

Fehlt uns noch die Annahme für die andere Schleife. Diese ist analog zur ersten Schleife herauszufinden. Wir starten bei Block $s$ und haben die Eingabe $(x,0,y,0,...)$, da wir x bereits aus der vorhergehenden Schleife wissen, $R_1$ aufgrund der Dekrementierung auf $0$ ist und somit nur noch $R_2 = y$ verbleibt, was wir in dieser Schleife genau $R_1 = y$ Mal dekrementieren und $R_0 = x$ somit um die gleiche Anzahl inkrementieren. Wir haben hier ebenfalls drei Schritte bis wir wieder in Block $s$ angekommen sind. Als Ergebnis erwarten wir somit wieder in Block $s$ zu sein und folgende Registerbelegung zu haben: $(x+i, 0, y-i, 0, ...)$, da $i$ genau die Anzahl ist, die wir die Schleife durchlaufen und $y$ dekrementiert und $x$ inkrementiert haben. Hier ist dann auch schon die Annahme: $ES^{3i}(s,(x,0,y,0,...) = (s,(x+i,0,y-i,0,...))$. Für diese führen wir nun den Induktionsbeweis über $i$ durch:

Annahme: $ES^{3i}(s,(x,0,y,0,...) =$ $(s,(x+i,0,y-i,0,...))$

Zu beweisen ist die Behauptung:

$ES^{3(i+1)}(s,(x,0,y,0,...) = (s,(x+(i+1),0,y-(i+1),0,...))$

Auch hier einfach ausrechnen:

$ES^{3i+3}(s,(x,0,y,0,...) = (s,(x+i+1,0,y-i-1,0,...))$

D.h. am Ende unseres Beweises muss $(s,(x+i+1,0,y-i-1,0,...))$ rauskommen.

Wir fangen an:

$ES^{3i+3}(s,(x,0,y,0,...) = ES^{3}$$(s,(x+i,0,y-i,0,...))$ (wieder den rechten Teil der Annahme einsetzen und ab jetzt das Diagramm durchspielen)

= $ES^{2}(t,(x+i,0,y-i,0,...))$ (nun sind wir in Block t)

= $ES(t,(x+i+1,0,y-i,0,...))$ (nun sind wir in Block u)

= $(s,(x+i+1,0,y-i-1,0,...))$ (nun sind wir an Ende wieder in Block s)

Und auch hier: das Ergebnis entspricht dem rechten Teil der Behauptung. Damit haben wir auch die zweite die Schleife bewiesen.

Die Fälle für $i = 0$ (d.h. man springt im Flussdiagramm direkt durch bis zum $HALT$) habe ich ausgelassen, da sie durch einfaches Ausrechnen offensichtlich sind. Durch die drei Schritte (Flussdiagramm einer allgemeinen Maschine erstellen, Flussdiagramm einer normale Maschine für jede in der allgemeinen Maschine verwendete komplexe Funktion erstellen, Beweis der Korrektheit der normalen Maschinen durch vollständige Induktion) haben wir bewiesen, dass unsere allgemeine Maschine $M$ die Funktion $f(x,y) = x+y$ berechnet. Damit gilt $f_M = f$.

Wie immer: bei Fehlern bitte Bescheid geben.

Buchempfehlung

Datum: 5. Oktober 2012
Kategorie: Theoretische Informatik
Kommentarfeed: RSS 2.0 • Trackback: Trackback-Url