{"id":1047,"date":"2012-12-04T11:11:00","date_gmt":"2012-12-04T09:11:00","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1047"},"modified":"2025-11-25T22:44:06","modified_gmt":"2025-11-25T21:44:06","slug":"ti-utm-stm-und-phi-theorem-lernziele-ke5","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1047","title":{"rendered":"TIA: smn-Theorem, Rekursions- und \u00c4quivalenzsatz (Lernziele KE5, 3\/3)"},"content":{"rendered":"<p><strong>Update<\/strong>: Formulierungen etwas verst\u00e4ndlicher gemacht. Wenn euch das smn-Theorem noch nicht ganz klar, war bitte den Beitrag nochmal lesen.<\/p>\n<p><strong>Update<\/strong>: aus zwei macht drei. Das ist nun hoffentlich der letzte Teil zu KE5 mit einem riesen Beispiel zum smn-Theorem.<\/p>\n<p>Noch einmal die Wiederholung der zwei Anforderungen an vern\u00fcnftige Programmiersprachen:<\/p>\n<blockquote>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><strong>(U)<\/strong> Es soll einen Computer geben, der zu jedem Programm \\(P\\) und jedem m\u00f6glichen Eingabewert \\(x\\) das Resultat \\(\\sigma(P)(x)\\) berechnet und nicht h\u00e4lt wenn\u00a0\\(\\sigma(P)(x)\\) nicht existiert.<\/li>\n<li><strong>(S)<\/strong> Zu je zwei Programmen \\(P\\) und \\(Q\\) m\u00f6chte man ein Programm f\u00fcr die Komposition konstruieren k\u00f6nnen, d.h. es soll eine berechenbare Funktion \\(h\\) geben, so dass \\(\\sigma(h(P,Q)=\\sigma(Q) \\circ\\sigma(P)\\).<\/li>\n<\/ul>\n<\/blockquote>\n<p>W\u00e4hrend wir<strong> (U)<\/strong> mit dem utm-Theorem gut behandeln konnten, schauen wir uns jetzt <strong>(S)<\/strong> an:<\/p>\n<h2>Lernziel 5<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erkl\u00e4rung und Anwendung des <strong>smn-Theorems<\/strong><\/em><\/p>\n<p>Kommen wir nun zum smn-Theorem, unserem \u00dcbersetzungslemma. Formal ausgedr\u00fcckt:<\/p>\n<blockquote><p>\\(f \\in P^{(2)}\\), dann gibt es eine total-rekursive Funktion \\(r \\in R^{(1)}\\) mit:<\/p>\n<p>\\(f(i,j) = \\varphi_{r(i)}(j)\\) f\u00fcr alle \\(i,j \\in \\mathbb{N}\\).<\/p><\/blockquote>\n<p>Ehm, ja. Was macht das Ding nun?<\/p>\n<p>Im wesentlichen geht es darum, dass sich berechenbare Funktionen kombinieren lassen. Durch die Hintereinanderausf\u00fchrung lassen sich neue Funktionen und somit auch neue Programme (und damit selbstverst\u00e4ndlich auch neue Maschinen) mit eigenen G\u00f6delnummern \\(i\\) erschaffen.<\/p>\n<p>Dazu werden die Funktionen einfach hintereinander ausgef\u00fchrt und die Variable \\(x\\) als Eingabe immer wieder von Maschine zu Maschine &#8222;mitgenommen&#8220;. Da bei diesem Vorgang, abh\u00e4ngig von der konkreten Belegung der Variable \\(x\\) eine neue Maschine erschaffen wird, gibt uns unsere Funktion \\(r\\) diese neue G\u00f6delnummer preis. In dieser Maschine ist die Variable \\(x\\) konkret belegt und fixiert. Variable \\(j\\) nimmt sie jedoch ganz normal an.<\/p>\n<p>Dadurch ist es m\u00f6glich aus Funktionen mit mehreren Argumenten Funktionen mit nur einem Argument zu erstellen, die jedoch das selbe berechnen (<a href=\"http:\/\/de.wikipedia.org\/wiki\/Currying\">Currying<\/a> genannt). Wir &#8222;fixieren&#8220; sozusagen Argumente und codieren sie in unsere neuen Maschinen ein. Am Beispiel unten wird es etwas deutlicher.<\/p>\n<p>Zun\u00e4chst: \\(R^{(1)}\\) sind die berechenbaren, totalen, einstelligen Funktionen (sie sind \u00fcberall in \\(\\mathbb{N}\\) definiert). Die Funktionen in \\(P^{(1)}\\) m\u00fcssen nicht \u00fcberall definiert sein. Im Skript ist das in menschlicher Sprache beschrieben:<\/p>\n<blockquote><p><em>&#8222;Jedes Programm der Programmiersprache \\(\\psi\\) f\u00fcr Zahlenfunktionen mit berechenbarer, universeller Funktion kann mit der Funktion \\(r\\) in die Programmiersprache \\(\\varphi\\) \u00fcbersetzt werden&#8220;<\/em><\/p><\/blockquote>\n<p>Das trifft es eig. ganz gut. Das ist jedoch nicht direkt die Formalisierung unseres \\((S)\\), der Zusammenhang kommt aber gleich noch.<\/p>\n<p>In der <a href=\"http:\/\/de.wikipedia.org\/wiki\/Smn-Theorem\">Wikipedia<\/a> steht zum smn-Theorem auch noch folgender Satz (den ich leicht modifiziert habe damit er besser zu uns passt):<\/p>\n<blockquote><p><em>&#8222;Die smn &#8211; Eigenschaft besagt, dass es zu einem Code \\(f_M\\), der mit den Parametern \\(i\\) und \\(x\\) ausgef\u00fchrt wird (bzw. ausgef\u00fchrt werden kann), ein Transformationsprogramm \\(r\\) gibt, das aus \\(f_M\\), \\(i\\) und \\(x\\) ein Programm \\(f_{M_i}\\)\u00a0berechnet, welches bei der Eingabe von \\(x\\) das gleiche berechnet, wie \\(f_M\\) bei der Eingabe von \\(i\\) und \\(x\\)&#8222;<\/em><\/p><\/blockquote>\n<p>Ja, macht Sinn. Formal ausgedr\u00fcckt:<\/p>\n<p style=\"padding-left: 30px;\">\\(f_M(i,x)=r(f_M,i,x)=f_{M_i}(x)\\)<\/p>\n<p>(Hier sind \\(i\\) und \\(x\\) Argumente, und \\(f_M\\) die G\u00f6delnummer der Ursprungsmaschine, \\(f_{M_i}\\) ist dann die G\u00f6delnummer der Maschine mit dem festgesetzten \\(i\\)).<\/p>\n<p>Auch ist es nicht das eig. smn-Theorem, welches sonst \u00fcberall verwendet wird und die Stelligkeit \\(m + n\\) nutzt, sondern eine abgewandelte Form davon (wie vieles andere im Skript auch), damit es f\u00fcr den Leser nicht zu einfach wird und er Zusatzliteratur heranziehen kann. Wo k\u00e4men wir denn hin?!<\/p>\n<p>Als <strong>Beweis<\/strong> im Skript wird folgende Idee angebracht:<\/p>\n<p>Zun\u00e4chst machen wir uns klar, was wir suchen. Wir brauchen eine Maschine f\u00fcr unsere Funktion \\(r\\) aus der Definition.<\/p>\n<p>Wir wir oben sehen, bekommt \\(f_M\\) (also im Endeffekt die Maschine \\(M\\)) zwei Parameter \u00fcbergeben: \\(i\\) und \\(x\\). Dabei geht \\(f_M\\) hin und berechnet die Funktion (welche auch immer) mit ihren zwei Argumenten \\(i\\) und \\(x\\). Was passiert, wenn wir im ersten Schritt nun \\(i\\) in unserer neuen Maschine \\(M_i\\) festsetzen?<\/p>\n<p><strong>Beispiel<\/strong>: \\(f(i,x)=i+x\\)<\/p>\n<p style=\"padding-left: 30px;\">Um diese Funktion zu berechnen brauchen wir eine Maschine \\(M\\), die wir wie folgt definieren:<\/p>\n<p style=\"padding-left: 60px;\">\\(M=\\{F,{\\{1\\}}^*\\times {\\{1\\}}^*,{\\{1\\}}^*,EC^{(2)},AC\\}\\)<\/p>\n<p style=\"padding-left: 30px;\">Die Eingabecodierung \\(EC\\) ist:<\/p>\n<p style=\"padding-left: 60px;\">\\(EC^{(2)}(1^i,^x)=(\\epsilon,B,1^{i}B1^{x}B)\\)<\/p>\n<p style=\"padding-left: 60px;\"><strong>Konkretes Beispie<span style=\"text-decoration: underline;\">l<\/span><\/strong> f\u00fcr \\(f(2,3)\\):\u00a0\\(EC^{(2)}(11,111)=(\\epsilon,B,11B111B)\\). Auf dem Eingabeband stehen also die Eingabeparameter \\(i\\) und \\(x\\) getrennt nebeneinander rechts vom Lesekopf.<\/p>\n<p style=\"padding-left: 30px;\">Das dazugeh\u00f6rige Flussdiagramm \\(F\\) w\u00e4re:<\/p>\n<p style=\"padding-left: 30px; text-align: center;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-2259\" style=\"margin-left: 20px; margin-right: 100px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM.png\" alt=\"fiuxM\" width=\"366\" height=\"313\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM.png 610w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM-300x256.png 300w\" sizes=\"auto, (max-width: 366px) 100vw, 366px\" \/><\/a><\/p>\n<p style=\"padding-left: 30px; text-align: left;\">Ausgeschrieben sieht das Flussdiagramm also so aus, nennen wir es mal \\(\\omega\\in\\Omega^{*}\\):<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((0:1:1?,1,4)\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((1:1:R,2)\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((2:0:1,3)\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((3:0:R,0)\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((4:1:R,4)\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((5:1:1?,1,6)\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\">\\((6:HALT)\\)<\/p>\n<p style=\"padding-left: 30px; text-align: left;\">(Bitte nagelt mich nicht auf das Alphabet \\(\\Omega\\) und den korrekten Aufbau der Befehle fest, mir geht es hier nur um das Verst\u00e4ndnis)<\/p>\n<p style=\"padding-left: 30px; text-align: left;\">Was tut es? Es geht Band \\(1\\) von Anfang bis Ende durch: findet es eine \\(1\\), so schreibt es auch eine \\(1\\) auf das Ausgabeband \\(0\\). Findet es ein erstes \\(B\\) (unser Trennzeichen zwischen dem Parameter \\(1^i\\) und \\(1^x\\)) auf dem Eingabeband \\(1\\), geht es auf dem Band nach rechts und schaut ob da der zweite Parameter steht. Bis zum n\u00e4chsten \\(B\\), d.h. dem Ende des zweiten Parameters \\(1 ^x\\) wird nun in jedem Schritt eine weitere \\(1\\) auf das Ausgabeband \\(0\\) geschrieben.<\/p>\n<p style=\"padding-left: 30px; text-align: left;\"><strong>PS<\/strong>: Ihr erinnert euch an das utm-Theorem und unsere \\(h\\)-Funktion? Wir k\u00f6nnen das ausgeschriebene Programm\\(\\omega\\) (bzw. seine G\u00f6delnummer \\({\\nu_{\\Omega}}^{-1}(\\omega)\\)) und seine Eingaben auf B\u00e4nder unserer universellen Turingmaschine schreiben und es einfach simulieren. Behaltet das mal im Hinterkopf.<\/p>\n<p style=\"padding-left: 30px; text-align: left;\">Am Ende haben wir also die Ausgabe \\(f_M(1^i,1^x)=1^{f(i,x)}\\)<\/p>\n<p style=\"padding-left: 60px; text-align: left;\"><strong>Konkretes Beispiel<\/strong>:\u00a0\\(f_M(11,111)=1^5=11111\\)<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Und jetzt kommen wir zum Problem, das wir l\u00f6sen wollen: wie schaffen wir es eine Maschine anzugeben, die nur einen Parameter \\(1^x\\) hat und dennoch das gleiche Resultat berechnet?<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\(EC(1^x)=(\\epsilon,B,1^i 1^xB)\\)<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Wie k\u00f6nnen wir denn \\(1^i 1^x\\) berechnen\u00a0wenn wir gar kein \\(1^i\\) als Eingabeparameter haben?!<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Ganz einfach: wir schreiben den Parameter \\(1^i\\) auf das Eingabeband, links neben \\(1^x\\) und rechnen dann wie \\(M\\) weiter.\u00a0Nehmen wir wieder als konkrete Belegung \\(i=1^2\\) und lassen unser \\(x\\) variabel, was uns zu einer neuen Maschine \\(M_2\\) mit dem Flussdiagramm \\(F_2\\) f\u00fchrt:<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM_i22.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2265\" style=\"margin-left: 10px; margin-right: 100px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM_i22.png\" alt=\"fiuxM_i2\" width=\"359\" height=\"230\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM_i22.png 599w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/fiuxM_i22-300x192.png 300w\" sizes=\"auto, (max-width: 359px) 100vw, 359px\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Der gr\u00fcne Teil ist der zus\u00e4tzliche Part, ich nenne ihn mal \\(\\gamma_2\\) (abh\u00e4ngig von \\(i=2\\)). Schreiben wir dieses komplette Flussdiagramm \\(F_2\\) aus, so haben wir \\(\\omega_2\\) (Achtung, die Marken habe ich aus Faulheit nicht umbenannt. In Wirklichkeit m\u00fcsste man sie umbenennen, so dass das neue Flussdiagramm \\(F_2\\) auch mit Marke \\(0\\) beginnt. Ich habe f\u00fcr die Marken vor Marke \\(0\\) einfach Buchstaben genommen) als Bandprogramm:<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((A:1:L,B)\\)<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((B:1:1,C)\\)<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((C:1:L,D)\\)<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((D:1:1,E)\\)<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((E:1:L,0)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((0:1:1?,1,4)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((1:1:R,2)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((2:0:1,3)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((3:0:R,0)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((4:1:R,4)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((5:1:1?,1,6)\\)<\/p>\n<p style=\"padding-left: 60px;\">\\((6:HALT)\\)<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Nachdem der gr\u00fcne Teil des Flussdiagramms \\(\\gamma_2\\) ausgef\u00fchrt wurde haben wir auf dem Eingabeband folgende Belegung:<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((\\epsilon,B,1^{2}B1^{x}B)\\).<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Und, oh Wunder, das sieht ja genauso aus wir unsere Eingabecodierung f\u00fcr \\(1^2,1^x\\). Und schwupp, k\u00f6nnen wir ganz normal wie die urspr\u00fcngliche Maschine \\(M\\) (der wei\u00dfe Teil im Flussdiagramm) weiterrechnen.<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Wir Ihr euch leicht vorstellen k\u00f6nnt, k\u00f6nnen wir auch das f\u00fcr jedes beliebige \\(i\\) machen, indem wir den gr\u00fcnen Part \\(\\gamma\\) einfach abh\u00e4ngig von \\(i\\) zu \\(\\gamma_i\\) verl\u00e4ngern. Am Ende haben wir damit eine &#8222;Quasi-Eingangsbelegung&#8220; von:<\/p>\n<p style=\"text-align: left; padding-left: 60px;\">\\((\\epsilon,B,1^{i}B1^{x}B)\\)<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">Abh\u00e4ngig von \\(i\\) haben wir somit immer eine neues Programm \\(\\omega_i\\) mit der Maschine \\(M_i\\) inkl. &#8211; selbstverst\u00e4ndlich &#8211; auch immer einer neuen G\u00f6delnummer\u00a0\\(k={\\nu_{\\Omega}}^{-1}(\\omega_i)\\).<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">(Wiederholung: zur Funktion \\(\\nu_{\\Omega}(k)\\), welche uns zu einer G\u00f6delnummer \\(k\\) das Bandprogramm \\(\\omega\\) gibt, ist die Umkehrfunktion \\({\\nu_{\\Omega}}^{-1}(\\omega)\\). Diese gibt uns zu einem Bandprogramm \\(\\omega\\) die zugeh\u00f6rige G\u00f6delnummer \\(k\\)).<\/p>\n<p style=\"text-align: left;\">Wir haben mit unserem Verfahren also das \\(i\\) innerhalb einer Maschine quasi &#8222;fixiert&#8220;. Mit der neuen G\u00f6delnummer \\(k\\) k\u00f6nnen wir eine universelle Turingmaschine zu f\u00fcttern und sie mit nur einem Parameter \\(x\\) simulieren, so dass gilt:<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">\\(f(i,x) = \\varphi_{r(i)}(x)\\) f\u00fcr alle \\(i,x \\in \\mathbb{N}\\) bzw.<\/p>\n<p style=\"text-align: left; padding-left: 30px;\">\\(f_M(i,x)=r(f_M,i,x)=f_{M_i}(x)\\)<\/p>\n<p style=\"text-align: left;\">Und das Problem? Tja&#8230; wir brauchen ein Verfahren, dass uns dieses Flussdiagramm \\(F_i\\) und damit auch das Bandprogramm \\(\\omega_i\\) automatisch erzeugt und somit die G\u00f6delnummer \\(k={\\nu_{\\Omega}}^{-1}(\\omega_i)\\) abh\u00e4ngig von einem \\(i\\) berechnet. Dazu gehen wir wie folgt vor:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Wir basteln uns eine Maschine \\(N\\), welche auf Band \\(1\\) den Parameter \\(i\\) hat<\/li>\n<li>\\(N\\) schreibt das komplette, initiale Programm \\(\\omega\\) auf Band \\(2\\)<\/li>\n<li>Nun schreibt \\(N\\) den gr\u00fcnen Part, also das Teilprogramm (nennen wir es mal \\(\\gamma_i\\), abh\u00e4ngig vom \\(i\\) auf Band \\(3\\)<\/li>\n<li>Nun kopiert \\(N\\) das initiale Programm \\(\\omega\\) von Band \\(2\\) neben das Teilprogramm \\(\\gamma\\) auf Band \\(3\\) und benennt die Marken so um, dass die erste Marke des Teilprogramms \\(\\gamma\\) zuerst ausgef\u00fchrt wird und anschlie\u00dfend in die erste Marke vom initialen Programm \\(\\omega\\) m\u00fcndet.\n<p>Also praktisch genau das, was wir mit \\(A-E\\) gemacht haben, nur eben nicht so faul wie ich, sondern tats\u00e4chlich mit nat\u00fcrlichen Zahlen. Da das initiale Programm \\(\\omega\\) auch mit der Marke \\(0\\) anf\u00e4ngt, m\u00fcssen diese beim Kopiervorgang selbstverst\u00e4ndlich auch umbenannt werden.<\/li>\n<li>Am Ende steht auf Band \\(3\\) also ein komplett neues Programm \\(\\omega_i\\), dass wir interpretieren k\u00f6nnen.<\/li>\n<li>Der Vollst\u00e4ndigkeit halber: da wir nicht den Code, sondern die G\u00f6delnummer interpretieren, m\u00fcssen wir \\(\\omega_i\\) noch in die G\u00f6delnummer umwandeln: \\(k={\\nu_{\\Omega}}^{-1}(\\omega_i)\\)<\/li>\n<\/ul>\n<p>Damit gilt \\(f_N(1^i)=1^k\\) und wir haben unser \\(r\\) gefunden:<\/p>\n<p style=\"padding-left: 30px;\">\\(r=\\iota^{-1}(f_N(\\iota(i)))\\)<\/p>\n<p style=\"padding-left: 30px;\">PS: \\(\\iota(i)=1^i\\) und\u00a0\\(\\iota^{-1}(1^i)=i\\)<\/p>\n<p>Schon wieder diese Iotas!\u00a0Wollen wir das an dem obigen Beispiel mal durchspielen? Klar doch.<\/p>\n<p><strong>Beispiel<\/strong>: \\(N\\) f\u00fcr \\(f(i,x)=i+x\\)<\/p>\n<p style=\"padding-left: 30px;\">Wir nutzen wieder unser \\(M\\) inkl. Flussdiagramm \\(F\\) von oben f\u00fcr die Berechnung der zweistelligen Funktion \\(f\\), sowie auch das ausgeschriebene Programm \\(\\omega\\) davon.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Mit der Maschine \\(N\\) und dem Programm \\(\\omega\\) der initialen, zweistelligen Maschine \\(M\\) bekommen wir f\u00fcr \\(f_N(1^i)=1^k\\) die G\u00f6delnummer von \\(M_i\\).<\/li>\n<li>\\(r\\) w\u00e4re dann:\\(\\begin{array}{ll}r(i)&amp;={\\iota}^{-1}(f_N({\\iota}(i)))\\\\&amp;={\\iota}^{-1}(f_N(1^i))\\\\&amp;={\\iota}^{-1}(1^k)\\\\&amp;=k\\end{array}\\)<\/li>\n<li>Damit haben wir zu einem \\(i\\) die G\u00f6delnummer \\(k\\) einer Maschine, die uns zu jedem \\(x\\) die korrekte Funktion \\(\\varphi_k(x)=f(i,x)\\) berechnet.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Konkretes Beispiel? Aber sicher!<\/p>\n<p><strong>Konkretes Beispiel<\/strong>:\u00a0\\(N\\) f\u00fcr \\(f(2,3)=2+3=5\\)<\/p>\n<p style=\"padding-left: 30px;\">Die G\u00f6delnummern halte ich willk\u00fcrlich, da die konkrete Berechnung ja nicht unbedingt wichtig ist. Tun wir also einfach so, als w\u00e4re die von \\(N\\) errechnete G\u00f6delnummer von \\(M_2\\) einfach \\(k=1^44\\)<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><span style=\"line-height: 13px;\"><span style=\"line-height: 13px;\">\\(N\\) startet also mit \\(i=2\\) auf Band \\(1\\), schreibt das initiale Programm \\(omega\\) auf Band \\(2\\) und das Teilprogramm \\(\\gamma_2\\) (gr\u00fcn) auf Band \\(3\\). Die B\u00e4nder von \\(N\\) sehen nun so aus (ich habe der \u00dcbersichtlichkeit halber (okay, ich gebe es zu, ich war wieder zu faul) nicht die ganzen Programme \\(\\omega\\) und \\(\\gamma\\) auf die B\u00e4nder gepackt):<\/span><\/span><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/baender_N.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2266\" style=\"margin-left: 10px; margin-right: 100px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/baender_N.png\" alt=\"baender_N\" width=\"489\" height=\"102\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/baender_N.png 815w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/baender_N-300x62.png 300w\" sizes=\"auto, (max-width: 489px) 100vw, 489px\" \/><\/a><\/li>\n<li><span style=\"line-height: 13px;\"><span style=\"line-height: 13px;\"><span style=\"line-height: 13px;\">Jetzt geht \\(N\\) hin und kopiert das initiale Programm \\(\\omega\\) von Band \\(2\\) links neben \\(\\omega\\) auf Band \\(2\\) und benennt die Marken um (in unserem Beispiel sind die schon umbenannt &#8211; statt in Zahlen in Buchstaben, aber dennoch umbenannt -; normal w\u00fcrde das Teilprogramm auch mit \\(0\\) statt \\(A\\) starten usw.). Band \\(3\\) sieht dann so aus:<\/span><\/span><\/span><\/li>\n<\/ul>\n<p><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/band_3_N-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone wp-image-2933\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/band_3_N-1-300x10.png\" alt=\"\" width=\"479\" height=\"17\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/band_3_N-1-300x10.png 300w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/band_3_N-1-768x27.png 768w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/band_3_N-1-1024x36.png 1024w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/band_3_N-1.png 1293w\" sizes=\"auto, (max-width: 479px) 100vw, 479px\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Leider ist die Grafik etwas klein geraten, Sorry. Am Ende steht also unser komplettes Programm \\(\\omega_2=\\gamma_2\\cdot\\omega\\) auf Band \\(3\\) mit umbenannten Marken, bereit zur Ausf\u00fchrung. Naja, fast bereit. Denn das Programm \\(\\omega_2\\) selbst ist ja nicht ausf\u00fchrbar, sondern nur seine G\u00f6delnummer.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><span style=\"line-height: 13px;\">Und die bekommen wir, indem wir zum Programm \\(\\omega_2\\) nun seine G\u00f6delnummer \\({\\nu_{\\Omega}}^{-1}(\\omega_2)=1^44\\)\u00a0(nicht vergessen, \\(1^44\\) ist die willk\u00fcrliche G\u00f6delnummer f\u00fcr \\(\\omega_2\\), die wir uns ausgedacht haben) berechnen. Wir wissen ja, dass wir durch die Ordnungsfunktion auf dem Alphabet unserer Bandprogramme auch eine Standardnummerierung haben.\n<p>Die Funktion\u00a0\\({\\nu_{\\Omega}}^{-1}\\) ist, wie wir im Beitrag zur Standardnummerierung gezeigt haben, berechenbar. Ich gebe hier also nicht extra ein Flussdiagramm einer Maschine an, dass uns zu den Zeichen des Programms \\(\\omega_2\\) auf Band \\(3\\) anhand der Ordnungsfunktion die G\u00f6delnummer berechnet. Wir k\u00f6nnten es aber problemlos.<\/span><\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Damit gilt letztendlich:\u00a0\\(f_N(11)=1^44\\). Nur noch die \\(1^44\\) mit unseren Iotas (\\(\\iota\\)) in Dezimaldarstellung umwandeln und wir sind fertig:<\/p>\n<p style=\"padding-left: 60px;\">\\(\\begin{array}{ll}r(2)&amp;=\\iota^{-1}(f_N(\\iota(2)))\\\\&amp;=\\iota^{-1}(f_N(1^2))\\\\&amp;=\\iota^{-1}(1^44))\\\\&amp;=44\\end{array}\\)<\/p>\n<p style=\"padding-left: 30px;\">F\u00fcttern wir die Maschine mit der G\u00f6delnummer \\(44\\) \\(M_2=\\nu_M(\\omega_2)\\) nun mit unserem \\(x=5\\), so bekommen wir \u00a0\\(f_{M_2}(2)=5\\), was genau das gleiche ist wie \\(f_M(2,3)=5\\), das Ergebnis unserer Ursprungsmaschine \\(M\\) mit zwei Parametern.<\/p>\n<p style=\"padding-left: 30px;\">Fertig.<\/p>\n<p style=\"padding-left: 30px;\">M\u00fcnzen wir das beispiel konkret auf das smn-Theorem, so bedeutet es:<\/p>\n<p style=\"padding-left: 60px;\">\\(f(2,3) = \\varphi_{r(2)}(3)=\\varphi_{144}(3)=5\\) f\u00fcr \\(i=2\\) und \\(x=3\\) bzw.<\/p>\n<p style=\"padding-left: 60px;\">\\(f_M(2,3)=r(f_M,2,3)=f_{M_2}(3)=5\\)<\/p>\n<p style=\"padding-left: 60px;\">PS: nicht vergessen: \\(f_M\\) ist dabei unser Ursprungsprogramm \\(\\omega\\), dass f\u00fcr \\(N\\) nat\u00fcrlich fest vorgegeben ist. Es \u00e4ndert sich nicht, egal welches \\(i\\) oder \\(x\\) wir haben, daher k\u00f6nnen wir es f\u00fcr alle Eingaben fest vorgeben.<\/p>\n<p style=\"padding-left: 30px;\">Und wenn Ihr nach oben, in die Definition vom smn-Theorem schaut, ist es genau die Definition, nur mit unseren Werten f\u00fcr \\(i\\) und \\(x\\) gef\u00fcllt.<\/p>\n<p>Rekapitulieren wir: alles, was unser Programm \\(r\\) bzw. die Maschine \\(N\\) macht, ist uns ein festes Argument zusammen mit dem Quellcode des Urspungsprogramms in eine neue Maschine zu codieren und uns dazu die zugeh\u00f6rige G\u00f6delnummer anzugeben. Mit unserer universellen Turingmaschine \\(u_\\varphi\\) (utm-Theorem) k\u00f6nnen wir diese neue Maschine mit den verbliebenen, nicht fixierten Argumenten interpretieren. Nur der Zusammenhang zu \\((S)\\) ist euch wahrscheinlich noch nicht klar. Aber darum k\u00fcmmern wir uns jetzt.<\/p>\n<p>Die Eigenschaft \\((S)\\) (d.h. die effektive Komposition) gefordert wird. Wenn man also zwei Programme einer Sprache komponieren kann, ist das smn-Theorem erf\u00fcllt und umgekehrt. Das liegt an einer Kleinigkeit, unserer Funktion \\(r\\) aus dem smn-Theorem.<\/p>\n<p><strong>Zusammenhang zwischen effektiver Komposition und dem smn-Theorem<\/strong><\/p>\n<p>Wir schauen uns nochmal die Forderung <strong>(S)<\/strong> an, welche an Programmiersprachen gestellt wird:<\/p>\n<ul>\n<li><strong>(S)<\/strong>\u00a0Zu je zwei Programmen \\(P\\) und \\(Q\\) m\u00f6chte man ein Programm f\u00fcr die Komposition konstruieren k\u00f6nnen, d.h. es soll eine berechenbare Funktion \\(h\\) geben, so dass \\(\\sigma(h(P,Q)=\\sigma(Q) \\circ\\sigma(P)\\).<\/li>\n<\/ul>\n<p>W\u00e4hrend die Funktion \\(r\\) in ihrer urspr\u00fcnglichen Form, \\(r: \\mathbb{N} \\rightarrow\\mathbb{N}\\) mit \\(r(i) = k\\) einen Index\/G\u00f6delnummer f\u00fcr eine neue Maschine ausgibt, damit \\(f(i,x) = \\varphi_k(x)\\) gilt, gibt uns die gleiche Funktion, jedoch mit dem Definitionsbereich \\(\\mathbb{N}^2\\), d.h. \u00a0\\(r: \\mathbb{N^2} \\rightarrow\\mathbb{N}\\)\u00a0(die Funktion \\(r\\) bekommt also zwei Parameter aus \\(\\mathbb{N}\\) \u00fcbergeben) auch <strong>nur einen<\/strong> Index einer Maschine. Dieses Mal jedoch den Index\/G\u00f6delnummer einer Maschine, die zwei Ursprungsmaschinen mit den Indizes \\(i\\) und \\(j\\) <strong>zusammenschaltet<\/strong>, so dass gilt: \u00a0\\(f(&lt;i,j&gt;,x) = \\varphi_i(\\varphi_j(x))\\). That&#8217;s it.<\/p>\n<p>Funktionieren tut das genauso wie beim Beispiel zum smn-Theorem:<\/p>\n<p>(Danke an Herbert f\u00fcr seinen Beitrag zum Thema in der NG)<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Dazu werden die Marken aus dem Flussdiagramm der Maschine \\(i\\) erh\u00f6ht\/umbenannt. Und zwar um den Wert der gr\u00f6\u00dften Marke aus dem Flussdiagramm der Maschine \\(j\\) damit es in der neuen Maschine keine gleichen Marken gibt, denn es k\u00f6nnte aus beiden Maschinen Marken mit der gleichen Nummer geben.<\/li>\n<li>Dann wird aus der \\(HALT\\)-Marke von Maschine \\(i\\) in die Startmarke der Maschine \\(j\\) und wir haben eine Zusammenschaltung und nur eine einzige Maschine aus zwei gebaut.<\/li>\n<li>Das k\u00f6nnen wir nat\u00fcrlich beliebig kombinieren, so dass unser \\(r\\) wie folgt definiert wird:\u00a0\\(r: \\mathbb{N}^m \\rightarrow\\mathbb{N}\\). Die &#8222;\u00dcbersetzungsleistung&#8220; besteht hier nicht von einer Sprache in die andere, sondern in einer Zusammenschaltung von zwei Maschinen in eine durch Umbenennung der Marken und Verkn\u00fcpfen der Flussdiagramme, so dass wir am Ende aus zwei Flussdiagrammen nur noch eines haben.<\/li>\n<\/ul>\n<p>Wir k\u00f6nnen im Endeffekt also eine beliebige Anzahl (\\(m\\))\u00a0von Maschinen zusammenschalten, so dass wir am Ende nur eine Maschine haben. Jetzt k\u00f6nnen wir uns auch die \u00fcbliche Definition der Funktion \\(r\\) herleiten, die normal \\(s\\) hei\u00dft:<\/p>\n<p>\\(s_n^{m}:\\mathbb{N}^{m+1} \\rightarrow \\mathbb{N}\\) mit \\(\\varphi_{s_n^{m}(i,y_1,&#8230;,y_m)}(z_1,&#8230;,z_n) = \\varphi_i(y_1,&#8230;,y_m,z_1,&#8230;,z_n)\\)<\/p>\n<p>Und hier verstehen wir auch warum sich das Theorem eben <strong>smn-Theorem<\/strong> nennt. Die Funktion besagt nichts anderes, als dass wir \\(m\\) Maschinen zusammenschalten und somit in eine \u00fcberf\u00fchren\/transformieren k\u00f6nnen, die mit \\(n\\) Argumenten gef\u00fcttert werden kann und das selbe Ergebnis hat wie die urspr\u00fcngliche Maschine. Und das ist ja genau unser Wunsch nach einer Komposition aus Forderung \\((S)\\).<\/p>\n<p>Klar geworden? Damit haben wir nun auch unser \\((S)\\) abgehakt.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: mit dem smn-Theorem ist es uns nicht nur m\u00f6glich Eingabeparameter einer Maschine fest zu codieren und zur neu erzeugten Maschine eine G\u00f6delnummer anzugeben, die um einen Eingabeparameter (den fest codierten) weniger ben\u00f6tigt und dennoch das gleiche Ergebnis berechnet (um <a href=\"http:\/\/de.wikipedia.org\/wiki\/Currying\">Currying<\/a> zu unterst\u00fctzen), sondern wir k\u00f6nnen mit dem smn-Theorem auch Funktionen, d.h. Maschinen zusammenschalten um eine Forderung an gute Programmiersprachen zu erf\u00fcllen: <strong>(S)<\/strong> die Forderung nach einer effektiven Komposition.<\/p>\n<p>Das funktioniert durch ein Zusammenf\u00fcgen der Flussdiagramme, bzw. Befehle der Maschinen bei gleichzeitiger Umbenennung der Marken, so dass z.B. die \\(HALT\\)-Marke einer Maschine statt zu halten nun auf die Anfangsmarke der anderen Maschine verweist.<\/p>\n<p>Zusammen mit dem utm-Theorem bilden sie das Grundger\u00fcst f\u00fcr gute Programmiersprachen: <strong>(S)<\/strong> und <strong>(U)<\/strong>.<\/p>\n<h2>Lernziel 6<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung des \u00c4quivalenzsatzes f\u00fcr Nummerierungen (Rogers)<\/em><\/p>\n<p>Wir machen uns zun\u00e4chst klar, dass wir mit \\(\\varphi\\) eine eigene Programmiersprache entwickelt haben. Wir konnten mit dieser alle Funktionen aus \\(P^{(1)}\\) nummerieren und diese auf unseren universellen Turingmaschinen ausf\u00fchren.<\/p>\n<p>Zwar haben wir die Syntax und die Notation dieser Bandbefehle willk\u00fcrlich gew\u00e4hlt. Das ist aber gar nicht tragisch, denn die Nummerierung im Skript ist genauso gut wie jede andere. Vorausgesetzt sie erf\u00fcllt das utm- (universelle Turingmaschine) und das smn- (\u00dcbersetzungslemma) Theorem. Dann sind die Nummerierungen n\u00e4mlich \u00e4quivalent zueinander, da sie ineinander \u00fcberf\u00fchrbar sind.<\/p>\n<p>Der <strong>\u00c4quivalenzsatz von Rogers<\/strong> besagt formal:<\/p>\n<blockquote><p>Sei \\(\\psi\\) eine Nummerierung von \\(P^{(1)}\\), dann sind folgende Eigenschaften \u00e4quivalent:<\/p>\n<p>1. \\(\\psi \\equiv \\varphi\\)<\/p>\n<p>2. \\(\\psi\\) erf\u00fcllt das utm- (universelle Funktion von \\(\\psi\\) ist berechenbar) und das smn- (Berechnung der Nummer eines Programms und damit z.B. die \u00dcbersetzung in eine andere Programmiersprache) Theorem.<\/p><\/blockquote>\n<p>Damit lassen sich alle Programme, die beide Theoreme erf\u00fcllen durch &#8222;\u00dcbersetzer&#8220; \\(g,h\\in R^{(1)}\\) ineinander \u00fcbersetzen. D.h. soviel wie:<\/p>\n<p style=\"padding-left: 30px;\">\\(\\varphi=g(\\psi)\\) und<\/p>\n<p style=\"padding-left: 30px;\">\\(\\psi=h(\\varphi)\\).<\/p>\n<p>Wir k\u00f6nnen uns daher auf eine Nummerierung beschr\u00e4nken wenn sie die beiden Theoreme erf\u00fcllt. Unser \\(\\varphi\\) ist somit genauso gut wie jede andere Nummerierung (die nat\u00fcrlich auch das utm- und das smn-Theorem erf\u00fcllen muss).<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: nach dem \u00c4quivalenzsatz von Rogers sind alle Programmiersprachen\/Nummerierungen \u00e4quivalent wenn sie das utm- und das smn-Theorem erf\u00fcllen.<\/p>\n<p>Hat man also eine andere Programmiersprache\/Nummerierung \\(\\psi:\\mathbb{N}\\rightarrow P^{(1)}\\), die beide Theoreme erf\u00fcllt, so sind diese \u00e4quivalent, d.h. \\(\\varphi\\equiv\\psi\\) und k\u00f6nnen mit &#8222;\u00dcbersetzern&#8220; ineinander \u00fcberf\u00fchrt werden.<\/p>\n<h2>Lernziel 7<\/h2>\n<p style=\"padding-left: 30px;\"><em>Formulieren des Rekursionssatzes<\/em><\/p>\n<p>Dieser Satz wird auch <em>Fixpunktsatz von Kleene<\/em> genannt. Ich fand es pers\u00f6nlich einfacher von der anderen Seite an diesen Satz heranzugehen, die Skripte der HU Berlin gehen einen \u00e4hnlichen weg. Aber fangen wir mal an: ein sch\u00f6nes Beispiel f\u00fcr den Rekursionssatz ist die Selbstreproduktion. Wir wollen also ein Programm, dass bei einer beliebigen Eingabe sich selbst ausgibt. Dazu ist der <strong>Rekursionssatz<\/strong> hilfreich.<\/p>\n<p>Formal ausgedr\u00fcckt:<\/p>\n<blockquote><p>Zu jeder Funktion \\(f \\in R^{(1)}\\) gibt es eine Zahl \\(n\\) mit \\(\\varphi_n = \\varphi_{f(n)}\\).<\/p><\/blockquote>\n<p>Was bedeutet das nun genau und was ist \\(n\\)? \\(n\\) ist die G\u00f6delnummer einer Maschine, also quasi unser in nat\u00fcrliche Zahlen codierter Programmcode (kennt Ihr schon, Thema Standardnummerierung). Unsere Programmtransformationsfunktion \\(f\\) bekommt als Eingabe diese G\u00f6delnummer \\(n\\), rechnet darauf rum und gibt uns als Ausgabe eine G\u00f6delnummer \\(f(n)=k\\) aus.<\/p>\n<p>Wenn wir nun die Maschine mit der G\u00f6delnummer \\(k\\) und dem Parameter \\(x\\) starten (\\(\\varphi_k(x)\\)), so bekommen wie die gleiche Ausgabe, die unser Programm mit der G\u00f6delnummer \\(n\\) und dem Parameter \\(x\\) gehabt h\u00e4tte (\\(\\varphi_n(x)\\)), d.h.<\/p>\n<p style=\"padding-left: 30px;\">\\(\\varphi_n(x) = \\varphi_{f(n)}(x)\\)<\/p>\n<p>Umgangssprachlich gesprochen: Wir k\u00f6nnen \\(f\\) als eine &#8222;Programmumschreibefunktion&#8220; betrachten. Nach diesem Satz gibt es Programme, die in ihrer Funktion von unserer Programmtransformationsfunktion \\(f\\) nicht ver\u00e4ndert werden. Aber Achtung: nur in der <span style=\"text-decoration: underline;\">Funktion<\/span>, d.h. es k\u00f6nnten Programmteile abge\u00e4ndert oder hinzugef\u00fcgt werden, die nicht zur Ausf\u00fchrung kommen. Die korrekte und gleiche Funktion\/Ausgabe des Programms ist damit dennoch gegeben.<\/p>\n<p style=\"padding-left: 30px;\">\\(n\\) wird deswegen auch der semantische <strong>Fixpunkt<\/strong> der Modifikationsfunktion \\(f\\) genannt.<\/p>\n<p>Damit ist es uns z.B. erlaubt Maschinen zu erstellen, welche eine Beschreibung von sich selbst berechnen und benutzen k\u00f6nnen. Das ist keineswegs selbstverst\u00e4ndlich! Denn lange Zeit galt diese sog. Selbstreproduktion, d.h. Maschinen, die sich selbst nachbauen ohne sich selbst zu enthalten als unm\u00f6glich.<\/p>\n<p>Alle Erfindungen, die andere Dinge herstellten wie z.B. eine Autofabrik oder Werkzeughersteller sind komplexer als das erzeugte Produkt und brauchen eine Beschreibung des herzustellenden Produktes. Damit w\u00e4re die Selbstreproduktion aber unm\u00f6glich, denn um einfache Produkte zu bauen, braucht man komplexe.<\/p>\n<p>Und genau das ist der Trugschluss, den <a href=\"http:\/\/de.wikipedia.org\/wiki\/John_von_Neumann\">von Neumann<\/a>\u00a01966 aufgezeigt hat, indem er theoretisch eine einfache Maschine konstruierte, die sich selbst reproduzieren kann:<\/p>\n<p>Diese Maschine besteht aus drei Teilen:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><span style=\"line-height: 13px;\"><span style=\"line-height: 13px;\"><span style=\"line-height: 13px;\">dem <strong>Konstrukteur<\/strong> \\(K\\)\n<p>Der\u00a0Konstrukteur\u00a0bekommt die Beschreibung einer Maschine (mathematisch gesehen also z.B. unsere G\u00f6delnummer \\(i\\)) und setzt diese dann mit den Bauteilen zusammen, so dass wir eine Maschine mit \\(\\varphi_i\\) bekommen.<\/span><\/span><\/span><\/li>\n<li>dem <strong>Kopierer<\/strong> \\(C\\)\n<p>Der\u00a0Kopierer\u00a0kann den Bandinhalt von einem Band auf ein anderes kopieren, so dass am Ende zwei B\u00e4nder mit dem selben Inhalt als Ausgabe ausgegeben werden.<\/li>\n<li>der <strong>Steuerung<\/strong> \\(S\\)\n<p>Die\u00a0Steuerung\u00a0k\u00fcmmert such um Konstrukteur und Kopierer und versorgt beide mit Eingaben.<\/li>\n<\/ul>\n<p>Was wir also brauchen ist, eine Maschine \\(M\\), die bei der Eingabe von sich selbst, sich selbst reproduziert. Und so sieht dann die Maschine aus:<\/p>\n<p style=\"text-align: center;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/reproduct.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-2289\" style=\"margin-left: 0px; margin-right: 50px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/reproduct.png\" alt=\"reproduct\" width=\"496\" height=\"120\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/reproduct.png 919w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/reproduct-300x72.png 300w\" sizes=\"auto, (max-width: 496px) 100vw, 496px\" \/><\/a><\/p>\n<p style=\"text-align: left;\">Wir geben den Bauplan \\(i\\) in die Steuerung, diese gibt sie an den Kopierer, welcher den Bauplan verdoppelt. Eine Kopie wird an den Konstrukteur \u00fcbergeben, der daraus eine neue Maschine \\(M_i\\) baut. Und eben diese neue Maschine (der &#8222;Sohn&#8220;) bekommt dann von seinem &#8222;Vater&#8220; den Bauplan ausgeh\u00e4ndigt und baut dann den &#8222;Enkel&#8220;, eine exakte Kopie von sich selbst usw.<\/p>\n<p>Und nun wieder zur\u00fcck zur theoretischen Informatik:<\/p>\n<p>Wir haben damit eine M\u00f6glichkeit zur Selbstreproduktion und k\u00f6nnen Maschinen angeben, die sich selbst ausgeben k\u00f6nnen.\u00a0Mit dem Rekursionssatz ist es also sichergestellt, dass es ein Programm gibt, welches bei allen m\u00f6glichen Eingaben sich selbst ausgibt. Eine Anwendung sind z.B. die <a href=\"http:\/\/de.wikipedia.org\/wiki\/Quine_(Computerprogramm)\">Quines<\/a>, denn sie geben bei jeder Ausgabe sich selbst aus, damit gilt der Satz \u00fcber <strong>Selbstreproduktion<\/strong>:<\/p>\n<blockquote><p>Es gibt eine Zahl \\(n\\), so dass \\(\\varphi_n(x) = n\\) f\u00fcr alle \\(x\\).<\/p><\/blockquote>\n<p>Wer k\u00f6nnte denn an sowas interessiert sein? Au\u00dfer Skynet. Viren zu Beispiel.<\/p>\n<p>Just als ich den Beitrag getippt habe, fliegt mir ein Satz Folien um die Ohren, die ich euch nicht vorenthalten will: Folien zur <a href=\"http:\/\/ddi.cs.uni-potsdam.de\/didaktik\/Forschung\/VortragsfolienRekursionstheorem.pdf\">Selbstreproduktion der Uni Potsdam<\/a>.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Der Rekursionssatz von Kleene besagt, dass man zu einem gegebenen Modifikationsprogramm \\(f\\) immer einen Quelltext finden kann, der trotz Modifikation seine Aufgabe weiterhin erf\u00fcllt. Da sich die Semantik des Programms somit nicht \u00e4ndert wird dieser Quelltext (das \\(n\\)) auch semantischer Fixpunkt von \\(f\\) genannt.<\/p>\n<p>Ein Anwendungsbereich dieses Satzes ist die Selbstreproduktion, so dass die Ausgabe von sich selbst der Fixpunkt ist (das Programm gibt sich selbst aus) und es gelten muss: \\(\\varphi_n(x)=n\\), egal was man als \\(x\\) eingibt.<\/p>\n<p>Puh, das war ein Haufen arbeit. Wie immer gilt: sollten sich Fehler eingeschlichen haben: bitte wieder Bescheid geben. Danke auch an die Kollegen aus der NG, die so manche einleuchtende Erkl\u00e4rung eingeworfen und zu diesem Text beigetragen haben. Schade, dass die NG jedes Semester gel\u00f6scht wird. So verwindet manch eine sch\u00f6ne Erl\u00e4uterung im digitalen Papierkorb. Vielleicht tr\u00e4gt der Blog ja etwas dazu bei, dass einige Erl\u00e4uterungen \u00fcber das Haltbarkeitsdatum der NG bestehen bleiben.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: Formulierungen etwas verst\u00e4ndlicher gemacht. Wenn euch das smn-Theorem noch nicht ganz klar, war bitte den Beitrag nochmal lesen. Update: aus zwei macht drei. Das ist nun hoffentlich der letzte Teil zu KE5 mit einem riesen Beispiel zum smn-Theorem. Noch einmal die Wiederholung der zwei Anforderungen an vern\u00fcnftige Programmiersprachen: (U) Es soll einen Computer geben, &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=1047\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: smn-Theorem, Rekursions- und \u00c4quivalenzsatz (Lernziele KE5, 3\/3)\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-1047","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\/1047","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=1047"}],"version-history":[{"count":97,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1047\/revisions"}],"predecessor-version":[{"id":3513,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1047\/revisions\/3513"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1047"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1047"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1047"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}