{"id":2280,"date":"2012-12-03T13:25:52","date_gmt":"2012-12-03T11:25:52","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=2280"},"modified":"2025-11-25T22:43:20","modified_gmt":"2025-11-25T21:43:20","slug":"tia-utm-theorem-lernziele-ke5-23","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=2280","title":{"rendered":"TIA: utm-Theorem (Lernziele KE5 2\/3, Update 2)"},"content":{"rendered":"<p><strong>Update 2<\/strong>: Fehler korrigiert. Danke Max.<\/p>\n<p><strong>Update 2<\/strong>: Merksatz zum Lernziel hinzugef\u00fcgt.<\/p>\n<p><strong>Update<\/strong>: aus zwei Beitr\u00e4gen habe ich mittlerweile drei gemacht. Die Ladezeiten vom smn-Theorem waren ja nicht zu ertragen.<\/p>\n<p>Nun Teil 2 der Kurseinheit 5. Nachdem wir in <a title=\"TI: Standardnummerierung und -Komplexit\u00e4t Phi (KE5)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">Teil 1<\/a> die Standardnummerierung \\(\\varphi\\) und die Standardkomplexit\u00e4t \\(\\Phi\\) und das \\(\\Phi\\)-Theorem\u00a0behandelt haben, folgen in diesem und dem n\u00e4chsten Teil die zwei weiteren Theoreme. <del>Der letzte Beitrag war mit acht Seiten schon relativ lang, hoffentlich wird dieser was k\u00fcrzer.<\/del><\/p>\n<p>Zu fr\u00fch gefreut, das Beispiel im <a href=\"https:\/\/fernuni.digreb.net\/?p=1047\">n\u00e4chsten Beitrag<\/a> zum smn-Theorem hat mich ebenfalls 8 Seiten gekostet, daher die Beitragstrennung und der letzte Beitrag der Serie zu KE5 von TIA ist:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=1047\">TIA: smn-Theorem (Lernziele KE5, 3\/3)<\/a><\/li>\n<\/ul>\n<p>Starten wir zun\u00e4chst mit einigen Anforderungen an vern\u00fcnftige Programmiersprachen:<\/p>\n<p>Es gibt zwei Anforderungen an vern\u00fcnftige Programmiersprachen, die im Skript zu Anfang behandelt wurden. Das sind<\/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>Auch wenn die Programmiersprache RPG wahrscheinlich beide Voraussetzungen erf\u00fcllt, vern\u00fcnftig wird sie dadurch trotzdem nicht. Aber bevor IBM-Fans mir die Fensterscheiben einwerfen machen wir lieber weiter im Text \ud83d\ude09<\/p>\n<h2>Lernziel 4<\/h2>\n<p style=\"padding-left: 30px;\"><em>Anwendung und Erl\u00e4uterung des <strong>utm-Theorems<\/strong><\/em><\/p>\n<p><span style=\"font-size: 13px;\">F\u00fcr die Formalisierung des utm-Theorems brauchen wir zun\u00e4chst eine hilfreiche Funktion, die wir im <\/span><a style=\"font-size: 13px;\" title=\"TIA: Standardnummerierung und -Komplexit\u00e4t Phi (Lernziele KE5, 1\/2)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">letzten Beitrag<\/a><span style=\"font-size: 13px;\"> bereits definiert und als berechenbar bewiesen hatten:<\/span><\/p>\n<p style=\"padding-left: 30px;\">\\(h:\\mathbb{N}^3 \\rightarrow \\mathbb{N}\\) \u00a0mit<\/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>Ich werde das jetzt nicht gro\u00df ausf\u00fchren, steht ja alles im ersten Teil der Lernziele zu KE5, sondern sage euch nur schnell noch einmal, was sie macht:\u00a0Wir bekommen eine \\(1+\\) das Ergebnis der Maschine mit der Nummer \\(i\\) bei der Eingabe von \\(n\\) wenn die <a title=\"TI: Standardnummerierung und -Komplexit\u00e4t Phi (KE5)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">Standardkomplexit\u00e4t<\/a> \\(\\Phi_i\\) existiert und kleiner\/gleich \\(t\\) ist (die Berechnung von \\(i\\) bei der Eingabe von \\(x\\) ist noch vor \\(t\\) Schritten abgeschlossen). Ansonsten gibt es nur eine Null zur\u00fcck. Fair.<\/p>\n<p>Wie hilft diese Funktion uns nun beim\u00a0<strong>utm-Theorem<\/strong>?<\/p>\n<p>Das <strong>utm-Theorem<\/strong> ist definiert als<\/p>\n<blockquote><p>\\(u_\\varphi :\\subseteq \\mathbb{N}^2 \\rightarrow \\mathbb{N}\\) mit<\/p>\n<p>\\(u_\\varphi(i,x) := \\varphi_i(x)\\) f\u00fcr alle \\(i,x \\in \\mathbb{N}\\).<\/p>\n<p>\\(u_\\varphi\\) ist dann berechenbar und wird <em>die universelle Funktion von<\/em> \\(\\varphi\\) genannt<\/p><\/blockquote>\n<p>Aber wahrscheinlich f\u00fcgen sich bei euch noch nicht alle Puzzle-Teile zu einem Bild zusammen. Vielleicht holen wir daher zun\u00e4chst etwas weiter aus: eine universelle Turing-Maschine ist eine Maschine, die beliebige andere Maschinen simulieren kann.<\/p>\n<p>Wie wir im vorherigen Beispiel gesehen haben, k\u00f6nnen wir einer Turing-Maschine eine andere Maschine und das Eingabewort als Parameter mitgeben und so diese Maschine simulieren. Am Ende kopiert unsere universelle Maschine die Ausgabe auf Band \\(0\\) und wir sind fertig (nur, dass wir im <a title=\"TIA: Standardnummerierung und -Komplexit\u00e4t Phi (Lernziele KE5, 1\/2)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">vorherigen Beitrag<\/a> noch eine \\(1\\) zum Ergebnis addiert haben). Die Maschine agiert also als eine Art Interpreter und ist nicht auf die Berechnung einer einzigen Funktion beschr\u00e4nkt.<\/p>\n<p>Was haben wir dazu nun gemacht? Die Turing-Maschinen sprechen nur un\u00e4r, d.h. Zeichen aus unserem Bandprogramm \\(\\omega\\in BP\\) mit \\(\\omega=(1^2:1,,1)\\), mit unseren Klammern, Kommas und Doppelpunkten k\u00f6nnen wir eigentlich gar nicht interpretieren.<\/p>\n<p>Doch, das k\u00f6nnen wir! Und zwar mittels der Nummerierung \\(\\varphi\\). Im obigen Beispiel stehen diese zwar im Klartext auf dem Band, aber nur der \u00dcbersichtlichkeit halber. Wenn Ihr euch statt einer \u00f6ffnenden Klammer \\((\\) nun ihren Nummerierungswert der Ordnungsfunktion \\(a\\rightarrow\\nu_\\Omega\\) (\\(a(&#8222;(&#8222;)=3\\))auf dem Band denkt, dann ist das Jacke wie Hose. Im <a title=\"TI: Standardnummerierung und -Komplexit\u00e4t Phi (KE5)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">ersten Teil<\/a> haben wir gezeigt, dass das durch die Ordnungsfunktion wunderbar funktioniert.<\/p>\n<p>Nachdem wir nun diese Maschine in Zahlen \u00fcberf\u00fchrt haben, haben wir eine sog.\u00a0<em>G\u00f6delisierung<\/em> durchgef\u00fchrt. Die Codierung, die am Ende f\u00fcr die Maschine herauskommt ist die sogenannte\u00a0<em>G\u00f6delnummer<\/em>.\u00a0Das formale utm-Theorem ist die formale und etwas abstrakte Version dieser universellen Turing Maschine, denn sie erf\u00fcllt die am Anfang gestellte Forderung \\((U)\\) (siehe oben).<\/p>\n<p>Wir k\u00f6nnen n\u00e4mlich mit diesem Computer \\(U\\) (unsere universelle Turing-Maschine) zu jedem Programm \\(P\\) (welches wir vorher entsprechend codiert haben), das mit einem Eingabewert \\(x\\) gef\u00fcttert werden w\u00fcrde, durch die Simulation\/Interpretation von ihm, sein Ergebnis berechnen, also genau unser gesuchtes \\(\\sigma(P)(x)\\).<\/p>\n<p>Das utm-Theorem bedeutet also nichts anderes, als dass eine Funktion \\(u_\\varphi(i,x)\\) (sie nimmt also die Nr. der zu simulierenden Maschine und die Eingabe f\u00fcr sie als Parameter auf) berechenbar ist wenn sie als Ausgabe \\(\\varphi_i(x)\\) (also genau das Ergebnis der simulierten Maschine \\(i\\)) hat. Genau das bedeutet die obige formale Definition des utm-Theorems.<\/p>\n<blockquote><p>\\(u_\\varphi(i,x) := \\varphi_i(x)\\) f\u00fcr alle \\(i,x \\in \\mathbb{N}\\).<\/p><\/blockquote>\n<p>Jetzt m\u00fcssen wir also nur noch eine Maschine angeben, die \\(u_\\varphi\\) berechnet. Unsere Funktion \\(h\\) von oben leistet uns hier gro\u00dfe Dienste: w\u00e4hrend wir bei \\(h(i,n,t)\\) im Parameter \\(t\\) genau angeben mussten, wie lange die simulierende Maschine rechnen darf, wollen wir bei \\(u_\\varphi\\) eig. nur das Ergebnis haben und nicht angeben, wie lange unsere Maschine zu rechnen hat. Das \\(t\\) ist uns also egal. Und das geht ganz einfach.<\/p>\n<p><strong>Beispiel<\/strong>:\u00a0wir simulieren das Programm \\(h\\), welches unser Programm\u00a0\\((1^2:1,,1)(:1,1,1^2)(:B,,)\\) mit der G\u00f6delnummer \\(n_1\\) simuliert, in einer Schleife und z\u00e4hlen unser \\(t\\) ab \\(1\\) einfach hoch. Eingabe bleibt \\(n = 3\\).<\/p>\n<ol style=\"padding-left: 30px;\">\n<li>F\u00fchre \\(h(n_1,3,1)\\) aus und speichere es in \\(R_0\\)<\/li>\n<li>Wenn \\(R_0 = 0\\) (wir haben die \\(HALT\\)-Marke im Programm mit unserem \\(t=1\\)\u00a0noch nicht erreicht und bekommen daher eine \\(0\\) als Ausgabe), erh\u00f6he \\(t\\) um eins und f\u00fchre dann \\(h(2,3,2)\\)\u00a0aus, usw.<\/li>\n<li>Wenn \\(R_0\\) eine Ausgabe ungleich \\(0\\) hat, dann subtrahiere eine \\(1\\) vom Ergebnis (in \\(h\\) haben wir es ja immer um Eins erh\u00f6ht) und beende dich.<\/li>\n<\/ol>\n<p>Dam Ende steht in \\(R_0\\) das Ergebnis (\\(3\\)) und wir haben unser kleinstes \\(t = 8\\) auch. Es wird im Skript im Register \\(R_3\\) zwischengespeichert. Damit ist auch \\(u_\\varphi\\) berechenbar.<\/p>\n<p>Im Skript wird eine weitere universelle Funktion f\u00fcr die <a title=\"TI: Standardnummerierung und -Komplexit\u00e4t Phi (KE5)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">Standardkomplexit\u00e4t<\/a>, n\u00e4mlich \\(u_\\Phi\\) definiert:<\/p>\n<blockquote><p>\\(u_\\Phi :\\subseteq \\mathbb{N}^2 \\rightarrow \\mathbb{N}\\) mit<\/p>\n<p>\\(u_\\Phi(i,x) := \\Phi_i(x)\\) f\u00fcr alle \\(i,x \\in \\mathbb{N}\\).<\/p><\/blockquote>\n<p>Sie macht nicht viel anders als \\(u_\\varphi\\). Wir bekommen hier jedoch nicht das Ergebnis\u00a0\\(\\varphi_i(x)\\)\u00a0als Ausgabe, sondern\u00a0das kleinste \\(t\\) (die Anzahl der Rechenschritte, Schrittzahlfunktion, wir erinnern uns?) bei der Eingabe von \\(x\\), also genau \\(\\Phi_i(x)\\). Das Ergebnis schreiben wir ins \\(R_0\\), dem Ergebnisregister der berechnenden Maschine und sind fertig.<\/p>\n<p><strong><span style=\"font-size: 1.17em;\">Zusammenhang zu \\(R^{(1)}\\)<\/span><\/strong><\/p>\n<p>Nachdem ich gemerkt habe, dass ich einige Details von \\(P^{(1)}\\) und\u00a0\\(R^{(1)}\\) durcheinander brachte und freundlich von Harald und Carsten aus der NG darauf hingewiesen wurde, habe ich mich entschlossen das hier auch nieder zu schreiben. Obwohl ich der Meinung bin, dass die meisten von euch die Unterschiede zwischen den beiden Mengen gut bewusst sind und sie keine Auffrischung brauchen, bin ich mir sicher, dass ich das in sp\u00e4testens einigen Monaten vor der Pr\u00fcfungsvorbereitung wieder verdr\u00e4ngt habe. Also tue ich etwas f\u00fcr mein &#8222;Zukunfts-ich&#8220; (How i met your mother l\u00e4sst gr\u00fc\u00dfen) und schreibe in aller Deutlichkeit nochmal:<\/p>\n<blockquote><p>\\(P^{(1)}\\): partielle (nicht \u00fcberall definierte), berechenbare Funktionen. Nummerierung \\(\\varphi\\) von \\(P^{(1)}\\)\u00a0erf\u00fcllt das utm-Theorem, d.h. es gibt eine universelle Turingmaschine, die die Funktion interpretiert und die entsprechende Ausgabe berechnet.<\/p>\n<p>\\(R^{(1)}\\): totale (\u00fcberall definierte), berechenbare Funktionen. <strong>Keine<\/strong> Nummerierung von \\(R^{(1)}\\)\u00a0erf\u00fcllt das utm-Theorem (es gibt also keine universelle Funktion \\(u\\) zum interpretieren des Programms).<\/p><\/blockquote>\n<p>Die letzte Feststellung ist wichtig: warum erf\u00fcllt keine Nummerierung von \\(R^{(1)}\\) das utm-Theorem? Denn es w\u00e4re doch &#8211; wie im Skript angemerkt &#8211; praktisch wenn man sich nur auf \u00fcberall definierte Funktionen beschr\u00e4nken k\u00f6nnte. Was n\u00fctzt einem ein Programm, dass bei einer Eingabe ggf. nicht h\u00e4lt? Leider geht das nicht. Die Beweisidee ist wie folgt:<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"line-height: 13px;\">Zun\u00e4chst: was ist eine Nummerierung? Einfach nur die Nummer einer Funktion. W\u00e4hrend wir also \\(P^{(1)}\\), die einstelligen, berechenbaren, ggf. partiellen Funktionen mit \\(\\varphi\\) nummeriert haben und diese Funktion (bzw. die Maschinen, die die Funktionen berechnen) durch eine universelle Turingmaschine mit \\(u_\\varphi(i,x)=\\varphi_i(x)\\) simulieren, k\u00f6nnen, bekommen wir bei \\(R^{(1)}\\) ein Problem.<\/span><\/p>\n<p>Warum? W\u00e4hrend \\(\\varphi_i(x)\\) nicht f\u00fcr jedex \\(x\\) definiert sein muss, d.h. es auch eine Ausgabe \\(\\varphi_i(x)=div\\) geben kann, haben wir bei dem gleichen Spiel mit \\(\\psi\\), der Nummerierung von\u00a0\\(R^{(1)}\\) immer eine Ausgabe. Ist ja auch klar, die Funktionen aus \\(R^{(1)}\\)\u00a0sind total und damit eben f\u00fcr jedes \\(x\\) definiert.<\/p>\n<p>In was f\u00fcr ein Problem laufen wir hier?<\/p>\n<p style=\"padding-left: 30px;\">Wir nehmen eine Nummerierung \\(\\psi\\) von \u00a0\\(R^{(1)}\\). Lt. utm-Theorem gibt es dazu eine universelle Funktion\u00a0\\(u_\\psi(i,x)=\\psi_i(x)\\), d.h. eine universelle Turing-Maschine, welche als Eingabe die G\u00f6delnummer\/den Index der Maschine und ein \\(x\\) bekommt und diese so simuliert (siehe das 2. Beispiel f\u00fcr \\(h\\) von oben), dass auf Band \\(0\\) anschlie\u00dfend die Ausgabe \\(\\psi_i(x)\\)\u00a0steht.<\/p>\n<p style=\"padding-left: 30px;\">Nun basteln wir uns eine Funktion \\(h(i)=u_\\psi(i,i)+1\\). Diese ist auch total und berechenbar, da \\(\\psi(i,i)\\) ja selbst total und berechenbar war. D.h. die universelle Funktion \\(u\\) simuliert uns die Maschine \\(i\\) mit der Eingabe \\(i\\) und addiert eine \\(1\\) dazu. Sie ist damit definitiv von\u00a0\\(\\psi(i,i)\\) verschieden und somit eine neue Maschine.<\/p>\n<p style=\"padding-left: 30px;\">Da es eine komplett neue Maschine ist, hat sie nat\u00fcrlich auch eine neue G\u00f6delnummer\/einen neuen Index \\(k\\). Da wir aber alle totalen Funktionen bereits durchnummeriert haben, ist \\(h(k) = \\psi_k(k) = \\psi_k(k)+1\\), was aber nicht funktioniert. Denn \\(\\psi_k(k)\\) existiert ja bereits in unserer Auflistung und kann ja gar nicht eine neue Maschine sein.<\/p>\n<p style=\"padding-left: 30px;\">Das ist wieder ein Beweis durch Diagonalisierung: wir sind von der Vollst\u00e4ndigkeit unserer Auflistung ausgegangen und haben offensichtlich trotzdem noch eine neue Maschine erstellen k\u00f6nnen, was uns zu einem Widerspruch f\u00fchrt. Damit erf\u00fcllt keine Nummerierung nur der totalen, berechenbaren Funktionen \\(R^{(1)}\\) das utm-Theorem.<\/p>\n<p>Und was ist mit \\(P^{(1)}\\)? Damit klappt es:<\/p>\n<p style=\"padding-left: 30px;\">Wir gehen zun\u00e4chst genauso vor, wie bei\u00a0\\(R^{(1)}\\): holen uns eine Nummerierung mit \\(\\varphi\\) und eine\u00a0universelle Funktion\u00a0\\(u_\\varphi(i,x)=\\varphi_i(x)\\).<\/p>\n<p style=\"padding-left: 30px;\">Nun erstellen wir die neue Funktion:\u00a0\\(h(i)=u_\\varphi(i,i)+1\\). Da \\(\\varphi(i,i)\\) nicht total sein muss (f\u00fcr ein \\(x\\) kann \\(\\varphi(i,x)=div\\) sein), k\u00f6nnte\u00a0\\(h(i)=u_\\varphi(i,i)+1\\) ebenfalls nicht total sein und die Aussage\u00a0\\(h(k)=\\varphi_k(k)=\\varphi_k(k)+1\\) h\u00e4tte durchaus Bestand:\u00a0\\(h(k)=\\varphi_k(k)=div=\\varphi_k(k)+1=div+1=div\\).<\/p>\n<p>Ist tats\u00e4chlich etwas abstrakt, aber hoffentlich trotzdem nachvollziehbar.<\/p>\n<p>(Hier geht ein gro\u00dfer Dank an Barbara, Harald, Oliver und Herbert aus der NG f\u00fcr ein paar &#8211; wenn auch hinkende &#8211; Vergleiche \ud83d\ude09 Wenn jemand in &#8222;einfacheren Worten&#8220; eine Erkl\u00e4rung hat, warum eine Nummerierung f\u00fcr \\(P^{(1)}\\) das utm- Theorem erf\u00fcllen kann, aber keine Nummerierung f\u00fcr \\(R^{(1)}\\) das zu leisten vermag, der m\u00f6ge mir bitte eine Nachricht schicken. Ich w\u00fcrde das dann gerne hier aufnehmen)<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: bei dem utm-Theorem geht es im Grunde um die Frage ob es einen Computer gibt, der jeden anderen Computer simulieren kann.\u00a0In der theoretischen Informatik w\u00e4re es zwar unproblematisch f\u00fcr jede Aufgabe eine eigene Maschine anzugeben, ist aus praktischer sicherlich kein gangbarer Weg.<\/p>\n<p>Diese Fragestellung hat gro\u00dfe Bedeutung bei den Programmiersprachen, denn nur durch die Bejahung dieser Frage k\u00f6nnen Programmiersprachen durch Computer interpretiert und so Anwendungen auf ihnen ausgef\u00fchrt werden.<\/p>\n<p>Daher betrachten wir den Computer als universelles Ger\u00e4t, dass Programme (andere Computer sozusagen, die nur eine Funktion berechnen) und Daten entgegen nimmt und die Funktion des Programms auf den entgegen genommenen Daten simuliert.<\/p>\n<p>Frage ist hierbei: gibt es denn so eine Funktion, die auf einer Turingmaschine ausgef\u00fchrt, eine andere Funktion simulieren kann? Und genau diese Funktion wird universelle Funktion \\(u\\) genannt, die als Eingabe eine G\u00f6delnummer \\(i\\) des zu simulierenden Programms \\(\\omega\\) und die Eingabedaten \\(x\\) entgegen nimmt und auf diesen die Befehle des Programms Schritt f\u00fcr Schritt durchf\u00fchrt um am Ende die gleiche Ausgabe zu haben wie das Programm selbst: \\(u_\\varphi(i,x)=\\varphi_i(x)\\).<\/p>\n<p>In unserem Beweis im <a title=\"TIA: Standardnummerierung und -Komplexit\u00e4t Phi und das Phi-Theorem (Lernziele KE5, 1\/2)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">letzten Betrag<\/a> hat es unsere Funktion \\(h\\) f\u00fcr uns erledigt (wobei sie noch die maximale Anzahl der zu rechnenden Schritte verwendet hatte).<\/p>\n<p><strong>Merksatz<\/strong>:<\/p>\n<blockquote><p>Das formale utm-Theorem ist die formale und etwas abstrakte Version dieser universellen Turing Maschine. Es besagt, dass eine universelle Funktion existiert, die jede andere berechenbare Funktion berechnen kann.<\/p><\/blockquote>\n<p>Im n\u00e4chsten Beitrag geht es dann um das <a href=\"https:\/\/fernuni.digreb.net\/?p=1047\">smn-Theorem<\/a>\u00a0und Rekursionss\u00e4tze.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update 2: Fehler korrigiert. Danke Max. Update 2: Merksatz zum Lernziel hinzugef\u00fcgt. Update: aus zwei Beitr\u00e4gen habe ich mittlerweile drei gemacht. Die Ladezeiten vom smn-Theorem waren ja nicht zu ertragen. Nun Teil 2 der Kurseinheit 5. Nachdem wir in Teil 1 die Standardnummerierung und die Standardkomplexit\u00e4t und das -Theorem\u00a0behandelt haben, folgen in diesem und dem &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=2280\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: utm-Theorem (Lernziele KE5 2\/3, Update 2)\u201c <\/span>weiterlesen<\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-2280","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\/2280","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=2280"}],"version-history":[{"count":10,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2280\/revisions"}],"predecessor-version":[{"id":3512,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2280\/revisions\/3512"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2280"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2280"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2280"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}