{"id":2093,"date":"2013-06-17T15:30:55","date_gmt":"2013-06-17T13:30:55","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=2093"},"modified":"2025-11-24T22:04:45","modified_gmt":"2025-11-24T21:04:45","slug":"tia-flussdiagramma-maschinen-und-berechenbare-zahlenfunktionen-lernziele-ke1","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=2093","title":{"rendered":"TIA: Flussdiagramme, Maschinen und berechenbare Zahlenfunktionen (Lernziele KE1, Update 2)"},"content":{"rendered":"\n<p><strong>Update<\/strong>: Einwand von Felix aufgenommen.<\/p>\n\n\n\n<p><strong>Update<\/strong>:&nbsp;Marion hat einen Fehler bei der Berechnung der \\(ES\\) gefunden. Danke!<\/p>\n\n\n\n<p><strong>Update<\/strong>: Eine Registermaschine kann nicht die Subtraktion, sondern nur die arithmetische Differenz.<\/p>\n\n\n\n<p><strong>Update<\/strong>: Hinweis darauf, dass das erste Register bei der Eingabecodierung \\(EC\\) f\u00fcr eine Maschine belegt werden kann (wir haben keine Einschr\u00e4nkungen), aber nicht durch die Eingabecodierung f\u00fcr eine Registermaschine! <\/p>\n\n\n\n<p>Als ich die ersten Beitr\u00e4ge zur Kurseinheit 1 von Teil A der theoretischen Informatik geschrieben habe, orientierte ich mich an den Themen. Entstanden sind damit die Unterbeitr\u00e4ge:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=468\">Normale und allgemeine Registermaschinen<\/a><\/li>\n\n\n\n<li><a title=\"TI: Einzelschritt- und Schrittzahlfunktion sowie \u00dcbergangsrelationen (Update)\" href=\"https:\/\/fernuni.digreb.net\/?p=512\">Einzelschritt- und Schrittzahlfunktion sowie \u00dcbergangsrelationen (Update)<\/a><\/li>\n\n\n\n<li><a title=\"TI: Beweis der Addition zweier Register mit einer Registermaschine\" href=\"https:\/\/fernuni.digreb.net\/?p=515\">Beweis der Addition zweier Register mit einer Registermaschine<\/a><\/li>\n<\/ul>\n\n\n\n<p>Irgendwann, gegen Ende der Kurseinheit 5 habe ich gemerkt, dass es vielleicht sinniger ist anhand der Lernziele zu gehen. Das bringt etwas mehr Struktur in die Beitr\u00e4ge und wirft einen roten Faden durch das Skript.<\/p>\n\n\n\n<p>Als ich dann bei Kurseinheit 7 von Teil B angelangt war, hat sich mein Entschluss gefestigt die alten Beitr\u00e4ge ebenfalls zu \u00fcberarbeiten. Was ich hiermit also tun m\u00f6chte.&nbsp;<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 1<\/h2>\n\n\n\n<p><em>Angabe und Erl\u00e4uterung der Definition des Flussdiagramms<\/em><\/p>\n\n\n\n<p>Ich w\u00fcrde vorschlagen, wir definieren wieder und erkl\u00e4ren die Definition Zeile f\u00fcr Zeile: das Flussdiagramm ist ein 4-Tupel \\(F=(Q,D,\\sigma,q_o)\\)<\/p>\n\n\n\n<p>\\(Q\\) als Markenmenge<br>\\(D\\) als Datenmenge<br>\\(q_0\\) als Startmarke<br>\\(\\sigma\\)<\/p>\n\n\n\n<p>zu jeder Marke geh\u00f6rt entweder eine Zuweisung<\/p>\n\n\n\n\\((f,p)\\)\n\n\n\n<p>oder eine Verzweigung\/Test<\/p>\n\n\n\n\\((S,p,p^{&#8218;})\\)\n\n\n\n<p>Beispiel gef\u00e4llig?<\/p>\n\n\n\n<p><strong>Beispiel<\/strong>: \\(F_1=(Q,D,\\sigma,q_0)\\) mit<\/p>\n\n\n\n<p>\\(Q=\\{1,2,3,4\\}\\): wir haben nur vier Marken im Flussdiagramm<\/p>\n\n\n\n<p>\\(D=\\mathbb{N}^2\\): wir operieren auf max. zweistelligen, nat\u00fcrlichen Zahlen<\/p>\n\n\n\n<p>\\(q_0=1\\): die Anfangsmarke ist \\(1\\)<\/p>\n\n\n\n<p>Und nun kommt unsere Funktion, die jeder Marke eine Operation zuweist. Das macht das Flussdiagramm n\u00e4mlich erst aus.<\/p>\n\n\n\n<p>\\(\\sigma(1)=(y=1,2)\\) (Zuweisung)<\/p>\n\n\n\n<p>\\(\\sigma(2)=(y&gt;x,4,3)\\) (Verzweigung\/Test)<\/p>\n\n\n\n<p>\\(\\sigma(3)=(y=y+1,2)\\) (Zuweisung)<\/p>\n\n\n\n<p>\\(\\sigma(4)=HALT\\) (Haltemarke)<\/p>\n\n\n\n<p>Und wenn wir \\(F_1\\) auf Papier bringen:<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/flussdiagramm_KE1.png\"><img loading=\"lazy\" decoding=\"async\" width=\"586\" height=\"258\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/flussdiagramm_KE1.png\" alt=\"flussdiagramm_KE1\" class=\"wp-image-2098\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/flussdiagramm_KE1.png 586w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/flussdiagramm_KE1-300x132.png 300w\" sizes=\"auto, (max-width: 586px) 100vw, 586px\" \/><\/a><\/figure>\n<\/div>\n\n\n<p class=\"has-text-align-center\"><\/p>\n\n\n\n<p>Nicht so schwer, oder? Was tut das Flussdiagramm \\(F_1\\)? Nichts besonderes: es z\u00e4hlt nur \\(y\\) hoch bis es gr\u00f6\u00dfer ist als \\(x\\). Nicht besonders sinnvoll, aber kurz (ich bin faul, sorry) und anschaulich.<\/p>\n\n\n\n<p><strong>Antwort zum Lernziel:<\/strong>&nbsp;Ein Flussdiagramm besteht aus einer Marken- und Datenmenge, einer Startmarke und einer Funktion, die jeder Marke aus der Markenmenge eine Zuweisung oder eine Verzweigung zuordnet.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 2<\/h2>\n\n\n\n<p><em>Angabe und Erl\u00e4uterung der Semantik des Flussdiagramms<\/em><\/p>\n\n\n\n<p>Semantik? Bedeutung! Das Flussdiagramm \\(F\\) definiert n\u00e4mlich nichts anderes als eine Funktion \\(f_F\\), die aus den Parametern (oben waren es \\(x\\) und \\(y\\)) in einer Endkonfiguration (so denn es eine gibt) ein Ergebnis generiert. Die Semantik eines Flussdiagramms gliedert sich in folgende Begriffe:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Konfiguration<\/strong>: z.B. Anfangs- und Endkonfiguration sowie Zwischenkonfigurationen<\/li>\n\n\n\n<li><strong>Einzelschrittfunktion<\/strong>: \u00dcbergang in einem Berechnungsschritt von einer Konfiguration in eine andere<\/li>\n\n\n\n<li><strong>Schrittzahlfunktion<\/strong>: \\(div\\) wenn es zu einer Eingabe keine Endkonfiguration gibt oder die Anzahl der Schritte, die zu einer Eingabe bis zur Endkonfiguration gef\u00fchrt haben<\/li>\n\n\n\n<li><strong>Gesamtschrittfunktion<\/strong>: Endkonfiguration zu einer Eingabe. Wenn sie existiert. Ansonsten \\(div\\).<\/li>\n\n\n\n<li><strong>Semantik<\/strong>: Das Ergebnis<\/li>\n<\/ul>\n\n\n\n<p><strong>Beispiel<\/strong>:&nbsp;\\(F_1=(Q,D,\\sigma,q_0)\\) (von oben)<\/p>\n\n\n\n<p>Sagen wir, wir starten \\(F_1\\) mit \\(x=2\\) und \\(y=0\\).<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Anfangskonfiguration: <\/strong>\\((1,(2,0))\\) und <strong>Endkonfiguration<\/strong>:&nbsp;\\((4,(2,3))\\) (Zwischenkonfigurationen lasse ich mal weg)<\/li>\n\n\n\n<li><strong>Einzelschrittfunktion: <\/strong>z.B. \\(ES(1,(2,0)=(2,(2,1))\\). Nach einem Schritt befinden wir uns in Marke \\(2\\) und haben nur \\(y=1\\) gesetzt. W\u00fcrden wir aber z.B. \\(ES^6(1,(2,0))\\) nehmen, so m\u00fcssten wir f\u00fcnf Berechnungsschritte im Flussdiagramm ausf\u00fchren und w\u00e4ren bei<\/li>\n<\/ul>\n\n\n\n\\(\\begin{align}ES^6(1,(2,0))&amp;=ES^5(2,(2,1))\\\\&amp;=ES^4(3,(2,1))\\\\&amp;=ES^3(2,(2,2))\\\\&amp;=ES^2(3,(2,2))\\\\&amp;=ES(2,(2,3))\\\\&amp;=(4,(2,3))\\end{align}\\)\n\n\n\n<p>(<strong>Update<\/strong>:&nbsp;Nach Einwand von Felix korrigiert. Danke!)<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Schrittzahlfunktion: <\/strong>\\(SZ(1,(2,0))=7\\). Nach \\(7\\) Schritten kommen wir, ausgehend von der Anfangskonfiguration \\((1,(2,0))\\) in die Endkonfiguration \\((4,(2,3))\\).<\/li>\n\n\n\n<li><strong>Gesamtschrittfunktion<\/strong>: \\(GS(1,(2,0))=(4,(2,3))\\). Die Endkonfiguration zur Anfangskonfiguration \\((1,(2,0))\\) ist eben \\((4,(2,3))\\) und damit unsere Gesamtschrittfunktion.<\/li>\n\n\n\n<li><strong>Semantik<\/strong>: \\(f_{F_1}(2,0)=(2,3)\\). Das Ergebnis der harten Arbeit unseres Flussdiagrsmms.<\/li>\n<\/ul>\n\n\n\n<p>Auch nicht viel schwerer als Lernziel 1.<\/p>\n\n\n\n<p>In einem <a href=\"https:\/\/fernuni.digreb.net\/?p=512\">alten Beitrag<\/a> habe ich das bereits f\u00fcr Registermaschinen aufgegriffen.<\/p>\n\n\n\n<p><strong>Antwort zum Lernziel:<\/strong> das Flussdiagramm definiert eine Funktion \\(f_F\\) (die Semantik des Flussdiagramms) auf der Datenmenge des Flussdiagramms, welche von einer Anfangskonfiguration (Startmarke, Eingabe) nach endlich vielen Schritten zu einer Endkonfiguration (Endmarke, Ausgabe)&nbsp;f\u00fchrt. Oder auch nicht.<\/p>\n\n\n\n<p>Die Belegung der Variablen im Flussdiagramm ist das Ergebnis der Berechnung, es gilt dann \\(f_F(Eingabe)=Ausgabe\\).<strong>&nbsp;<\/strong>Gibt es zu der Eingabe kein Ergebnis, so ist \\(f_F(Eingabe)=div\\).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 3<\/h2>\n\n\n\n<p><em>Angabe und Erl\u00e4uterung der Definition und Semantik einer Maschine<\/em><\/p>\n\n\n\n<p>Kommen wir nun zu den Maschinen. Warum reicht uns das Flussdiagramm von oben nicht? Weil die Datenmenge \\(D\\) des Flussdiagramms meistens nicht mit der Definitions- oder Bildmenge unserer durch das Flussdiagramm darzustellenden Funktion \u00fcbereinstimmen wird. Wir brauchen hier also zus\u00e4tzlich noch ein paar andere Dinge: eine Maschine ist ein 5-Tupel mit \\(M=(F,X,Y,EC,AC)\\).<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-style-default is-layout-flow wp-block-quote-is-layout-flow\">\n<p>\\(F\\) ist ein Flussdiagramm (siehe oben)<\/p>\n\n\n\n<p>\\(X\\) ist eine Eingabe- und \\(Y\\) eine Ausgabemenge.<\/p>\n\n\n\n<p>\\(EC:X\\rightarrow D\\): Eingabecodierung. Es ist nichts weiter als eine Funktion, die aus einem Element aus \\(X\\) eine Eingabecodierung aus \\(D\\) f\u00fcr unser Flussdagramm ausgibt. Under Flussdiagramm nimmt n\u00e4mlich keine Elemente aus \\(X\\), sondern nur aus \\(D\\) entgegen.<\/p>\n\n\n\n<p>\\(AC:D\\rightarrow Y\\): Ausgabecodierung. Ebenfalls nur eine Funktion, die hier jedoch zu einem Element aus \\(D\\), der Datenmenge des Flussdiagramms ein Element aus der Ausgabemenge \\(Y\\) zuweist.<\/p>\n\n\n\n<p>Damit berechnet \\(M\\), unsere Maschine also eine Funktion \\(f_M=AC(f_F(EC))\\)<\/p>\n<\/blockquote>\n\n\n\n<p>Das letztere erschlie\u00dft sich wahrscheinlich nicht sofort. Aber wie k\u00f6nnen das an einem Beispiel etwas anschaulicher gestalten.<\/p>\n\n\n\n<p><strong>Achtung<\/strong> (Update): w\u00e4hrend wir bei der Eingabecodierung bei einer Maschine es zulassen, dass wir das erste Register belegen, tun wir das keinesfalls bei einer Registermaschine! Das ist bei der Initialbelegung durch die Funktion \\(EC\\) nicht zul\u00e4ssig, denn es fungiert als Ergebnisregister und ist initial immer mit \\(0\\) belegt!<\/p>\n\n\n\n<p><strong>Beispiel<\/strong>: Maschine \\(M\\) mit dem Flussdiagramm von oben, \\(x=2\\) und den zus\u00e4tzlichen Mengen und Funktionen<\/p>\n\n\n\n<p>\\(X,Y=\\mathbb{N}\\): die Mengen unserer Eingabe- und Ausgabecodierungen f\u00fcr unsere Maschine sind nicht mehr Tupel (\\(\\mathbb{N}^2\\)), wie sie das Flussdiagramm brauchst, sondern bestehen nur noch aus einem einzigen Element.<\/p>\n\n\n\n<p>\\(EC:X\\rightarrow D\\) mit \\(EC(x)=(x,0)\\).<\/p>\n\n\n\n<p>\\(AC:D\\rightarrow Y\\) mit \\(AC(x,y)=y\\)<\/p>\n\n\n\n<p>Wir k\u00f6nnen unsere Maschine \\(M\\) also einfach nur mit \\(x\\) f\u00fcttern und erhalten durch die Eingabefunktion \\(EC\\) auch unser \\(y\\) f\u00fcr die Eingabe in unser Flussdiagramm. \u00c4hnliches gilt f\u00fcr die Ausgabecodierung: unser Flussdiagramm gibt uns \\((x,y)\\) als Ausgabe heraus, was wir mit der Funktion \\(AC\\) in \\(y\\) umwandeln.<\/p>\n\n\n\n<p>Setzen wir also \\(x=2\\) mal ein:<\/p>\n\n\n\n<p>\\(EC(x)=(2,0)\\). Damit f\u00fcttern wir unser Flussdiagramm und bekommen als Ausgabe des Flussdiagramms \\(f_F=(2,3)\\). Das werfen wir in unsere Ausgabecodierung&nbsp;\\(AC(2,3)=3\\) und haben die Ausgabe unserer Maschine \\(f_M\\).<\/p>\n\n\n\n<p>Der letzte Punkt unserer Maschine mit ausgef\u00fclltem \\(x=2\\) bedeutet also:<\/p>\n\n\n\n\\(\\begin{align}f_M&amp;=AC(f_F(EC(2)))\\\\&amp;=AC(f_F(2,0))\\\\&amp;=AC(2,3)\\\\&amp;=3\\end{align}\\)\n\n\n\n<p>That&#8217;s it.<\/p>\n\n\n\n<p><strong>Antwort zum Lernziel:<\/strong> eine Maschine tut f\u00fcr uns also nichts anderes, als es uns zu erm\u00f6glichen nicht mehr auf der Datenmenge \\(D\\)&nbsp;des Flussdiagramms operieren zu m\u00fcssen. Durch die &#8222;Eingabecodierungs-Funktion&#8220; \\(EC\\) k\u00f6nnen wir aus einer beliebigen Eingabemenge \\(X\\) in die Datenmenge \\(D\\) des Flussdiagramms abbilden und so unser Flussdiagramm mit einer passenden Eingabe f\u00fcttern.<\/p>\n\n\n\n<p>Mittels der &#8222;Ausgabecodierungs-Funktion&#8220; \\(AC\\) gelingt uns auch der R\u00fcckweg aus der Ausgabe des Flussdiagramms (die ja ein Element aus \\(D\\) ist) in die Ausgabemenge \\(Y\\).<strong><br><\/strong><\/p>\n\n\n\n<p>Damit ist die Semantik einer Maschine die Funktion \\(f_M\\subseteq X\\rightarrow{Y}\\), die mit Hilfe von \\(EC\\) und \\(AC\\) die Mengen \\(X\\) und \\(Y\\) von, bzw. in die Datenmenge \\(D\\) f\u00fcr das Flussdiagramm \u00fcberf\u00fchrt. Es gilt somit \\(f_M=AC(f_F(EC))\\) wenn wir von einer Anfangskonfiguration zu einer Endkonfiguration kommen. Ansonsten ist \\(f_M=div\\).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 4<\/h2>\n\n\n\n<p><em>Angabe und Erl\u00e4uterung der Definition einer Registermaschine<\/em><\/p>\n\n\n\n<p>Kommen wir nun zu den Registermaschinen. Den eig. Stars dieser Kurseinheit. Ich hatte bereits in <a href=\"https:\/\/fernuni.digreb.net\/?p=468\">diesem Beitrag<\/a> etwas zum Thema geschrieben. Es macht also keinen Sinn das hier noch einmal zu Wiederholen. Daher: bitte dort nachlesen und wiederkommen \ud83d\ude09<\/p>\n\n\n\n<p><strong>Update<\/strong>: nicht vergessen, die Eingabecodierung f\u00fcr eine Registermaschine belegt nicht das erste Register \\(R_0\\)!<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n\\(EC^{(k)}(x1,&#8230;,x_k):=(0,x_1,&#8230;,x_k)\\)\n<\/blockquote>\n\n\n\n<p>Ebenso ergeht es uns mit der Ausgabecodierung: uns ist egal, was in den anderen Registern steht, wir finden nur das erste Register spannend:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n\\(AC(a_0,a_1,&#8230;):=a_0\\)\n<\/blockquote>\n\n\n\n<p><strong>Antwort zum Lernziel:<\/strong> die Registermaschinen bestehen aus Registern mit durch die Eingabecodierung induzierten Registerbelegungen und der &#8222;Ausgabecodierungs-Funktion&#8220;, welche uns das 1. Register (Register \\(R_0\\)) der Registermaschine als Ausgaberegister festlegt. Dadurch ist es uns nur m\u00f6glich die Register \\(R_1-R_m\\) mittels Eingabecodierung zu belegen.<\/p>\n\n\n\n<p>Die Registermaschine verf\u00fcgt nur \u00fcber drei Grundoperationen: Addition von \\(1\\), <del>Subtraktion<\/del> arithmetische Differenz und Test auf \\(0\\).<strong><br><\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 5<\/h2>\n\n\n\n<p><em>Angabe und Erl\u00e4uterung der Definition einer verallgemeinerten Registermaschine<\/em><\/p>\n\n\n\n<p>Auch die Erl\u00e4uterungen zur verallgemeinerte Registermaschine sind <a href=\"https:\/\/fernuni.digreb.net\/?p=468\">hier<\/a> zu finden. Daher k\u00fcmmern wir uns nur um das Lernziel.<\/p>\n\n\n\n<p><strong>Antwort zum Lernziel:<\/strong> Durch die verallgemeinerte Registermaschine ist es uns m\u00f6glich weitaus mehr Operationen als die Grundoperationen Addition und Subtraktion von \\(1\\), sowie Test auf \\(0\\) durchzuf\u00fchren.<\/p>\n\n\n\n<p>Diese Operationen werden jedoch aus den Grundoperationen zusammengesetzt und erlauben es uns Registerinhalte miteinander zu vergleichen oder Registern Werte zuzuweisen, die durch Funktionen berechnet wurden (wobei Registerinhalte der Registermaschine selbst als Parameter dieser Funktion fungieren k\u00f6nnen).<strong><br><\/strong><\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 6<\/h2>\n\n\n\n<p><em>Angabe der Definition einer berechenbaren Zahlenfunktion<\/em><\/p>\n\n\n\n<p>Ich gebe mal ganz frech die Definition aus dem Skript wieder:<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>Eine Funktion \\(f:\\subseteq\\mathbb{N}^k\\rightarrow\\mathbb{N}\\) hei\u00dft <strong>berechenbar<\/strong> wenn es eine \\(k\\)-stellige Registermaschine \\(M\\) gibt, die sie berechnet, so dass gilt: \\(f=f_M\\).<\/p>\n<\/blockquote>\n\n\n\n<p>Das ist eine der zentralen Definitionen im Teil A der theoretischen Informatik und findet sich auch h\u00e4ufig als Frage in den Protokollen der m\u00fcndlichen Pr\u00fcfung wieder: diese Definition sagt uns, dass wir eine Funktion dann berechenbar nennen k\u00f6nnen, wenn wir eine Registermaschine angeben, die sie berechnet und im Endeffekt auf die Grundoperationen Addition und Subtraktion von \\(1\\) sowie Test auf \\(0\\) zur\u00fcckf\u00fchrt.<\/p>\n\n\n\n<p><strong>Beispiel<\/strong>: \\(f(x,y)=x+y\\)<\/p>\n\n\n\n<p>Wollen wir also nachweisen, dass die Funktion \\(f\\) berechenbar ist, so m\u00fcssen wir eine Registermaschine inkl. Flussdiagramm angeben, dass uns die gleiche Ausgabe in Register \\(R_0\\) liefert, wie die Funktion \\(f\\).<\/p>\n\n\n\n<p>F\u00fcr Details und den Beweis, dass die Addition zweier Register (\\(f(x,y)=x+y\\)) berechenbar ist, empfehle ich euch <a href=\"https:\/\/fernuni.digreb.net\/?p=515\">hier<\/a>&nbsp;den alten Beitrag zum Thema.<\/p>\n\n\n\n<p><strong>Antwort zum Lernziel: <\/strong>Wir k\u00f6nnen eine Funktion mit \\(k\\)Parametern also berechenbar nennen wenn wir sie mit einer \\(k\\)-stelligen Registermaschine und der Grundoperationen innerhalb eines Flussdiagramms berechnen k\u00f6nnen., so dass gilt: \\(f = f_M\\).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Lernziel 7<\/h2>\n\n\n\n<p><em>Zeigen, dass eine Funktion berechenbar ist<\/em><\/p>\n\n\n\n<p>Das Thema wurde ebenfalls <a href=\"https:\/\/fernuni.digreb.net\/?p=515\">hier<\/a> detaillierter besprochen und gezeigt wie man eine Funktion (das angesprochene Beispiel mit der Addition zweier Register) als berechenbar nachweist. Ich begn\u00fcge mich also hier mit dem letzten Lernziel dieser Kurseinheit.<\/p>\n\n\n\n<p><strong>Antwort zum Lernziel:<\/strong> Um zu beweisen, dass eine Funktion berechenbar ist, muss man diese am Ende nur mit den Grundoperationen Subtraktion und Addition von \\(1\\) und Test auf \\(0\\) abbilden k\u00f6nnen.<\/p>\n\n\n\n<p>Hat man z.B. die Addition mittels dieser Grundoperationen nachgebildet und mittels vollst\u00e4ndiger Induktion bewiesen, dass sie f\u00fcr alle Werte das gew\u00fcnschte Ergebnis liefert, so kann man diese komplexe Operation nun in seiner verallgemeinerten Registermaschine f\u00fcr weitere Beweise anderer Funktionen nutzen.<\/p>\n\n\n\n<p>Z.B. kann man ausgehend von den Grundoperationen die Addition zweier Register \\(x+y\\) beweisen und anschlie\u00dfend mit der Addition den Beweis der Multiplikation \\(x\\cdot y\\) angehen. Mit der Multiplikation gelingt uns dann das Beweisverfahren f\u00fcr die Exponentialfunktion \\(x^y\\), usw.<\/p>\n\n\n\n<p>Die Lernziele von Kurseinheit 1 haben wir damit durch. Noch 6 und der Kurs ist komplett \ud83d\ude09 Bei Fehler wie immer: ASAP in die Kommentare damit falsches Zeug nicht so lange online bleibt!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: Einwand von Felix aufgenommen. Update:&nbsp;Marion hat einen Fehler bei der Berechnung der gefunden. Danke! Update: Eine Registermaschine kann nicht die Subtraktion, sondern nur die arithmetische Differenz. Update: Hinweis darauf, dass das erste Register bei der Eingabecodierung f\u00fcr eine Maschine belegt werden kann (wir haben keine Einschr\u00e4nkungen), aber nicht durch die Eingabecodierung f\u00fcr eine Registermaschine! &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=2093\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: Flussdiagramme, Maschinen und berechenbare Zahlenfunktionen (Lernziele KE1, 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-2093","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\/2093","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=2093"}],"version-history":[{"count":62,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2093\/revisions"}],"predecessor-version":[{"id":3350,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2093\/revisions\/3350"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2093"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2093"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2093"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}