Starten wir aber einfach wieder anhand der Lernziele und k\u00e4mpfen uns da durch.<\/p>\n
Lernziel 1<\/h2>\n
Angabe und Erl\u00e4uterung der Definition und der Eigenschaften der Cantorschen Tupelfunktion Zum Gl\u00fcck habe ich bereits hier<\/a> einen langen Beitrag zum Thema erstellt und wiederhole mich deswegen nicht, sondern springe sofort zur Antwort.<\/p>\n Antwort zum Lernziel<\/strong>: mit der Cantorschen Tupelfunktion ist es uns m\u00f6glich einem \\(n\\)-Tupel mit Elementen aus \\(\\mathbb{N}\\) eine einzige, eindeutige Zahl aus \\(\\mathbb{N}\\) zuzuordnen (Reduktion). Durch diese bijektive Abbildung von \\(\\mathbb{N}^n\\rightarrow\\mathbb{N}\\)\u00a0k\u00f6nnen wir uns auf die Berechnung von einstelligen Funktionen beschr\u00e4nken.<\/p>\n Einen weiteren prominenten Platz hat die Cantorsche Tupelfunktion bei dem Vergleich von Mengen: zwei Mengen sind gleichm\u00e4chtig wenn man zwischen ihnen eine Bijektion herstellen kann.<\/p>\n Erl\u00e4uterung der Abschlusseigenschaften berechenbarer Zahlenfunktionen<\/em><\/p>\n Ich bin mir hier gerade etwas unschl\u00fcssig: im Skript ist nicht mehr viel zu dem Thema drin, als der Satz zur Substitution, primitive Rekursion, \\(\\tilde{\\mu}\\) und der Umkehrfunktion. Vielleicht dann am besten an ein paar Beispielen?<\/p>\n Substitution<\/strong><\/p>\n Zun\u00e4chst haben wir zwei ggf. partielle Funktionen \\(g:\\subseteq\\mathbb{N}^m\\rightarrow\\mathbb{N}\\) und ggf. partielle Funktionen \\(h_1\\) bis \\(h_m\\) (d.h. so viele Funktionen wie der Definitionsbereich von \\(g\\) Parameter hat), mit \\(h_1,…,h_m\\subseteq\\mathbb{N}^k\\rightarrow\\mathbb{N}\\). Alle Funktionen sind berechenbar. Dann ist auch die Substitution \\(Sub(g,h_1,…,h_m)\\) berechenbar.<\/p>\n \\(Sub(g,h_1,…,h_m)\\subseteq\\mathbb{N}^k\\rightarrow\\mathbb{N}\\) ist definiert durch\u00a0\\(Sub(g,h_1,…,h_m)(x):=g(h_1(x),…,h_m(x))\\)<\/p>\n Viel Zeug, oder? Keine Sorge, ist ganz easy.<\/p>\n Beispiel<\/strong><\/p>\n \\(g(x,y)=x+y\\)<\/p>\n \\(h_1(x,y,z)=x+y\\)<\/p>\n \\(h_2(x,y,z)=x+z\\)<\/p>\n Die Substitution sieht nun so aus:<\/p>\n \\(Sub(g,h_1,h_2)(x,y,z)=g(h_1(x,y,z),h_2(x,y,z))\\).<\/p>\n Belegen wir unsere Funktion mit Werten: \\(x=2,y=3,z=4\\)<\/p>\n \\(\\begin{array}\u00a0Sub(g,h_1,h_2)(2,3,4)&=g(h_1(2,3,4),h_2(2,3,4))\\\\&=g(5,h_2(2,3,4))\\\\&=g(5,6)\\\\&=11\\end{array}\\)<\/p>\n War doch trivial, oder (das wollte ich immer schon mal sagen!)?<\/p>\n Primitive Rekursion<\/strong><\/p>\n Das ist ein klein wenig ekeliger als die Substitution, aber wir bekommen das gleich noch klein.<\/p>\n Auch hier haben wir zwei Funktionen\u00a0\u00a0\\(g:\\mathbb{N}^k\\rightarrow\\mathbb{N}\\) und\u00a0\u00a0\\(h:\\mathbb{N}^{k+2}\\rightarrow\\mathbb{N}\\), die berechenbar sind (Achtung: sie m\u00fcssen auch total sein, denn sonst k\u00f6nnen wir nicht \u00fcber diese „rekursivieren“). Wenn das der Fall ist, dann ist auch \\(Prk(g,h)\\) berechenbar.<\/p>\n \\(Prk(g,h)\\) ist definiert als:<\/p>\n \\(f(x,0) = g(x)\\)<\/p>\n \\(f(x,y+1)=h(x,y,f(x,y))\\)<\/p>\n F\u00fcr alle \\(x\\in\\mathbb{N}^k\\) und \\(y\\in\\mathbb{N}\\). Man sieht bereits jetzt, dass wir rekursiv arbeiten. Noch deutlicher wird es an einem Beispiel.<\/p>\n Beispiel<\/strong><\/p>\n \\(g(x,z)=x+z\\)<\/p>\n \\(h(a,b,x,z)=a+b+x+z\\)<\/p>\n Nehmen wir einfach mal \\(y=3\\) (\\(3\\)-malige Rekursion) und \\(x=2,z=3,a=4,b=5\\).<\/p>\n \\(\\begin{array}\u00a0Prk(g,h)(2,3)&=f(2,3,3)\\\\&=h(2,3,2,f(2,3,2))\\\\&=h(2,3,2,(h(2,3,1,f(2,3,1))))\\\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,f(2,3,0))))))\\\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,g(2,3))))))\\\\&=h(2,3,2,(h(2,3,1,(h(2,3,0,5)))))\\\\&=h(2,3,2,(h(2,3,1,10)))\\\\&=h(2,3,2,16)\\\\&=23\\end{array}\\)<\/p>\n Versuchen wir das mit \\(y=2\\):<\/p>\n \\(\\begin{array}\u00a0Prk(g,h)(2,2)&=f(2,3,2)\\\\&=h(2,3,1,f(2,3,1))\\\\&=h(2,3,1,(h(2,3,0,f(2,3,0))))\\\\&=h(2,3,1,(h(2,3,0,5)))\\\\&=h(2,3,1,10)\\\\&=16\\end{array}\\)<\/p>\n Viel Text, aber sicherlich gut nachzuvollziehen. Wir loopen und also durch die Funktionen mit einer festen<\/strong> Anzahl an Schleifen! In diesem Beitrag<\/a> habe ich die primitive Rekursion etwas detaillierter betrachtet.<\/p>\n Und was ist wenn wir keine feste Anzahl an Schleifen haben k\u00f6nnen? Dann hilft uns unser \\(\\mu\\)-Operator.<\/p>\n\\(\\tilde{\\mu}\\)\n Ist \\(h\\) mit\u00a0\\(h:\\subseteq\\mathbb{N}^{k+1}\\rightarrow\\mathbb{N}\\) berechenbar, so ist es auch\u00a0\\(\\tilde{\\mu}(h)\\). Wie ihr seht, auch hier ist \\(h\\) total. Was ist\u00a0\\(\\tilde{\\mu}\\)?! \\(\\tilde{\\mu}:\\subseteq\\mathbb{N}^{k}\\rightarrow\\mathbb{N}\\).\u00a0Es ist definiert durch:<\/p>\n \\(\\tilde{\\mu}(h)(x)=\\mu y[h(x,y)=0]\\)<\/p>\n What the… Entspannung, Entspannung! Das ist nichts weiter als unsere \\(\\mu\\)-Rekursion. Ich suche gerade im Skript ob wir das bereits irgendwo auf den vorherigen Seiten hatten… witzig. Hatten wir nicht. Das ist wirklich die erste Erw\u00e4hnung. Und dann gleich ins kalte Wasser. Nicht schlimm, denn unser\u00a0\\(\\tilde{\\mu}\\) ist nichts weiter, als der Operator, der es uns erlaubt auch Dinge zu berechnen, wo wir die genaue Anzahl an Schleifendurchl\u00e4ufen noch nicht wissen.<\/p>\n Und zwar indem wir unserer zu berechnende Funktion so weit umformen, dass wir beim Ende der Berechnung auf eine Nullstelle sto\u00dfen.\u00a0Ich werde das nicht gro\u00df ausf\u00fchren, sondern verweise ganz frech auf meinen alten Beitrag zum Thema<\/a>.<\/p>\n Umkehrfunktion<\/strong> \\(f^{-1}\\)<\/p>\n Das schwerste zum Schluss. Hier gehen wir davon aus, dass \\(f\\) injektiv<\/a> ist (wichtig!). Wir beschr\u00e4nken uns auch auf einstellige Funktionen. Warum? Na? Na? Genau: aufgrund der Cantorschen Tupelfunktion<\/a> k\u00f6nnen wir das. Wenn diese Funktion also berechenbar ist, so ist es auch ihre Umkehrfunktion. Klingt logisch. Ist es auch.<\/p>\n W\u00e4hrend f\u00fcr \\(f\\) Totalit\u00e4t und Injektivit\u00e4t gefordert ist, k\u00f6nnen wir bei \\(f^{-1}\\) bei einer ggf. partiellen Funktion rauskommen. Das liegt daran, dass wir in der Bildmenge von \\(f\\) evtl. Elemente haben, die wir mit unserer Funktion nicht „treffen“. Diese landen aber f\u00fcr \\(f^{-1}\\) dennoch in der Definitionmenge, sind aber nicht definiert. Damit ist \\(f^{-1}\\) eben partiell.<\/p>\n Beispiel<\/strong><\/p>\n \\(f(x) = x+5\\) mit der Umkehrfunktion \\(f^{-1}(\\tilde{x})=\\tilde{x}-5\\). Setzen wir \\(x=10\\) und \\(\\tilde{x}=f(x)\\), so\u00a0haben wir:<\/p>\n \\(f(10)=15\\)<\/p>\n \\(f^{-1}(15)=10\\)<\/p>\n Passt.<\/p>\n Damit haben wir die Abschlusseigenschaften f\u00fcr berechenbare Zahlenfunktionen durch.<\/p>\n Antwort zum Lernziel<\/strong>: Funktionen, die sich aus den Funktionen Substitution, primitive Rekursion, \\(\\mu\\)-Rekursion und der inversen Funktion zusammensetzen sind ebenfalls berechenbar.<\/p>\n F\u00fcr die Substitution k\u00f6nnen die Funktionen auch partiell sein, f\u00fcr de primitive und \\(\\mu\\)-Rekursion sind wir jedoch auf totale Funktionen angewiesen, da wir sonst nicht durch die Schleifendurchl\u00e4ufe kommen. W\u00e4hrend wir bei der primitiven Rekursion zwingend die Anzahl der Schleifendurchl\u00e4ufe kennen m\u00fcssen, ist es uns bei der \\(\\mu\\)-Rekursion durch das „Nullsetzen“ der Funktion nicht wichtig. Es bricht eben ab wenn die Nullstelle gefunden ist. Wie lange es dauert wissen wir nicht.<\/p>\n Ersteres ist das \u00c4quivalent zur \\(LOOP\\)-Schleife („tue etwas genau \\(x\\) Mal“), w\u00e4hrend die \\(\\mu\\)-rekursion einer \\(WHILE\\)-Schleife („tue etwas bis…“) entspricht.<\/p>\n F\u00fcr die inverse Funktion ben\u00f6tigen wir neben einer totalen Funktion \\(f\\) jedoch auch die Eigenschaft der Injektivit\u00e4t f\u00fcr \\(f\\), da wir nur auf maximal ein Element aus der Bildmenge abbilden d\u00fcrfen, da sonst die Umkehrabbildung auf zwei unterschiedliche Elemente abbilden w\u00fcrde.<\/p>\n Definition der WHILE-Programme, Erl\u00e4uterung ihrer Semantik und Angabe des Zusammenhangs zu berechenbaren Funktionen Letztes Lernziel in dieser Kurseinheit. In diesem Beitrag<\/a> sind die Details bereits herausgearbeitet, ich k\u00fcmmere mich daher nur um die Definition und Semantik aus dem Skript. Das Fazit kann man wortw\u00f6rtlich eig. auch f\u00fcr die Antwort zum Lernziel \u00fcbernehmen. Also k\u00fcmmern wir uns um die Syntax und die Semantik.<\/p>\n \\(R_i+\\) und\u00a0\\(R_i-\\) sind \\(WHILE\\)-Programme<\/p>\n Dabei addiert\u00a0\\(R_i+\\) im \\(i\\)-ten Registereine \\(1\\),\u00a0\\(R_i-\\) subtrahiert eine \\(1\\) im\u00a0\\(i\\)-ten Register.<\/p>\n IF \\(R_i=0\\) THEN \\(P\\) ELSE \\(Q\\)<\/p>\n Wir gehen davon aus, dass \\(P\\) und \\(Q\\) selbst \\(WHILE\\)-Programme sind.<\/p>\n WHILE \\(R_i\\neq 0\\) DO \\(P\\)<\/p>\n Kennen wir auch schon. Solange das Register \\(R_i\\) nicht \\(0\\) ist, wird \\(P\\) ausgef\u00fchrt.<\/p><\/blockquote>\n Zus\u00e4tzlich dazu haben wir noch unser kleines Tau \\(\\tau\\). Dadurch weisen wir unseren oben beschriebenen Kommandos tats\u00e4chliche Funktionen auf der Datenmenge \\(D=\\mathbb{N}^{\\mathbb{N}}\\) zu, die wir bereits verbal beschrieben haben (sie ist die uns bekannte Datenmenge der Registermaschinen). Als Beispiel nehmen wir \\(R_i+\\) und \\(R_i-\\):<\/p>\n \\(\\tau(R_i+)(a_0,a_1,…):=(a_0,a_1,…,a_i+1,…,)\\)<\/p>\n \\(\\tau(R_i-)(a_0,a_1,…):=(a_0,a_1,…,a_i-1,…,)\\)<\/p>\n Wir k\u00f6nnen einem kompletten \\(WHILE\\)-Programm mittels \\(\\tau\\) ebenfalls eine Ausgabe auf der Datenmenge \\(D\\) beschaffen: \\(\\tau(P)\\). Und damit haben wir dann die komplette Registerausgabe unserer Maschine, die das Programm \\(P\\) berechnet. Damit schaffen wir es, dass unser Programm auf der Eingabecodierung einer Registermaschine operieren kann und uns auch eine Ausgabecodierung der Registermaschine liefert (siehe vorheriger Beitrag<\/a>).<\/p>\n Noch eine kleine Definition f\u00fcr die \\(WHILE\\)-Berechenbarkeit<\/p>\n Wir nennen eine Funktion \\(f:\\mathbb{N}^k\\rightarrow\\mathbb{N}\\) \\(WHILE\\)-berechenbar genau dann wenn gilt: \\(f=AC(\\tau(P)(EC))\\)<\/p><\/blockquote>\n \u00c4hnliches Spiel wie im Beitrag zu KE1. Wir haben unterschiedliche Datenmengen f\u00fcr \\(\\tau\\) und f\u00fcr die Flussdiagramme der Registermaschinen. Mit \\(EC\\) und \\(AC\\) wandelt wir diese nur ineinander um.<\/p>\n Das f\u00fchrt uns direkt zum\u00a0Zusammenhang zu den berechenbaren Funktionen.<\/p>\n Beispiel<\/strong><\/p>\n <\/strong>Funktion\u00a0\\(f(x,y)=x+y\\) (operiert auf \\(\\mathbb{N}^2\\rightarrow\\mathbb{N}\\))<\/p>\n Dazu haben wir ein \\(WHILE\\)-Programm \\(P\\), welches uns die Funktion \\(f\\) berechnet.\u00a0Es operiert auf\u00a0\\(\\mathbb{N}^3\\rightarrow\\mathbb{N}^3\\)<\/p>\n Wir k\u00f6nnen auch ein Flussdiagramm \\(F\\) einer Registermaschine \\(M\\) angeben, dass uns die gleiche Funktion raushaut.<\/p>\n W\u00e4hrend das Flussdiagramm ebenfalls auf\u00a0\\(\\mathbb{N}^3\\rightarrow\\mathbb{N}^3\\) operiert, haben wir bei der Registermaschine jedoch\u00a0\\(\\mathbb{N}^3\\rightarrow\\mathbb{N}\\).<\/p>\n Damit gilt \\(f=\\tau(P)=f_M=f_F\\). Oder doch nicht? Spielen wir das doch einfach mal mit \\(x=2,y=3\\) durch:<\/p>\n \\(f(2,3)=5\\)<\/p>\n \\(\\tau(P)(0,2,3)=(5,2,0)\\)<\/p>\n \\(f_M(0,2,3)=5\\)<\/p>\n \\(f_F(0,2,3)=(5,2,0)\\)<\/p>\n
\n<\/em><\/p>\nLernziel 2<\/h2>\n
Lernziel 3<\/h2>\n
\n<\/em><\/p>\nR0=R1;<\/pre>\n
WHILE R2 NOT 0 DO<\/pre>\n
\u00a0 R0+;<\/pre>\n
\u00a0 R2-;<\/pre>\n
END;<\/pre>\n
![\"while-machine\"](\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/while-machine.png\")
<\/a><\/p>\n