Das Flussdiagramm aus Schritt 2 ist oben dargestellt. Da wir nur eine komplexe Operation (die Addition) haben, haben wir nur ein Flussdiagramm f\u00fcr eine normale Registermaschine. Man \u00fcberzeuge sich, dass nur die erlaubten 3 Operationen benutzt werden. \u00dcberzeugt? Gut! Fangen wir mit dem Induktionsbeweis an.<\/p>\n
Wir pr\u00fcfen zun\u00e4chst de F\u00e4lle, die wir als Eingabe haben und leiten hieraus die Induktionsbehauptungen ab:<\/p>\n
Wir m\u00f6chten jede nat\u00fcrliche Zahl (\\(\\mathbb{N}\\)) addieren k\u00f6nnen. Im Endeffekt sind diese dann fest und wir haben nur eine unterschiedliche Anzahl an Einzelschritten, die wir durch das Programm gehen m\u00fcssen bis das Ergebnis im Register \\(R_0\\) steht. Abh\u00e4ngig von den Eingabewerten. Da wir zwei Schleifen haben, k\u00f6nnen wir f\u00fcr diese auch zwei Induktionsbehauptungen aufstellen.<\/p>\n
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\u00e4ufe 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\u00e4ngigkeit von x:<\/p>\n\\(ES^{3i}(p,(0,x,y,0,…) = (p,(i,x-i,y,0,…)\\)\n
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\u00e4fe, somit 6 Einzelschritte und landen wieder bei \\(p\\). Die Behauptung scheint also korrekt. Fehlt nur noch der Induktionsbeweis f\u00fcr den Dominoeffekt damit wir nicht unendlich viele F\u00e4lle durchtesten m\u00fcssten.<\/p>\n
Wir f\u00fchren f\u00fcr die oben aufgestellte<\/p>\n
Annahme: \\(ES^{3i}(p,(0,x,y,0,…)\\) = \\((p,(i,x-i,y,0,…))\\)<\/span><\/p>\neinen Induktionsbeweis \u00fcber \\(i\\) durch. Zu beweisen ist:<\/p>\n
Behauptung: \\(ES^{3(i+1)}(p,(0,x,y,0,…) = (p,((i+1),x-(i+1),y,0,…)\\)<\/p>\n
der Einfachheit halber ausrechnen:<\/p>\n\\(ES^{3i+3}(p,(0,x,y,0,…) = (p,(i+1,x-i-1,y,0,…)\\)\n
D.h. am Ende unseres Beweises muss \\((p,(i+1,x-i-1,y,0,…))\\)<\/span> rauskommen. Wir fangen also an:<\/p>\n\\(ES^{3i+3}(p,(0,x,y,0,…) = ES^{3}\\)\\((p,(i,x-i,y,0,…)\\)<\/span> (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\u00fccken und spielen jetzt das Flussdiagramm durch)<\/p>\n= \\(ES^2(q,(i,x-i,y,0,…))\\) (nun sind wir in Block q)<\/p>\n
= \\(ES(r,(i+1,x-i,y,0,…))\\) (nun sind wir in Block r)<\/p>\n
= \\((p,(i+1,x-i-1,y,0,…))\\)<\/span> (am Ende sind wir in Block p)<\/p>\nUnd siehe da: das Ergebnis entspricht dem rechten Teil der Behauptung. Damit haben wir die Schleife bewiesen.<\/p><\/blockquote>\n
Fehlt uns noch die Annahme f\u00fcr 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\u00fcr diese f\u00fchren wir nun den Induktionsbeweis \u00fcber \\(i\\) durch:<\/p>\n
Annahme: \\(ES^{3i}(s,(x,0,y,0,…) =\\) \\((s,(x+i,0,y-i,0,…))\\)<\/span><\/p>\nZu beweisen ist die Behauptung:<\/p>\n\\(ES^{3(i+1)}(s,(x,0,y,0,…) = (s,(x+(i+1),0,y-(i+1),0,…))\\)\n
Auch hier einfach ausrechnen:<\/p>\n\\(ES^{3i+3}(s,(x,0,y,0,…) = (s,(x+i+1,0,y-i-1,0,…))\\)\n
D.h. am Ende unseres Beweises muss \\((s,(x+i+1,0,y-i-1,0,…))\\)<\/span> rauskommen.<\/p>\nWir fangen an:<\/p>\n
\\(ES^{3i+3}(s,(x,0,y,0,…) = ES^{3}\\)\\((s,(x+i,0,y-i,0,…))\\)<\/span> (wieder den rechten Teil der Annahme einsetzen und ab jetzt das Diagramm durchspielen)<\/p>\n\\(=ES^{2}(t,(x+i,0,y-i,0,…))\\) (nun sind wir in Block t)
\n\\(=ES(t,(x+i+1,0,y-i,0,…))\\) (nun sind wir in Block u)
\n\\(=(s,(x+i+1,0,y-i-1,0,…))\\)<\/span> (nun sind wir an Ende wieder in Block s)<\/p>\nUnd auch hier: das Ergebnis entspricht dem rechten Teil der Behauptung. Damit haben wir auch die zweite die Schleife bewiesen.<\/p><\/blockquote>\n
Die F\u00e4lle f\u00fcr \\(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\u00fcr jede in der allgemeinen Maschine verwendete komplexe Funktion erstellen, Beweis der Korrektheit der normalen Maschinen durch vollst\u00e4ndige Induktion) haben wir bewiesen, dass unsere allgemeine Maschine \\(M\\) die Funktion \\(f(x,y) = x+y\\) berechnet. Damit gilt \\(f_M = f\\).<\/p>\n
Wie immer: bei Fehlern bitte Bescheid geben.<\/p>\n","protected":false},"excerpt":{"rendered":"
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\u00fccken kann (die korrekte Funktion dieser vorausgesetzt bzw. bewiesen). Auch m\u00fcssen die im Flussdiagramm vorkommenden Tests rekursiv, d.h. entscheidbar sein. Wir … <\/p>\n
\u201eTI: Beweis der Addition zweier Register mit einer Registermaschine\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-515","post","type-post","status-publish","format-standard","hentry","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/515","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=515"}],"version-history":[{"count":47,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/515\/revisions"}],"predecessor-version":[{"id":3499,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/515\/revisions\/3499"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=515"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=515"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
![\"\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/10\/RGmulti.png\" "\\"RGmulti\\"")
<\/a><\/p>\n