{"id":991,"date":"2012-11-29T11:00:14","date_gmt":"2012-11-29T09:00:14","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=991"},"modified":"2025-11-25T22:41:53","modified_gmt":"2025-11-25T21:41:53","slug":"ti-lernziele-aus-ke5","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=991","title":{"rendered":"TIA: Standardnummerierung und -Komplexit\u00e4t Phi und das Phi-Theorem (Lernziele KE5, 1\/3, Update 7)"},"content":{"rendered":"<p><strong>Update<\/strong>: Tippfehler, Danke Marcel.<\/p>\n<p><strong>Update<\/strong>: Ungenauigkeit beseitigt. Danke Steve.<\/p>\n<p><strong>Update<\/strong>: Fehler beseitigt. Danke Max.<\/p>\n<p><strong>Update<\/strong>: Pfui, da sind mir doch tats\u00e4chlich ein paar Funktionen abhanden gekommen. Sind alle wieder im Text. Auch habe ich einen <a href=\"https:\/\/fernuni.digreb.net\/?p=2572\">weiteren Betrag<\/a> verfasst um den Zusammenhang zwischen einer Programmiersprache und \\(\\varphi\\) sowie dem utm- und smn-Theorem noch etwas zu verdeutlichen.<\/p>\n<p><strong>Update<\/strong>: Fehler beseitigt.<\/p>\n<p><strong>Update<\/strong>: ein paar Details zur Standardnummerierung \\(P^{(1)}\\)\u00a0habe ich noch hinzugef\u00fcgt. Denn die ist nicht bijektiv, sondern nur surjektiv. Das wollte ich unbedingt noch einmal hervorheben, da es im letzten Beitrag so ausgesehen hat, als w\u00e4ren alle Standardnummerierungen bijektiv, was f\u00fcr \\(P^{(1)}\\) nicht stimmt.<\/p>\n<p><strong>Update<\/strong>: beim erneuten Lesen sind mir einige Fehler aufgefallen, die ich nun (hoffentlich) ausgemerzt habe. Auch habe ich die Lernziele etwas umgestellt, so dass sie zwischen den zwei Beitr\u00e4gen besser passen. Wenn also noch irgendwo Verweise sein sollten, wo sie nicht hingeh\u00f6ren: bitte Bescheid geben.<\/p>\n<p>Die Antworten zu den Lernzielen habe ich noch nicht ausformuliert, kommt aber gleich noch.<\/p>\n<p>Weil&#8217;s so sch\u00f6n war: nochmal entlang der Lernziele, diesmal aus KE5. Die Lernziele zu KE5 bestehen aus <del>zwei<\/del> drei Beitr\u00e4gen: diesem hier, dem zweiten und dritten Teil mit:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><a title=\"TIA: utm-Theorem (Lernziele KE5 2\/3)\" href=\"https:\/\/fernuni.digreb.net\/?p=2280\">TIA: utm-Theorem (Lernziele KE5, 2\/3)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=1047\">TIA: smn-Theorem (Lernziele KE5, 3\/3)<\/a><\/li>\n<\/ul>\n<p>Wir starten im ersten Teil direkt mit dem ersten Lernziel: der Standardnummerierung f\u00fcr \\(P^{(1)}\\)<\/p>\n<h2>Lernziel 1<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung der Definition der\u00a0Standardnummerierung \\(\\varphi\\) von \\(P^{(1)}\\)<\/em><\/p>\n<p>Was eine Standardnummerierung ist, wissen wir bereits aus dem <a title=\"TIA: Berechenbarkeit (Lernziele aus KE4, Update 4)\" href=\"https:\/\/fernuni.digreb.net\/?p=837\">Beitrag zu KE4<\/a>. Sie ist (im Kontext von KE4) eine bijektive Abbildung zwischen den nat\u00fcrlichen Zahlen \\(\\mathbb{N}\\) und einer anderen Menge. Im letzten Beitrag haben wir alle Worte \u00fcber dem Alphabet \\(\\Sigma\\), n\u00e4mlich \\(\\Sigma^{*}\\) standard-nummeriert. In diesem Beitrag k\u00fcmmern wir uns um die einstelligen, berechenbaren Zahlenfunktionen \\(P^{(1)}\\).<\/p>\n<p>Nur hier gibt es ein kleines Problemchen:<\/p>\n<p>Ihr wisst doch noch, was dort der Unterschied zwischen einer Nummerierung und einer Standardnummerierung ist? Nein? Sch\u00e4mt euch! Wurde alles im letzten Beitrag durchgekauft. Aber trotzdem:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Eine Nummerierung muss nicht bijektiv sein, <a href=\"http:\/\/de.wikipedia.org\/wiki\/Surjektiv\">Surjektivit\u00e4t<\/a> reicht.<\/li>\n<li>Eine Standardnummerierung jedoch ist eine <a href=\"http:\/\/de.wikipedia.org\/wiki\/Bijektivit%C3%A4t\">bijektive<\/a> Abbildung zwischen zwei Mengen.<\/li>\n<\/ul>\n<p>Durch eine bijektive Abbildung zwischen zwei Mengen zeigen wir unter anderem, dass diese gleichm\u00e4chtig sind. Wo liegt nun das Problem? Kommt gleich, versprochen! Behaltet einfach erst einmal im Hinterkopf, dass die Bijektion f\u00fcr eine Standardnummerierung unserer \\(P^{(1)}\\) keinen Bestand hat.<\/p>\n<p>Im Skript ist \\(BM\\) die Menge der normierten Bandmaschinen mit dem Alphabet \\(\\{1,B\\}\\). Im Gegensatz zu den Bandmaschinen mit beliebigen Hilfsalphabeten sind diese jedoch nummerierbar.<\/p>\n<p>Zun\u00e4chst sollte man sich nochmal ins Ged\u00e4chtnis rufen, dass wir jede (Register-berechenbaren) Zahlenfunktion mittels <a title=\"TI: Berechenbarkeit (Lernziele aus KE4, Update II)\" href=\"https:\/\/fernuni.digreb.net\/?p=837\">Standardnummerierung<\/a> in (Turing-berechenbare) Wortfunktionen und umgekehrt \u00fcberf\u00fchren k\u00f6nnen. Was hier am Ende passieren soll ist, dass wir von einer nat\u00fcrlichen Zahl \u00fcber die Funktion \\(\\nu_P\\) zu einem Bandprogramm kommen. Von diesem ausgehend kommen wir mit \\(\\nu_M\\) auf eine normierte Bandmaschine (bzw. das Flussdiagramm aus diesem). Anschlie\u00dfend k\u00f6nnen wir diese mit\u00a0\\(\\xi\\) in eine einstellige, berechenbare Funktion aus \\(P^{(1)}\\) abbilden und haben zum Schluss \u00fcber mehrere Wege also eine Nummerierung der einstelligen, berechenbaren Funktion\u00a0\\(P^{(1)}\\)\u00a0erreicht. Aber mal langsam.<\/p>\n<p>Die Nummerierung \\(\\varphi\\) besteht im Skript aus vier Komponenten:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Ordnungsfunktion \\(a\\) f\u00fcr das Alphabet \\(\\Omega\\), so dass wir mit \\(\\nu_\\Omega\\) die Standardnummerierung aller Worte aus \\(\\Omega\\), d.h. von \\(\\omega\\in\\Omega^{*}\\) haben. Also nicht nur Programme, sondern auch Kauderwelsch wie z.B. \\(&#8222;1B(:&#8220;\\).<\/li>\n<li>\\(\\nu_P : \\mathbb{N} \\rightarrow BP\\), z.B. \\(\\nu_P(i)\\) als die Nummerierung des Bandprogramms \\(i\\). Es ist definiert durch:<\/li>\n<li>\\(\\nu_P(i)=\\begin{cases}\\nu_\\Omega(i)&amp;\\text{ wenn }\\nu_\\Omega(i)\\in{BP}\\\\&#8220;(:B,,)&#8220;&amp;\\text {sonst}\\end{cases}\\)\n<p>Wir bekommen damit zur Nummer \\(i\\) das zugeh\u00f6rige Bandprogramm wenn es tats\u00e4chlich ein Bandprogramm ist. Oder einfach nur eine Endlosschleife wenn die Nummer \\(i\\) zu irgendwelchem Kauderwelsch geh\u00f6rt, denn mit \\(\\nu_\\Omega\\) haben wir (siehe oben) alle Worte \u00fcber \\(\\Omega\\), d.h. auch Unsinn, nummeriert.<\/li>\n<li>\\(\\nu_M : \\subseteq \\Omega^* \\rightarrow BM\\), damit bekommen wir zum Wort \\(\\omega\\) aus \\(\\Omega^{*}\\) die zugeh\u00f6rige Bandmaschine \\(M\\) (dazu gleich mehr)<\/li>\n<li>Funktion \\(\\xi:BM \\rightarrow P^{(1)}\\) mit \u00a0\\(\\xi(M) := \\iota^{-1}{f{_M}}\\iota\\). \\(\\xi(M)\\) ist also die Funktion aus \\(P^{(1)}\\), welche die Funktion der Bandmaschine \\(M\\) berechnet.<\/li>\n<\/ul>\n<p>Damit kann die Standardnummerierung \\(\\varphi\\) als eine Komposition zwischen \\(\\xi\\circ\\nu_M\\circ\\nu_P\\) definiert werden.<\/p>\n<p>Das <strong>Problem<\/strong> ist nun, dass diese Standardnummerierung \\(\\varphi\\)\u00a0<strong>nicht bijektiv<\/strong> ist, wie die Standardnummerierung \\(\\nu_\\Sigma\\)! Das liegt an der Surjektivit\u00e4t der verwendeten Funktionen, u.a. \\(\\xi :BM \\rightarrow P^{(1)}\\). Denn zu einer Funktion aus \\(P^{(1)}\\) kann es durchaus mehrere Bandmaschinen aus \\(BM\\) geben, die die Funktion berechnen: wir f\u00fcgen der Berechnungsroutine einfach ein paar sinnlose Schleifen hinzu und haben so eine neue Maschine, aber immer noch die alte, berechnete Funktion.<\/p>\n<p>Jedoch ist sie trotzdem total, denn die Nummerierung aller Bandprogramme\u00a0\\(\\nu_P : \\mathbb{N} \\rightarrow BP\\) ist ja total: wir erwischen durch die Definition von \\(\\nu_P\\) tats\u00e4chlich nur richtige Bandprogramme. Und zwar alle.<\/p>\n<p>Und zu einem Bandprogramm bekommen wir die zugeh\u00f6rige Bandmaschine mit \\(\\nu_M\\).\u00a0Der Definitionsberech der Funktion \\(\\nu_M\\) ist durch die Totalit\u00e4t von \\(\\nu_P\\) die komplette Menge \\(BP\\).<\/p>\n<p>Die Komposition aus \\(\\nu_M(\\nu_P)\\) ist damit auch total. Und weil \\(\\xi : BM\\rightarrow{P^{(1)}}\\) auch total ist (wir haben zu allen Funktionen aus \\(P^{(1)}\\) min. eine Bandmaschine, die sie berechnet), ist die Komposition\u00a0\\(\\xi\\circ\\nu_M\\circ\\nu_P=\\xi(\\nu_M(\\nu_P))\\) ebenfalls total.<\/p>\n<p>Um es etwas deutlicher zu machen, holen wir uns Beispiele und bauen auf diesen dann die Definition auf:<\/p>\n<p>Zun\u00e4chst haben wir ein Alphabet \\(\\Omega\\), welches unsere Zeichen<\/p>\n<p style=\"padding-left: 30px;\">\\(\\Omega:=(1\\mid{B}\\mid{(}\\mid{)}\\mid{,}\\mid{:}\\mid{R}\\mid{L})\\)<\/p>\n<p>beinhaltet. Achtung \\(\\mid\\) ist unser Trennzeichen, da das Komma zum Alphabet\u00a0\\(\\Omega\\) geh\u00f6rt.<\/p>\n<p>Aus diesen Zeichen kann ein Bandbefehl \\(BB\\) unseres Programms bestehen, welches die Form<\/p>\n<p style=\"padding-left: 30px;\">\\((1^m:\\beta,1^n)\\) mit \\(\\beta\\in\\{B,1,R,L\\}\\)\u00a0oder<\/p>\n<p style=\"padding-left: 30px;\">\\((1^m:\\beta,1^k,1^n)\\) mit\u00a0\\(\\beta\\in\\{B,1\\}\\)<\/p>\n<p>hat. Das kennt Ihr alles schon von den Turingmaschinen. Der erste Befehl der Marke \\(1^m\\) schreibt entweder ein \\(B\\), eine \\(1\\) auf das Band oder geht nach \\(L\\)inks oder \\(R\\)echts und springt anschlie\u00dfend in die Marke \\(1^n\\).<\/p>\n<p>Der zweite Befehl ist eine Verzweigung: in der Marke \\(1^m\\) wird gepr\u00fcft ob unter dem Lesekopf aktuell ein \\(B\\) oder eine \\(1\\) steht. Ist das der Fall, wird in die Marke \\(1^k\\) verzweigt und ansonsten in die Marke \\(1^n\\) gesprungen.<\/p>\n<p>An den Beispiel weiter unten wird es gleich deutlicher.<\/p>\n<p>Ein Bandbefehl aus der Menge \\(BB\\) ist damit ein Wort \u00fcber \\(\\Omega\\), d.h. \\(BB\\subseteq\\Omega^{*}\\). Ein Bandprogramm aus der Menge \\(BP\\) ist eine Folge von Bandbefehlen (es kann auch nur eines seit) und ist damit auch nur eine Kombination aus Worten \u00fcber \\(\\Omega\\):\u00a0\\(BP\\subseteq\\Omega^{*}\\)<\/p>\n<p>Kommen wir nun zu unserer Funktion, die uns zu einem Bandprogramm aus \\(BP\\) eine Bandmaschine aus \\(BM\\) gibt, die die gleiche Funktion berechnet:<\/p>\n<p style=\"padding-left: 30px;\">\\(\\nu_M:BP\\rightarrow BM\\)<\/p>\n<p>Die Maschine \\(M\\in{BM}\\), die das Bandprogramm \\(\\omega\\in{BP}\\), welches aus einer Folge von Bandbefehlen aus der Menge \\(BB\\) besteht, berechnet, wird durch ein Flussdiagramm \\(F\\) beschrieben. Damit gilt:<\/p>\n<p style=\"padding-left: 30px;\">\\(M=\\nu_M(\\omega)\\in{BM}\\)<\/p>\n<p>D.h. mit der Funktion \\(\\nu_M(\\omega)\\) bekommen wir zum Bandprogramm \\(\\omega\\) die passende Maschine \\(M\\)<\/p>\n<p>Wir haben noch die Definition von \\(F\\) im Kopf? Nein? Macht nichts: \\(F := \\{Q,D_{\\{1,B\\}},\\sigma, q_0\\}\\).<\/p>\n<p style=\"padding-left: 30px;\">\\(Q\\): ist die Menge unserer Marken, d.h. die Beschriftung der Befehle und Verzweigungen (Rechtecke und Rauten) im Flussdiagramm.<\/p>\n<p style=\"padding-left: 30px;\">\\(D\\): ist unser Arbeitsalphabet. Wir beschr\u00e4nken uns im Skript auf \\(\\{1,B\\}\\), da sie die einzigen Zeichen sind, die wir ben\u00f6tigen (Satz \u00fcber <a title=\"TIA: Turing-Maschinen, Hilfssymbole und (Lernziele KE3, Update 2)\" href=\"https:\/\/fernuni.digreb.net\/?p=754\">Hilfssymbole<\/a>!)<\/p>\n<p style=\"padding-left: 30px;\">\\(\\sigma\\): die auszuf\u00fchrenden Aktionen f\u00fcr die Marken. Ist z.B. \\(n\\) eine Marke, so ist \\(\\sigma(n)\\) der auszuf\u00fchrende Befehl.<\/p>\n<p style=\"padding-left: 30px;\">\\(q_0\\): unsere Startmarke. Diese ist der Definition nach das erste Element aus \\(\\omega\\), d.h. der erste Befehl.<\/p>\n<p>Wir \u00fcberf\u00fchren also die Folge von Bandbefehlen im Endeffekt einfach in ein Flussdiagramm. Das geschieht nachfolgendem Schema:<\/p>\n<p>F\u00fcr \\((1^n:\\beta,1^k)\\) bekommen wir<\/p>\n<p><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/rechteck.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-1005\" style=\"margin-left: 120px; margin-right: 3000px;\" title=\"rechteck\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/rechteck.png\" alt=\"\" width=\"120\" height=\"72\" \/><\/a><\/p>\n<p>und f\u00fcr\u00a0\\((1^n:\\beta,1^m,1^k)\\) gibt es ein<\/p>\n<p><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/raute.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-1006\" style=\"margin-left: 100px; margin-right: 200px;\" title=\"raute\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/raute.png\" alt=\"\" width=\"180\" height=\"114\" \/><\/a><\/p>\n<p>Was mich zun\u00e4chst aus dem Konzept gebracht hat, sind Befehle und \u00dcbertragung dieser in ein Flussdiagramm in folgender Form:\u00a0\\((:1,1,1^2)\\), doppelte Zuweisungen zu einer Marke und \\(HALT\\)-Befehle. Die folgenden S\u00e4tze liefern hierzu den Schl\u00fcssel (Harald aus der NG hat mich hier drauf gesto\u00dfen. Danke nochmal):<\/p>\n<p style=\"padding-left: 30px;\">1. Falls es f\u00fcr eine Zahl\/Marke \\(k\\) mehrere Befehle gibt, so z\u00e4hlt nur der erste von links.<\/p>\n<p style=\"padding-left: 30px;\">2. Kommt irgendwo eine Zahl\/Marke \\(k\\) vor und beginnt kein Befehl mit \\(1^k\\), so ist es der HALT-Befehl.<\/p>\n<p><strong>Beispiel<\/strong>: aus dem Skript \\(\\omega = (1^2:1,,1)(:1,1,1^2)(:B,,)\\)<\/p>\n<p style=\"padding-left: 30px;\">Was m\u00fcssen wir hier also zun\u00e4chst tun? Wir schreiben uns alle Marken raus, die wir finden: 2 (aus \\((1^2:&#8230;)\\)), 0 (aus \\((:&#8230;)\\)) und 1 (aus \\((&#8230;,1)\\)). Nun schauen wir uns die Definitionen unserer Marken 0,1 und 2 an.<\/p>\n<ul style=\"list-style-type: square; padding-left: 60px;\">\n<li><strong>Marke 0<\/strong>: \\((:1,1,1^2)\\). Bedeutet: wenn \\(1\\), gehe zu Marke \\(1\\), ansonsten zu Marke \\(2\\). \\((:B,,)\\) wird ignoriert, da doppelte Zuweisung.<\/li>\n<li><strong>Marke 1<\/strong>: \\(HALT\\). Es wird auf die Marke \\(1\\) in Marke \\(0\\) und \\(2\\) verwiesen, aber es gibt keinen Befehl daf\u00fcr. Also ist es unsere \\(HALT\\)-Marke.<\/li>\n<li><strong>Marke 2<\/strong>: \\((1^2:1,,1)\\). Bedeutet: wenn \\(1\\), gehe zu Marke \\(0\\), ansonsten zu Marke \\(1\\). Ist unsere erste Marke und daher auch unser Einstiegspunkt im Flussdiagramm.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Mit diesen Informationen k\u00f6nnt Ihr euch nun das dazugeh\u00f6rige Flussdiagramm eurer Maschine \\(M\\) aufmalen (versucht es mal selbst und pr\u00fcft eure L\u00f6sung mit dem Spoiler-Ausklapp-Text unten) und habt damit euer \\(\\nu_M(\\omega)\\).<\/p>\n<p><a class=\"spoiler_link_show\" href=\"javascript:void(0)\" onclick=\"wpSpoilerToggle(document.getElementById('id1245198551'), this, 'L\u00f6sung zeigen', 'L\u00f6sung verstecken')\">L\u00f6sung zeigen<\/a>\n<div class=\"spoiler_div\" id=\"id1245198551\" style=\"display:none\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe712.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone  wp-image-1015\" style=\"margin-left: 100px; margin-right: 300px;\" title=\"aufgabe712\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe712-248x300.png\" alt=\"\" width=\"149\" height=\"180\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe712-248x300.png 248w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe712.png 385w\" sizes=\"auto, (max-width: 149px) 100vw, 149px\" \/><\/a><\/div>\n<\/p>\n<p>Und nun tun wir das wozu wir hier sind: wir definieren wir die Standardnummerierung \\(\\varphi\\) dem Skript nach.<\/p>\n<blockquote>\n<ol style=\"padding-left: 30px;\">\n<li>Ordnungsfunktion \\(a\\), welche die Zeichen (siehe oben) unserer Programmiersprache nummeriert. \\(a_1 = 1\\), \\(a_2 = B, &#8230; a_8 = L\\), usw. Mit \\(\\nu_\\Omega\\) wird dann die Standardnummerierung von \\(\\Omega^*\\) bezeichnet, denn \\(\\Omega^*\\) beinhaltet (wir denken wieder an den Beitrag \u00fcber die Standardnummerierung) ja alle Worte \u00fcber diesem Alphabet.D.h. wir k\u00f6nnen diese Kombinationen aus diesen Zeichen durchnummerieren.<\/li>\n<li>Mit \\(\\nu_P : \\mathbb{N} \\rightarrow BP\\) haben wir eine Funktion, die uns zu einer Zahl \\(i\\) das zugeh\u00f6rige Bandprogramm aus \\(BP\\) (bzw. eine Kombination aus den oben definierten Zeichen) zur\u00fcckgibt: n\u00e4mlich \\(\\nu_\\Omega (i)\\) (aber nur wenn es ein echtes Bandprogramm ist, welche wiederum aus Bandbefehlen der Menge \\(BB\\) besteht. Es k\u00f6nnte aber auch irgendwelches Kauderwelsch sein, was nicht ausf\u00fchrbar ist).\n<p>Wenn es also Kauderwelsch ist, wird ein \\(((:B,,)\\). zur\u00fcckgegeben, d.h. eine Endlosschleife. Damit ist\u00a0\\(\\nu_P\\) nur <a href=\"http:\/\/de.wikipedia.org\/wiki\/Surjektivit%C3%A4t\">surjektiv<\/a>, da man einige Nummern \\(i\\) mit \\(\\nu_P(i)\\) durchaus mehrfach auf\u00a0\\(((:B,,)\\) abbildet wenn sie nicht Nummern von legitimen Bandprogrammen sind.<\/li>\n<li>\\(\\nu_M : \\subseteq \\Omega^* \\rightarrow BM\\), damit bekommen wir zum Wort \\(\\omega\\) aus \\(\\Omega^{*}\\) (von wem wir durch \\(\\nu_P\\) sicher wissen, dass es sich um ein Bandprogramm handelt), die zugeh\u00f6rige Bandmaschine \\(M\\)<\/li>\n<li>Durch \\(\\xi:BM\\rightarrow P^{(1)}\\) mit \u00a0\\(\\xi(M):=\\iota^{-1}{f{_M}}\\iota\\) haben wir die von der Bandmaschine \\(M\\) berechnete Funktion aus \\(P^{(1)}\\). Zudem: \\(\\iota(i) = 1^i\\). Bei den beispiel gleich wird es deutlicher.<\/li>\n<li>Als letztes definieren wir \\(\\varphi:\\mathbb{N}\\rightarrow P^{(1)}\\) durch:\u00a0\\(\\varphi_i=\\varphi(i)=\\xi\\nu_M\\nu_P (i)\\). Auch hier hilft zum besseren Verst\u00e4ndnis das Ausklammern:\u00a0\\(\\varphi_i=\\varphi(i) = \\xi(\\nu_M (\\nu_P (i)))\\).<\/li>\n<\/ol>\n<\/blockquote>\n<p>Punkt 4 baut auf der ganzen Vorarbeit auf und standard-nummeriert uns schlussendlich unsere einstelligen, berechenbaren Funktionen aus \\(P^{(1)}\\). Und nicht vergessen: die Standardnummerierung von \\(P^{(1)}\\) ist <strong>surjektiv<\/strong> und <strong>total<\/strong>!<\/p>\n<p>Ein Beispiel w\u00e4re hilfreich, oder? Ich nehme gleich das Beispiel aus dem Skript und rechne es Schritt f\u00fcr Schritt durch.<\/p>\n<p><strong>Beispiel<\/strong>: \\(\\omega_1 = (: R,1)(1:B,11,)\\)<\/p>\n<p style=\"padding-left: 30px;\">Die Nummer des Bandprogramms ist in der Aufgabenstellung \\(n_1\\). Das ist relativ willk\u00fcrlich gew\u00e4hlt uns ist uns auch ziemlich egal. Wir k\u00f6nnten durch die ordnungsfunktion \\(a\\) auch eine echte G\u00f6delnummer angeben, aber wozu? Spielt hier keine gro\u00dfe Rolle.<\/p>\n<p style=\"padding-left: 30px;\">Wir haken nun die komplette Definition der Standardnummerierung ab:<\/p>\n<p style=\"padding-left: 30px;\">1. Als Ordnungsfunktion \\(a\\) nutzen wir die Funktion aus der Definition und haben so auch unsere Nummerierung von allen Worten \u00fcber dem Alphabet \\(\\Omega\\), n\u00e4mlich \\(\\nu_\\Omega\\).<\/p>\n<p style=\"padding-left: 30px;\">2. Nun brauchen wir \\(\\nu_P(n_1)\\). Da unser Wort\u00a0\\(\\omega_1 = (: R,1)(1:B,11,)\\) korrekt ist und aus \\(BP\\) kommt, bekommen wir das zur\u00fcck (siehe Definition):<\/p>\n<p style=\"padding-left: 60px;\">\\(\\nu_P(n_1)=\\nu_\\Omega(n_1)=\\omega_1=(: R,1)(1:B,11,)\\).<\/p>\n<p style=\"padding-left: 30px;\">W\u00e4re \\((: R,1)(1:B,11,)\\) nicht in \\(BP\\), so h\u00e4tten wir nur ein \\((:B,,)\\) bekommen. Daraus basteln wir uns nun ein wundersch\u00f6nes Flussdiagramm. Auch hier: alleine versuchen, dann L\u00f6sung \u00f6ffnen.<\/p>\n<p style=\"padding-left: 30px;\"><a class=\"spoiler_link_show\" href=\"javascript:void(0)\" onclick=\"wpSpoilerToggle(document.getElementById('id910688287'), this, 'L\u00f6sung zeigen', 'L\u00f6sung verstecken')\">L\u00f6sung zeigen<\/a>\n<div class=\"spoiler_div\" id=\"id910688287\" style=\"display:none\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe717.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-medium wp-image-1025\" style=\"margin-left: 150px; margin-right: 200px;\" title=\"aufgabe717\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe717-300x120.png\" alt=\"\" width=\"300\" height=\"120\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe717-300x120.png 300w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe717.png 614w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><\/div>\n<\/p>\n<p style=\"padding-left: 30px;\">Was macht das sch\u00f6ne St\u00fcck? Nehmen wir an wir geben in die Maschine \\(11\\) und starten bei Marke \\(0\\). Der Lesekopf ist anfangs ja auf dem letzten \\(B\\) (Blank) vor dem Eingabewort. Wir gehen nun nach rechts (Marke \\(0\\)) auf die erste \\(1\\) auf dem Band. Dann sind wir bei Marke \\(2\\) und pr\u00fcfen ob unter dem Lesekopf ein \\(B\\) (Blank) steht. Tut er das, gehen wir zu Marke \\(2\\) und halten. Befindet sich jedoch eine \\(1\\) unter dem Lesekopf, gehen wir wieder zu Marke \\(0\\) und tun das so lange bis wir auf ein Blank treffen und unser Eingabewort damit zu Ende ist.<\/p>\n<p style=\"padding-left: 30px;\">Soweit so unspektakul\u00e4r.<\/p>\n<p style=\"padding-left: 30px;\">Die so berechnete Funktion \\(f\\) unserer Maschine \\(M\\) ist somit: \\(f_{M}(1^m) = 1^m\\). Zur Auffrischung. Das \\(m\\) ist einfach nur die Anzahl der Einsen. Wir geben also \\(m\\) Einsen auf das Band und am Ende steht der Lesekopf auf Position \\(m+1\\) und wir haben als Ausgabe links vom Lesekopf also \\(m\\) Einsen auf dem Band. Sprechen wir von &#8222;normalen&#8220; Funktionen, die dezimal (\\(x\\)) und nicht un\u00e4r (\\(1^{x}\\)) definiert sind, w\u00e4re das \\(f(x) = x\\).<\/p>\n<p style=\"padding-left: 30px;\">Nun brauchen wir noch unser \\(\\varphi\\) (ich erkl\u00e4re die Berechnung weiter unten um die \u00dcbersichtlichkeit nicht zu killen):<\/p>\n<p style=\"padding-left: 30px;\">\\(\\begin{array}{lcl}\\varphi_{n_1}(m)&amp;=&amp; \\varphi(n_1)(m)&amp; {*1} \\\\ {} &amp;=&amp; \\xi(\\nu_M(\\nu_P(n_1)))(m) &amp; {*2} \\\\ {} &amp;=&amp; \\xi(\\nu_M((: R,1)(1:B,11,)))(m) &amp;\\mbox{*3}\\\\{} &amp;=&amp; \\xi(M)(m)&amp;\\mbox{*4}\\\\{}&amp;=&amp;\\iota^{-1}(f_M(\\iota(m)))&amp;\\mbox{*5}\\\\{}&amp;=&amp;\\iota^{-1}(f_M(1^m))&amp;\\mbox{*6}\\\\{}&amp;=&amp;\\iota^{-1}(1^m)&amp;\\mbox{*7}\\\\{}&amp;=&amp;m&amp;\\mbox{*8}\\end{array}\\)<\/p>\n<p style=\"padding-left: 30px;\">Fertig!<\/p>\n<p>Wir haben es also geschafft mit \\(\\varphi\\) die Funktionen aus \\(P1 {(1)}\\) zu nummerieren. Geben wir \\(\\varphi\\) also die dezimale Nummer der Maschine und einen dezimalen Parameter\u00a0aus \\(\\mathbb{N}\\) mit, bekommen wir als Ausgabe auch einen dezimalen Ausgabewert zur\u00fcck, obwohl die Maschine, die diesen Wert berechnet nur mit der un\u00e4ren Darstellung \\(1^m\\) arbeitet. Wir verk\u00fcrzen das in den Merksatz:<\/p>\n<blockquote><p><em>\\(\\varphi(i)\\) ist die von der \\(i-ten\\) Bandmaschine berechnete Funktion aus \\(P^{(1)}\\), der Menge der einstelligen partiell-rekursiven Funktionen.<\/em><\/p><\/blockquote>\n<p>Hier die Erkl\u00e4rung der Berechnung von oben (Danke an Carsten f\u00fcr den letzten Hinweis).<\/p>\n<p style=\"padding-left: 30px;\">\\(*1\\): nur sch\u00f6ner umgeschrieben, einfach der Definition nach<\/p>\n<p style=\"padding-left: 30px;\">\\(*2\\): der Definition nach ist \\(\\varphi(i)=\\xi\\nu_M\\nu_P(i)\\). Ich habe hier nur ausgeklammert. Und da wir\u00a0\\(\\varphi(i)\\) mit einem Parameter \\(m\\) f\u00fcttern, h\u00e4ngt er eben mit hinten dran.<\/p>\n<p style=\"padding-left: 30px;\">\\(*3\\): \\(n_1\\) war ja die willk\u00fcrliche Nummer unserer Maschine. \\(\\nu_P(n_1)\\) ist demnach unser Wort \\(\\omega_1 = (: R,1)(1:B,11,)\\) f\u00fcr die Maschine (siehe Definition von \\(\\nu_P\\)).<\/p>\n<p style=\"padding-left: 30px;\">\\(*4\\): \\(\\nu_M((: R,1)(1:B,11,))\\) ist also unsere Maschine \\(M\\) mit dem Flussdiagramm, welche unsere Funktion berechnet. Die von der Maschine \\(M\\) berechnete Funktion nennen wir ja immer \\(f_M\\).<\/p>\n<p style=\"padding-left: 30px;\">\\(*5\\): \\(\\xi(M)\\) ist unserer Definition nach ja eben \\(\\iota^{-1}(f_M(\\iota))\\). Da wir ja immernoch den Parameter \\(m\\) mitschleppen, h\u00e4ngt er weiterhin einfach nur mit.<\/p>\n<p style=\"padding-left: 30px;\">\\(*6\\): Jetzt wird es lustig. In der Definition steht, dass \\(\\iota(m) = 1^m\\) ist. D.h. einfach die Anzahl von Einsen. \\(\\iota(4)\\) w\u00e4re z.B. \\({} = 1^4 = 1111\\). Das dient uns als Eingabe f\u00fcr unsere Funktion \\(f_M\\). Die Bandmaschinen werden ja mit der un\u00e4ren Darstellung von Dezimalzahlen gef\u00fcttert. Daher brauchen wir hierf\u00fcr\u00a0\\(\\iota\\) um eine Dezimalzahl in ihre un\u00e4re Darstellung umzuwandeln damit wir unsere Maschine damit bedienen k\u00f6nnen.<\/p>\n<p style=\"padding-left: 30px;\">\\(*7\\): Was macht unsere Funktion \\(f_M\\) wenn man sie mit der Eingabe \\(1^m\\) startet? Genau: sie gibt uns als Ausgabe auch wieder \\(1^m\\) zur\u00fcck.<\/p>\n<p style=\"padding-left: 30px;\">\\(*8\\): Und \\(\\iota^{-1}\\) ist die Inverse zu \\(\\iota\\) und macht genau das umgekehrte. Es bekommt als Parameter die un\u00e4re Darstellung \\(1^m\\)\u00a0der Zahl \\(m\\) als Parameter und gibt uns die dezimale Darstellung \\(m\\) zur\u00fcck.<\/p>\n<p>Damit haben wir auch die Standardnummerierung \\(\\varphi\\) der einstelligen, berechenbaren Funktionen \\(P^{(1)}\\) abgehakt.<\/p>\n<p>Ich gehe in diesem Abschnitt jetzt nicht strikt den Lernzielen, da zu dieser Aufgabe auch noch die\u00a0<strong>Standardkomplexit\u00e4t<\/strong>\u00a0\\(\\Phi\\) geh\u00f6rt. Im anderen Beitrag w\u00e4re sie nicht wirklich gut aufgehoben. Aus diesem Grund nehme ich das noch hier auf. Aber zun\u00e4chst die Antwort zum Lernziel.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Die Standardnummerierung \\(\\varphi\\) der einstelligen, berechenbaren Funktionen \\(P^{(1)}\\) besteht aus den Komponenten:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Ordnungsfunktion \\(a\\) mit \\(a:\\{1,&#8230;,8\\}\\subseteq\\Omega\\) f\u00fcr die geordnete Nummerierung des Alphabets \\(\\Omega\\)<\/li>\n<li>\\(\\nu_\\Omega\\). Durch die Ordnungsfunktion induzierte\u00a0Standardnummerierung von\u00a0von \\(\\Omega^{*}\\).<\/li>\n<li>\\(\\nu_P(i):\\mathbb{N}\\rightarrow BP\\).\u00a0Funktion um zu einer Nummer \\(i\\) das zugeh\u00f6rige Bandprogramm\u00a0zu bekommen wenn \\(\\nu_\\Omega(i)\\) tats\u00e4chlich ein Bandprogramm ist<\/li>\n<li>\\(\\nu_M(i):BP\\rightarrow BM\\).\u00a0Funktion um zur einem Bandprogramm die zugeh\u00f6rige Bandmaschine zu bekommen.<\/li>\n<li>\\(\\xi:BM\\rightarrow P^{(1)}\\). Funktion um zu einer Maschine die zugeh\u00f6rige Funktion zu erhalten.<\/li>\n<\/ul>\n<p>Dadurch ist es m\u00f6glich, ausgehend von einer Zahl \\(i\\in\\mathbb{N}\\) eine Funktion aus \\(\\varphi(i)\\in{P^{(1)}}\\) zu erhalten:<\/p>\n<p style=\"padding-left: 30px;\">\\(\\varphi: \\mathbb{N}\\rightarrow BP\\rightarrow BM\\rightarrow P^{(1)}\\)<\/p>\n<h2>Lernziel 2<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung des \\(\\Phi\\)-Theorems<\/em><\/p>\n<p>Wir starten zun\u00e4chst mit der Definition der <strong>Standardkomplexit\u00e4t<\/strong> selbst:<\/p>\n<blockquote><p>\\(\\Phi\\) hei\u00dft Standardkomplexit\u00e4t zu \\(\\varphi\\) und ist definiert durch:<\/p>\n\\(\\Phi(i)(x):=\\Phi_i(x) := SZ_i(q_{0i}, (\\varepsilon, B, 1^x))\\)\n<p>\\(q_{oi}\\) ist die Anfangsmarke, \\(SZ_i\\) die Schrittzahlfunktion der Bandmaschine \\(\\nu_M(\\nu_P(i))\\).<\/p><\/blockquote>\n<p>Was haben wir hier?<\/p>\n<p>Im Endeffekt bekommen wir mit \\(\\Phi\\) also einfach nur die Anzahl der Schritte, die die Maschine \\(\\nu_M(\\nu_P(i))\\)\u00a0braucht um f\u00fcr eine Eingabe \\(x\\), ausgehend von Marke \\(q_{oi}\\) und der Bandbelegung \\((\\varepsilon, B, 1^x)\\) (unter dem Lesekopf steht das Blank \\(B\\) vor der Eingabe, einer un\u00e4ren Darstellung von \\(x\\)) die Berechnung durchzuf\u00fchren und schlie\u00dflich auf \\(HALT\\) stehen zu bleiben (oder eben nicht). Daf\u00fcr brauchen wir die\u00a0<a title=\"TI: Einzelschritt- und Schrittzahlfunktion sowie \u00dcbergangsrelationen (Update)\" href=\"https:\/\/fernuni.digreb.net\/?p=512\">Schrittzahlfunktion<\/a>\u00a0\\(SZ\\), die wir bereits kennen.<\/p>\n<p>\\(\\nu_M(\\nu_P(i))\\) schreckt euch doch nach dem Abschnitt zur Standardnummerierung \\(\\varphi\\) von \\(P^{(1)}\\) doch auch nicht mehr, so dass ich es nicht an einem Beispiel aufl\u00f6sen muss, oder? Nein? Gut. Dann machen wir weiter.<\/p>\n<p>Die Standardkomplexit\u00e4t \\(\\Phi\\) zu \\(\\varphi\\) hat zudem drei sch\u00f6ne Eigenschaften:<\/p>\n<blockquote><p>1. Die Funktion zur Standardkomplexit\u00e4t \\(\\Phi\\) einer Maschine \\(i\\) geh\u00f6rt zu den einstelligen, berechenbaren Funktionen \\(P^{(1)}\\).<\/p>\n<p>Ist auch klar, denn es ist die Rechenzeitfunktion der \\(i\\)-ten Bandmaschine.<\/p>\n<p>2. Der Definitionsbereich von \\(\\Phi_i\\) ist gleich dem Definitionsbereich von \\(\\varphi_i\\). Beide Funktionen verwenden den selben Parameter \\(x\\) aus \\(\\mathbb{N}\\) f\u00fcr ihre Eingabe.<\/p>\n<p>W\u00e4hrend \\(\\varphi_i(x)\\) uns das Ergebnis \\(y\\) aus seinem Bildbereich liefert, bekommen wir mit \\(\\Phi_i(x)\\) die zur Berechnung von \\(y\\) notwendige Schrittanzahl \\(z\\).<\/p>\n<p>Dass \\(y \\neq z\\) sein kann (mit etwas Zufall ist die Anzahl der Schritte gleich dem Ergebnis, aber das ist dann auch nur Zufall), f\u00fcr das gleiche \\(x\\), ist auch klar. Aber es bleibt das gleiche \\(x\\), daher ist<\/p>\n<p style=\"padding-left: 30px;\">\\(Def(\\Phi_i) = Def(\\varphi_i)\\).<\/p>\n<p>3. Die Menge \\(\\{(i,x,t) \\in \\mathbb{N}^3\\mid \\Phi_i(x) \\leq t\\}\\) ist rekursiv\/entscheidbar.<\/p><\/blockquote>\n<p>W\u00e4hrend Punkt Eins und Zwei wahrscheinlich klar sind, wiederholen wir f\u00fcr Punkt 3 noch einmal die Definition einer rekursiven\/entscheidbaren Menge aus einem alten Beitrag. Wann ist eine Menge also rekursiv\/entscheidbar? Genau dann wenn die\u00a0<a title=\"TI: Entscheidbarkeit und charakteristische Funktion\" href=\"https:\/\/fernuni.digreb.net\/?p=909\">charakteristische Funktion<\/a>\u00a0berechenbar ist. Die charakteristische Funktion f\u00fcr \\(\\Phi\\) ist:<\/p>\n<p style=\"padding-left: 30px;\">\\(g_\\Phi(i,x,t)=\\begin{cases} 1, &amp; \\mbox{ falls } \\Phi_i(x) \\leq t \\\\ 0, &amp; \\mbox{ sonst}\\end{cases}\\)<\/p>\n<p>Was bedeutet das?<\/p>\n<p>Ganz einfach: wir bekommen mit der Funktion\u00a0\\(g_\\Phi(i,x,t)\\) eine \\(1\\) zur\u00fcck wenn die Maschine \\(\\nu_M(\\nu_P(i))\\)\u00a0bei der Eingabe von \\(x\\) nicht mehr als \\(t\\) Rechenschritte bis zur \\(HALT\\)-Marke braucht. Braucht sie mehr, so bekommen wir eine \\(0\\) zur\u00fcck.<\/p>\n<p>Als Beweis benutzen wir wieder eine Funktion, die unserem \\(h(i,n,t)\\) (Erl\u00e4uterung von \\(h\\) ist im n\u00e4chsten Lernziel) sehr \u00e4hnlich ist.<\/p>\n<p style=\"padding-left: 30px;\">\\(h(i,n,t) = \\begin{cases} 1+\\varphi_i(n), &amp; \\mbox{ falls } \\Phi_i(n) \\mbox{ existiert und } \\Phi_i(n) \\leq t\\\\ 0, &amp; \\mbox{ sonst }\\end{cases}\\)<\/p>\n<p>Der Beweis, dass diese Funktion berechenbar ist, geh\u00f6rt auch zu den Lernzielen. Wir schieben die Funktion dennoch hier dazwischen und holen den Beweis gleich nach.<\/p>\n<p>Was passiert also bei\u00a0\\(g_\\Phi(i,x,t)\\)?<\/p>\n<p style=\"padding-left: 30px;\">1. \\(\\Phi_i(x)\\) ist ja die kleinste Zahl \\(t\\), bei der \\(h(i,n,t) \\neq 0\\) gilt, da \\(\\Phi_i(x)\\) uns ja die Anzahl der Schritte liefert, die die Maschine \\(\\nu_M(\\nu_P(i))\\)\u00a0braucht um bei der Eingabe \u00a0\\(x\\) zum Ende der Berechnung zu kommen.<\/p>\n<p style=\"padding-left: 30px;\">2.\u00a0\\(\\Phi_i(x)\\) gibt es nur wenn es die Schrittzahlfunktion \\(SZ(q_{oi},(\\varepsilon,B,1^xB))\\) und auch die Ausgabe \\(\\varphi_i(x)\\) gibt. Ansonsten w\u00e4re sie nicht vorhanden: keine Ausgabe, keine Schritte, keine Standardkomplexit\u00e4t \\(\\Phi\\).<\/p>\n<p style=\"padding-left: 30px;\">3. Da \\(h\\) berechenbar ist (weisen wir gleich nach), auch Kompositionen aus den Funktionen berechenbar sind, so ist auch unsere charakteristische Funktion \\(g_\\Phi(i,x,t) = min(1,h(i,x,t))\\) berechenbar.<\/p>\n<p>Was \\(min(1,h(i,x,t))\\) sollte klar sein, ich schreibe es trotzdem mal auf:<\/p>\n<p>Wir bekommen mit der Funktion \\(min\\) den kleinsten Wert aus der Auswahl von zwei Werten. Und wir haben die Auswahl zwischen \\(1\\) und dem Funktionswert von \\(h(i,x,t)\\).<\/p>\n<p>Unser \\(h\\) gibt aber nur den Funktionswert zur\u00fcck wenn die Maschine die Berechnung mit maximal \\(t\\) Rechenschritten abschlie\u00dft, denn \\(t\\) ist die Anzahl der Schritte, die wir maximal rechnen d\u00fcrfen. Ansonsten gibt es nur den Zonk, \u00e4hm, ich meine die \\(0\\). In diesem Fall hat die Maschine bereits \\(t\\) Schritte gerechnet und ist noch nicht bei der \\(HALT\\)-Marke angekommen, d.h. die Berechnung ist nach \\(t\\) Schritten noch nicht zu Ende.<\/p>\n<p>Wir haben daher immer \\(min(1,0) = 0\\) wenn \\(\\Phi_i(x) &gt; t\\) oder \\(min(1,Funktionwert)=1\\) wenn\u00a0\\(\\Phi_i(x)\\leq t\\). Passt.<\/p>\n<p>Damit ist gewiesen, dass die Menge\u00a0\\(\\{(i,x,t) \\in \\mathbb{N}^3\\mid \\Phi_i(x) \\leq t\\}\\) tats\u00e4chlich rekursiv\/entscheidbar ist, denn wir k\u00f6nnen entscheiden ob Maschine \\(i\\) bei der Eingabe von \\(x\\) nach \\(t\\) Schritten h\u00e4lt oder nicht.<\/p>\n<p>Naja, streng genommen m\u00fcssen wir dazu noch \\(h\\) als berechenbar nachweisen, aber das tun wir ja gleich im 3. Lernziel.<\/p>\n<p>Und was ist mit der<\/p>\n<p><strong>Beispielaufgabe<\/strong> zu \\(\\omega_1 = (: R,1)(1:B,11,)\\)\u00a0von Oben?<\/p>\n<p style=\"padding-left: 30px;\">Die holen wir mit dem Wissen, das wir haben nun nach.\u00a0Hier noch einmal das Flussdiagramm damit Ihr nicht scrollen m\u00fcsst:<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe717.png\"><img loading=\"lazy\" decoding=\"async\" style=\"margin-left: 50px; margin-right: 250px;\" title=\"aufgabe717\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/aufgabe717-300x120.png\" alt=\"\" width=\"300\" height=\"120\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Wie viele Schritte braucht unser Flussdiagramm denn bei der Eingabe von z.B. \\(1^3\\), d.h. drei Einsen um bis zur \\(HALT\\)-Marke zu gelangen und wie sieht die Ausgabe dann aus? Spielt das Flussdiagramm einfach mal damit durch und Ihr werden feststellen, dass Ihr genau \\(8\\) Schritte braucht.<\/p>\n<p style=\"padding-left: 30px;\">Bei der Eingabekonfiguration von \\((0,(\\varepsilon,B,1^3))\\) kommen wir nach \\(8\\) Schritten dann bei der Endkonfiguration\u00a0\\((2,(1^3,B,\\varepsilon))\\) an. Wenn man das Flussdiagramm nun genauer betrachtet kommt man drauf, dass man bis zur Endkonfiguration genau \\(2*3+2\\) Schritte passiert hat. Bei der Eingabe von \\(m\\) Einsen muss man die Schleife \\(m\\) Mal passieren und f\u00fchrt so am Ende \\(2m+2\\) Schritte durch, was uns zu unserer \u00dcbergangsrelation f\u00fchrt:<\/p>\n<p style=\"padding-left: 60px;\">\\((0,(\\varepsilon,B,1^m) \\vdash^{2m+2} (2,(1^m,B,\\varepsilon))\\)<\/p>\n<p style=\"padding-left: 30px;\">Und da \\(\\Phi_{n_1}(m)\\) nun genau die Anzahl der Schritte ist bis die Maschine bei der Eingabe von \\(m\\) \\(HALT\\) erreicht, ist<\/p>\n<p style=\"padding-left: 60px;\">\\(\\Phi_{n_1}(m) = 2m+2\\)<\/p>\n<p style=\"padding-left: 30px;\">Damit ist die Standardkomplexit\u00e4t \\(\\Phi_{n_1}\\)\u00a0zu \\(\\varphi(n_1)\\) bei der Eingabe von \\(m\\) genau \\(2m+2\\). W\u00fcrde die Maschine nicht halten, so w\u00e4re\u00a0\\(\\Phi_{n_1} = div\\).<\/p>\n<p>Hiermit ist die Standardnummerierung f\u00fcr \\(P^{(1)}\\) abgehakt und wir k\u00fcmmern uns jetzt um den Beweis von \\(h\\).<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: das \\(\\Phi\\)-Theorem besagt drei Dinge:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>dass die Schrittzahlfunktion \\(\\Phi_i=SZ_i\\) der Maschine \\(i\\) zu den einstelligen, berechenbaren Funktionen \\(P^{(1)}\\) geh\u00f6rt<\/li>\n<li>der Definitionsbereich von \\(\\Phi_i\\) ist gleich dem Definitionsbereich von \\(\\varphi_i\\), da beide Funktionen den selben Eingabeparameter \\(x\\) ben\u00f6tigen<\/li>\n<li>und die Menge\u00a0\\(\\{(i,x,t)\\in\\mathbb{N}^3\\mid \\Phi_i(x) \\leq t\\}\\) rekursiv\/entscheidbar ist, da die charakteristische Funktion berechenbar ist.<\/li>\n<\/ul>\n<p>Mit dieser Standardkomplexit\u00e4t k\u00f6nnen wir bestimmen wie viele Berechnungsschritte die Maschine \\(i\\) bei der Eingabe von \\(x\\) ben\u00f6tigt (\\(\\Phi_i(x)\\)) oder feststellen ob die Maschine \\(i\\) bei der Eingabe von \\(x\\) nach \\(t\\) Berechnungsschritten h\u00e4lt oder nicht (\\(g_\\Phi(i,x,t)\\)) um die Menge \\((i,x,t)\\in\\mathbb{N}^3\\) zu entscheiden.<\/p>\n<h2>Lernziel 3<\/h2>\n<p style=\"padding-left: 30px;\"><em>Beweis der Berechenbarkeit von \\(h:\\mathbb{N}^3\\rightarrow\\mathbb{N}\\)<\/em><\/p>\n<p>F\u00fcr die Formalisierung des utm-Theorems brauchen wir diese hilfreiche Funktion auch, also aufpassen! Definieren wir \\(h\\) zun\u00e4\u00fcchst:<\/p>\n<blockquote><p>\\(h:\\mathbb{N}^3 \\rightarrow \\mathbb{N}\\) \u00a0mit<\/p>\n\\(h(i,n,t) = \\begin{cases} 1+\\varphi_i(n), &amp; \\mbox{ falls } \\Phi_i(n) \\mbox{ existiert und } \\Phi_i(n) \\leq t\\\\ 0, &amp; \\mbox{ sonst }\\end{cases}\\)<\/blockquote>\n<p>Okay, dreistellige Funktion auf den nat\u00fcrlichen Zahlen, die ein einstelliges Ergebnis ausgibt. Wir bekommen eine \\(1\\) und das Ergebnis der Maschine\u00a0\\(\\nu_M(\\nu_P(i))\\)\u00a0bei der Eingabe von \\(n\\) wenn die\u00a0<a title=\"TI: Standardnummerierung und -Komplexit\u00e4t Phi (KE5)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">Standardkomplexit\u00e4t<\/a>\u00a0\\(\\Phi_i\\) existiert und kleiner\/gleich \\(t\\) ist, d.h. wir kommen zum Ergebnis (\\(HALT\\)-Marke noch bevor wir \\(t\\) Rechenschritte absolviert haben). Ansonsten gibt es nur eine Null zur\u00fcck. Fair.<\/p>\n<p>Um zu beweisen, dass die Funktion \\(h\\) berechenbar ist wird wie folgt vorgegangen:<\/p>\n<p>Wir zeigen, dass die Wortfunktion zu \\(h\\) berechenbar ist. Anhand der\u00a0<a title=\"TI: Berechenbarkeit (Lernziele aus KE4, Update II)\" href=\"https:\/\/fernuni.digreb.net\/?p=837\">Standardnummerierung<\/a>\u00a0k\u00f6nnen wir ja Worte in Zahlen und Zahlen in Worte codieren. Unsere Wortfunktion w\u00e4re damit: \\(\\nu_\\Sigma h\\bar{\\nu_\\Sigma}^-1\\).<\/p>\n<p>Schaut euch die Standardnummerierung noch einmal an, falls euch das nicht mehr viel sagt. Anschlie\u00dfend basteln wir uns eine Turing-Maschine mit \\(f_M=\\nu_\\Sigma h\\bar{\\nu_\\Sigma}^-1\\). Diese Funktion sieht dann so aus:<\/p>\n<p style=\"padding-left: 30px;\">\\(f_M(1^i,1^n,1^t) = 1^{h(i,n,t)}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(1^{h(i,n,t)}=\\begin{cases} 1^{1+\\varphi_i(n)}, &amp; \\mbox{ falls } \\Phi_i(n) \\mbox{ existiert und } \\Phi_i(n) \\leq t\\\\ \\varepsilon, &amp; \\mbox{ sonst }\\end{cases}\\)<\/p>\n<p>F\u00fchren wir uns einfach mal vor Augen, dass die Turing-Maschine nur Eingaben in Form von \\(1^x\\), also \\(x\\) Mal die \\(1\\) entgegen nimmt und auch wieder ausgibt. F\u00fcr die Funktion \\(h\\) wandeln wir unsere \\(i, n\\) und \\(t\\) daher einfach in die entsprechende Anzahl ein Einsen um (un\u00e4re Darstellung einer Dezimalzahl).<\/p>\n<p>W\u00e4hrend wir bei der Funktion \\(h\\) als Ergebnis dann \\(1+\\) den dezimalen Ausgabewert, also \\(\\varphi_i(n)\\) bekommen h\u00e4tten, bekommen wir hier einfach die dazu entsprechende Anzahl von Einsen (\\(1^{1+\\varphi_i(n)}\\)); die un\u00e4re Darstellung des Ergebnisses. Das der Ausgabewert \\(0\\) jedoch nicht in unserem vorher definierten Alphabet f\u00fcr die Maschine ist, nutzen wir das leere Wort \\(\\varepsilon\\) zur Codierung von \\(0\\).<\/p>\n<p>Bevor ich hier den Beweis praktisch abschreibe, w\u00e4re es wahrscheinlich sinnig ihn direkt anhand eines Beispiels durchzuspielen. Wir nehmen wieder die Aufgabe aus dem ersten Teil:<\/p>\n<p><strong>Beispiel<\/strong>:\u00a0\u00a0\\((1^2:1,,1)(:1,1,1^2)(:B,,)\\)<\/p>\n<p style=\"padding-left: 30px;\">mit der zugeh\u00f6rigen Nummer \\(n_1\\), der willk\u00fcrlichen Eingabe \\( n=3\\) und den maximal durchzuf\u00fchrenden Rechenschritten \\(t=9\\).<\/p>\n<p style=\"padding-left: 30px;\">Ein Ergebnis sollten wir auch herausbekommen, da wir aus dem letzten Beitrag ja wissen, dass die Standardkomplexit\u00e4t \\(\\Phi_{n_1}(3)\\)\u00a0der Funktion ja \\(8\\) und bekanntlich ist \\(8&lt;9\\) ist. Unser \\(f_M\\) sieht mit der willk\u00fcrlichen Wahl der Eingangsparameter nun so aus:<\/p>\n<p style=\"padding-left: 30px;\">\\(f_M(1^{n_1},1^3,1^9) = 1^{h(n_1,3,9)}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(1^{h(n_1,3,9)}=\\begin{cases} 1^{1+\\varphi_{n_1}(3)}, &amp; \\mbox{ falls } \\Phi_{n_1}(3) \\mbox{ existiert und } \\Phi_{n_1}(3) \\leq 9\\\\ \\varepsilon, &amp; \\mbox{ sonst }\\end{cases}\\)<\/p>\n<p style=\"padding-left: 30px;\">Wir haben folgende Teil-Flussdiagramme mit den entsprechenden Aufgaben:<\/p>\n<ul style=\"list-style-type: square; padding-left: 60px;\">\n<li>\\(F_1\\): Transformiert die Eingabe auf die einzelnen B\u00e4nder (siehe unten).<\/li>\n<li>\\(F_2\\): Kopiert die Anfangsmarke auf Band \\(4\\).<\/li>\n<li>\\(F_3\\): Sucht auf Band \\(1\\) nach dem Befehl mit der Marke von Band \\(4\\). Wird keine passende Marke auf Band \\(1\\) gefunden, so muss es eine \\(HALT\\)-Marke sein.<\/li>\n<li>\\(F_4\\): Simuliert den gefundenen Befehl von Band \\(1\\) auf dem Band \\(2\\), wo unser Eingabewort steht.<\/li>\n<li>\\(F_5\\): Testet ob weitergerechnet werden darf, d.h. ob noch Einsen auf Band \\(3\\) stehen.<\/li>\n<li>\\(F_6\\): Subtrahiert eine Eins von Band \\(3\\) bei jedem simulierten Rechenschritt von \\(F_4\\).<\/li>\n<li>\\(F_7\\): Kopiert vom Arbeits- und Eingabeband \\(2\\) am Ende alle Einsen auf Band \\(0\\) und erzeugt uns so auf dem gew\u00fcnschten Band \\(0\\) eine Ausgabe.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Wir transformieren die Eingabecodierung \\(EC(1^{n_1},1^3,1^9 )\\) und setzen jeden der drei Parameter als ein Eingabewort aus Einsen auf ein eigenes Band. Was jedoch mit \\(1^{n_1}\\) gemacht wird, ist etwas spannender: Aus \\(1^{n_1}\\) wird \\(\\nu_P(n_1)\\), unser Bandprogramm aus \\(BP\\) (zur Auffrischung: siehe Lernziel 1), welches nun auf Band \\(1\\) unserer Maschine steht.<\/p>\n<p style=\"padding-left: 30px;\">Auf Band \\(2\\) (Eingabeband) steht die Eingabe \\(1^{3}\\) (\\(n=3\\)). Auf diesem Band werden die einzelnen Berechnungsschritte von Band \\(1\\) (dem Programmband) simuliert. Band \\(3\\) (Schrittzahlband) ist der Schrittz\u00e4hler mit \\(1^9\\), wo bei jedem Schritt von \\(\\nu_P(n_1)\\) eine \\(1\\) gel\u00f6scht wird. Auf Band \\(4\\) (Markenband) wird die aktuelle Marke gespeichert. Unsere B\u00e4nder sehen nun so aus:<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/utm2.png\"><img loading=\"lazy\" decoding=\"async\" title=\"utm\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/utm2-1024x115.png\" alt=\"\" width=\"475\" height=\"64\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Das hat unser Teil-Flussdiagramm \\(F_1\\) gemacht. Nun kommt \\(F_2\\) und kopiert die Anfangsmarke nach Band 4:<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/utmband4.png\"><img loading=\"lazy\" decoding=\"async\" style=\"margin-left: 00px; margin-right: 300px;\" title=\"utmband4\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/utmband4.png\" alt=\"\" width=\"180\" height=\"36\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Nun sucht Teil-Flussdiagramm \\(F_3\\) auf Band \\(1\\), wo unser Programm gespeichert ist das erste Teilwort, wo die gespeicherte Marke von Band \\(4\\) vorkommt. Wenn es einen passenden Befehl findet, f\u00fchrt Teil-Flussdiagramm \\(F_4\\) den Befehl auf Band \\(2\\) aus. Wenn nicht, so ist es eine Endmarke (wir erinnern uns an den ersten Abschnitt: wenn im Programm auf eine Marke referenziert wird, es jedoch keine Beschreibung f\u00fcr diese gibt, so ist es eine \\(HALT\\)-Marke).<\/p>\n<p style=\"padding-left: 30px;\">Da die Marke \\(1^2\\) von \\(F_3\\) gefunden wird, wird der Befehl auf Band \\(2\\) von Teil-Flussdiagramm \\(F_4\\) ausgef\u00fchrt. Wenn er die Form \\((1^k:\\beta,1^n)\\) hat, wird die Bandoperation \\(\\beta\\) auf Band \\(2\\) ausgef\u00fchrt und die gespeicherte Marke auf Band \\(4\\) mit der Folgemarke \\(1^n\\) ersetzt. Hat der Befehl die Form\u00a0\\((1^k:\\beta,1^j,1^m)\\), so testet \\(F_4\\) ob unter dem Kopf \\(\\beta\\) steht und ersetzt die Marke auf Band \\(4\\) entsprechend dem Ergebnis durch \\(1^j\\) (nein, \\(\\beta\\) steht nicht unter dem Lesekopf) oder \\(1^m\\) (ja, \\(\\beta\\) steht unter dem Lesekopf). Das Teil-Flussdiagramm \\(F_5\\) pr\u00fcft ob auf dem Z\u00e4hlerband \\(3\\) noch Einsen stehen, d.h. ob weitergerechnet werden kann.<\/p>\n<p style=\"padding-left: 30px;\">In unserem Fall sehen unsere B\u00e4nder anschlie\u00dfend so aus, da der Befehl \\((1^2:1,,1)\\) auf Band \\(1\\) gefunden und ausgef\u00fchrt wurde. Auch ist eine \\(1\\) auf Band \\(2\\) unter dem Lesekopf, so dass wir nicht in die Marke \\(1\\), sondern in die &#8222;leere&#8220; Folgemarke springen werden und diese Folgemarke auf unser Folgemarkenband \\(3\\) schreiben. Auch haben wir eine \\(1\\) von unserem Z\u00e4hlerband, Band \\(4\\) mit dem Teil-Flussdiagramm \\(F_6\\) gel\u00f6scht.<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/utm_2.png\"><img loading=\"lazy\" decoding=\"async\" title=\"utm_2\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/utm_2-1024x117.png\" alt=\"\" width=\"475\" height=\"64\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Da noch Einsen auf dem Z\u00e4hlerband stehen (\\(F_5\\) hat das gepr\u00fcft), d\u00fcrfen wir weiterrechnen. Nun wird nach der &#8222;leeren&#8220; Marke auf Band \\(1\\) gesucht, diese auf Band \\(2\\) durch \\(F_4\\) ausgef\u00fchrt, wieder eine \\(1\\) vom Z\u00e4hlerband \\(3\\) durch \\(F_6\\) gel\u00f6scht, die Folgemarke auf Band \\(4\\) durch \\(F_4\\) geschrieben, diese wieder auf Band \\(1\\) durch \\(F_3\\) gesucht, usw.<\/p>\n<p style=\"padding-left: 30px;\">Wir wiederholen den Spa\u00df nun die ganze Zeit bis die Maschine letztendlich alle ihre Befehle abgearbeitet (es in einem befehl auf eine Marke referenziert, diese auf das Folgemarkenband geschrieben und gesucht. Sie steht aber nicht auf Band \\(1\\) &#8211; es ist also eine Endmarke) hat. Dann geht es von \\(F_3\\) zu \\(F_7\\), welches die Ausgabe von Band \\(2\\) auf Band \\(0\\) kopiert. W\u00e4re es keine Endmarke, w\u00fcrde von \\(F_5\\) noch einmal gepr\u00fcft werden ob noch Einsen auf dem Z\u00e4hlerband stehen. Wenn das nicht der Fall w\u00e4re, so w\u00fcrde die Maschine halten. In unserem Fall sind noch Einsen auf Z\u00e4hlerband, eine Endmarke ist aber erreicht worden, alles ist gut.<\/p>\n<p style=\"padding-left: 30px;\">Um noch wie gew\u00fcnscht die \\(1\\) zur Ausgabe \\(1^{\\varphi_{n_1}(1^3)}\\) zu addieren und den Lesekopf rechts von der Ausgabe zu positionieren werden am Ende noch die Befehle \\(0:1\\) und \\(0:R\\) ausgef\u00fchrt. \u00a0Am Ende sehen unsere B\u00e4nder wie folgt aus:<\/p>\n<p style=\"padding-left: 30px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/utmende.png\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-2246 alignnone\" style=\"margin-left: 0px; margin-right: 10px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/utmende.png\" alt=\"utmende\" width=\"450\" height=\"61\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/utmende.png 1420w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/utmende-300x40.png 300w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/11\/utmende-1024x139.png 1024w\" sizes=\"auto, (max-width: 450px) 100vw, 450px\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Die gesuchte Ausgabe steht auf dem Ausgabeband \\(0\\).<\/p>\n<p style=\"padding-left: 30px;\">Damit haben wir die Berechenbarkeit der Funktion \\(h\\) bewiesen. Und damit wir die ganze Arbeit nicht umsonst gemacht haben, nutzen wir \\(h\\) gleich f\u00fcr das smn- un das utm-Theorem.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Um die charakteristische Funktion \\(g_\\Phi\\) f\u00fcr das \\(\\Phi\\)-Theorem zu berechnen, ist es notwendig die Maschine mit der Nummer \\(i\\) auf einer (sog. universellen) Turingmaschine zu simulieren.<\/p>\n<p>Dazu wird das zu simulierende Bandprogramm \\(\\nu_P(i)\\), die Eingabe \\(x\\), die maximale Anzahl der Schritte \\(t\\) auf jeweils ein Band der neuen Maschine geschrieben und die einzelnen Befehle des Bandprogramms\u00a0\\(\\nu_P(i)\\) auf dem Eingabeband, wo \\(x\\) steht simuliert. Bei jedem Berechnungsschritt wird \\(t\\) auf dem Schrittzahlband um Eins dekrementiert, w\u00e4hrend auf dem Markenband sich die Marke des aktuell zu simulierenden Befehls befindet damit die simulierende Maschine immer wei\u00df, wo sie gerade ist.<\/p>\n<p>Endet die Berechnung noch bevor \\(t\\) auf dem Schrittzahlband zu \\(0\\) geworden ist, war die Berechnung erfolgreich und es ist \\(h\\neq 0\\). Ist auf dem Schrittzahlband jedoch bereits \\(t=0\\), so wird die Berechnung abgebrochen und es gilt \\(h=0\\). Damit braucht die Maschine \\(i\\) bei der Eingabe von \\(x\\) mehr Berechnungsschritte als \\(t\\) um zur Endmarke \\(HALT\\) zu gelangen.<\/p>\n<p>Diese Funktion ist nicht nur f\u00fcr das \\(\\Phi\\)-Theorem wichtig, sondern bildet auch die Basis einer <strong>universellen Turingmaschine<\/strong>.<\/p>\n<p>Weil der Beitrag zu den letzten drei Lernzielen so lang geworden ist, geht der Rest im <a title=\"TI: utm-, smn- und Phi-Theorem (Lernziele KE5, 2\/2)\" href=\"https:\/\/fernuni.digreb.net\/?p=1047\">n\u00e4chsten Beitrag<\/a> weiter.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: Tippfehler, Danke Marcel. Update: Ungenauigkeit beseitigt. Danke Steve. Update: Fehler beseitigt. Danke Max. Update: Pfui, da sind mir doch tats\u00e4chlich ein paar Funktionen abhanden gekommen. Sind alle wieder im Text. Auch habe ich einen weiteren Betrag verfasst um den Zusammenhang zwischen einer Programmiersprache und sowie dem utm- und smn-Theorem noch etwas zu verdeutlichen. Update: &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=991\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: Standardnummerierung und -Komplexit\u00e4t Phi und das Phi-Theorem (Lernziele KE5, 1\/3, Update 7)\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-991","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\/991","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=991"}],"version-history":[{"count":61,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/991\/revisions"}],"predecessor-version":[{"id":3511,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/991\/revisions\/3511"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=991"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=991"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=991"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}