{"id":2133,"date":"2013-06-27T17:50:24","date_gmt":"2013-06-27T15:50:24","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=2133"},"modified":"2025-11-25T21:20:45","modified_gmt":"2025-11-25T20:20:45","slug":"tia-turingmaschinen-bandmaschinen-und-berechenbare-wortfunktionen-lernziele-ke3","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=2133","title":{"rendered":"TIA: Turingmaschinen, Bandmaschinen und berechenbare Wortfunktionen (Lernziele KE3, Update II)"},"content":{"rendered":"<p><strong>Update 3<\/strong>: Korrektur nach Einwand von <a href=\"https:\/\/fernuni.digreb.net\/?p=2133#comment-10778\">Phil<\/a>. Finde ich super, dass Ihr nach fast 3 Jahren immer noch Fehler aufsp\u00fcrt und in den Kommentaren helft, die zu entfernen. Danke!<\/p>\n<p><strong>Update 2<\/strong>: Bitte Kommentar von Steve beachten. Grafik habe ich nun ersetzt (Marke 9 hinzugef\u00fcgt), aber die Punkte f\u00fcr die &#8222;Endlosigkeit&#8220; der B\u00e4nder in den Beispielen m\u00fcsst Ihr euch noch dazu denken. Auf die habe ich der \u00dcbersichtlichkeit halber (ja, nur der \u00dcbersichtlichkeit wegen! Gegen den Einwand, dass meine Schreibfaulheit daran Schuld w\u00e4re, wehre ich mich\u00a0entschieden(!)) in den Beispielen\u00a0verzichtet \ud83d\ude09<\/p>\n<p><strong>Update<\/strong>: Flussdiagramm Lernziel 2 abge\u00e4ndert. Danke Basti!<\/p>\n<p>Nun kommen wir zu den Turing- und Bandmaschinen.<\/p>\n<p>Wir n\u00e4hren uns also der Essenz des ersten Teils der theoretischen Informatik. Die folgenden Beitr\u00e4ge wurden f\u00fcr diese Kurseinheit bereits erstellt und sind in den passenden Lernzielen entsprechend verlinkt.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><a title=\"TI: Turing-Maschinen, Hilfssymbole und Lernziele KE3 (Update)\" href=\"https:\/\/fernuni.digreb.net\/?p=754\">Turing-Maschinen, Hilfssymbole und Lernziele KE3<\/a><\/li>\n<\/ul>\n<p>Ich empfehle daher sich einfach mal entlang dieses Beitrags zu hangeln und die Details dann entsprechen der Verlinkung aus dem anderen Beitrag zu holen.<\/p>\n<h2>Lernziel 1<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung der Definition einer Turingmaschine<br \/>\n<\/em><\/p>\n<p>Das, was im oben verlinkten Beitrag steht, fassen wir hier noch einmal kurz zusammen, da wir dort nur die Einbandmaschine im Detail beschrieben haben.<\/p>\n<p>Die Turingmaschine (Mehrbandmaschine) ist definiert als:<\/p>\n<blockquote>\\(M=(F,(\\Sigma^{*})^k,\\Sigma^{*},EC^{(k)},AC)\\)\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Das \\(F\\) der Turingmaschine ist unser Flussdiagramm<\/li>\n<li>\\((\\Sigma^{*})^{k}\\) sind unsere beliebig langen \\(k\\) Worte \u00fcber dem Alphabet \\(\\Sigma\\), welche sp\u00e4ter auf die \\(k\\) B\u00e4nder geschrieben werden.<\/li>\n<li>Die Turingmaschine\u00a0operiert auf unendlichen Folge von B\u00e4ndern als Datenspeicher mit dem darauf verwendeten Arbeitsalphabet \\(\\Gamma\\).<\/li>\n<li>Die Turingmaschine hat folgende <strong>Eingabecodierung<\/strong>: \\(EC^{(k)}:(\\Sigma^{*})^k\\rightarrow D\\), definiert als<br \/>\n\\(EC^{(k)}(x_1,&#8230;,x_k):=((\\epsilon,B,\\epsilon),(\\epsilon,B,x_1),&#8230;,(\\epsilon,B,x_k),(\\epsilon,B,\\epsilon))\\)<br \/>\nDas bedeutet nichts anderes, als dass wir jedes Eingabewort auf jeweils ein Band schreiben und alle anderen B\u00e4nder leer sind.<br \/>\n<strong>Beispiel<\/strong>:\u00a0\\(EC^{(3)}(aaa,b,bba):=((\\epsilon,B,\\epsilon),(\\epsilon,B,aaa),(\\epsilon,B,b),(\\epsilon,B,bba),&#8230;,(\\epsilon,B,\\epsilon))\\)<br \/>\nInitial steht also der Lesekopf \u00fcber dem ersten Blank.<\/li>\n<li>Die Turingmaschine hat folgende <strong>Ausgabecodierung<\/strong> \\(AC\\): das l\u00e4ngste Wort auf Band \\(0\\) , welches direkt links vom Lesekopf steht und nur Zeichen aus dem Alphabet \\(\\Sigma\\) beinhaltet. Lesen wir die Ausgabe also zur\u00fcck, so stoppen wir beim \\(B\\); die bis dahin gelesenen Zeichen sind unsere Ausgabe.<\/li>\n<li>Die Turingmaschine besteht nur aus folgenden <strong>Befehlen<\/strong>:\n<ul>\n<li>\\(i:L\\) Lesekopf auf Band \\(i\\) ein Feld nach links<\/li>\n<li>\\(i:R\\)\u00a0Lesekopf auf Band \\(i\\) ein Feld nach rechts<\/li>\n<li>\\(i:a\\)\u00a0Schreibe auf Band \\(i\\) das Zeichen \\(a\\) unter den Kopf<\/li>\n<li>\\(i:a?\\)\u00a0Teste auf Band \\(i\\), ob das Zeichen \\(a\\) unter dem Kopf steht<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<p><strong>Achtung<\/strong>: <del>sollte bei einer Links- oder Rechtsbewegung dann pl\u00f6tzlich ein \\(\\epsilon\\) unter dem Lesekopf stehen, wird ein Blank \\(B\\) daraus, da \\(\\epsilon\\) nicht zum Alphabet geh\u00f6rt.<\/del><\/p>\n<p>Der Einwand vom Phil in den Kommentaren ist berechtigt. \\(\\epsilon\\) geh\u00f6rt nicht zum Alphabet und wird nur f\u00fcr die Darstellung als Tripel \\((u,v,w)\\) benutzt (siehe letzter <a href=\"https:\/\/fernuni.digreb.net\/?p=2133#comment-10778\">Kommentar<\/a>).<\/p><\/blockquote>\n<p>Ist doch nicht so schwer, oder. Beispiel?<\/p>\n<p><strong>Beispiel<\/strong>: Turingmaschine\u00a0\\(M=(F,(\\Sigma^{*})^k,\\Sigma^{*},EC^{(k)},AC)\\)<\/p>\n<p style=\"padding-left: 30px;\">Alphabet \\(\\Sigma=\\{1,0\\}\\), besteht nur aus \\(1\\) oder \\(0\\)<\/p>\n<p style=\"padding-left: 30px;\">Anzahl der Arbeitsb\u00e4nder und somit auch unserer Worte: \\(k=2\\)<\/p>\n<p style=\"padding-left: 30px;\">Arbeitsalphbet \\(\\Gamma\\), dass aus unserem \\(\\Sigma\\) und einem Blank \\(\\{B\\}\\) besteht.<\/p>\n<p style=\"padding-left: 30px;\">Die oben definierte Eingabecodierung \\(EC\\)<\/p>\n<p style=\"padding-left: 30px;\">Die oben definierte Ausgabecodierung \\(AC\\)<\/p>\n<p style=\"padding-left: 30px;\">Und unserem Flussdiagramm \\(F\\):<\/p>\n<p style=\"padding-left: 30px; text-align: center;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/turing_1111.png\"><\/a><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/turing_1111.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-2715\" style=\"margin-left: 0px; margin-right: 100px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/turing_1111-300x167.png\" alt=\"\" width=\"400\" height=\"223\" srcset=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/turing_1111-300x167.png 300w, https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/turing_1111.png 723w\" sizes=\"auto, (max-width: 400px) 100vw, 400px\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Download: <a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/turing_111.rar\">JFLAP-Datei Turing-Maschine 111<\/a>.<\/p>\n<p style=\"padding-left: 30px;\">Sieht etwas kompliziert aus, ist es aber nicht. Sicherlich k\u00f6nnte man das alles auch etwas einfacher gestalten.<\/p>\n<p style=\"padding-left: 30px;\">Was tut die Maschine? Es z\u00e4hlt die Einsen, die auf den B\u00e4ndern \\(1\\) und \\(2\\) auf gleicher Position stehen und schreibt dann eine \\(1\\) auf Band \\(0\\). Bei jedem Schritt werden die Zeichen auf Band \\(1\\) und \\(2\\) jedoch auch entfernt.<\/p>\n<p style=\"padding-left: 30px;\">W\u00fcrden wir die Maschine also mit \\(0100101\\) und \\(0000100\\) starten, so h\u00e4tten wir am Ende die Ausgabe \\(1\\) auf Ausgabeband \\(0\\). W\u00fcrden wir als Eingabe aber\u00a0\\(0100101\\) und \\(1010010\\) w\u00e4hlen, so w\u00e4re das Ausgabeband leer.<\/p>\n<p style=\"padding-left: 30px;\">Formal ausgedr\u00fcckt bedeutet es<\/p>\n<p style=\"padding-left: 30px;\">\\((1,(\\epsilon,B,\\epsilon),(B,0100101,B),(B,000100,B))\\) \\(\\vdash^*(6,(1,B,\\epsilon),(\\epsilon,B,\\epsilon),(\\epsilon,B,\\epsilon))\\)<\/p>\n<p style=\"padding-left: 30px;\">Ihr kennt die \\(\\vdash^{*}\\)-Notation ja bereits, aber dennoch zur Auffrischung: es bedeutet, dass ausgehend vom Marker \\(1\\) mit einem leeren Ausgabeband und \\(0100101\\) auf Band \\(1\\), sowie \\(0000100\\) auf Band \\(2\\), wir am Ende in Marker \\(6\\) (unsere \\(HALT\\)-Marke) landen und dabei folgende Bandbelegung haben: auf Band \\(0\\) steht eine \\(1\\), Band \\(1\\) und \\(2\\) sind leer.<\/p>\n<p style=\"padding-left: 30px;\">Und so sieht der 2. Fall (\\(0100101\\) und \\(1010010\\)) aus:<\/p>\n<p style=\"padding-left: 30px;\">\\((1,(\\epsilon,B,\\epsilon),(B,0100101,B),(B,1010010,B))\\) \\(\\vdash^*(6,(\\epsilon,B,\\epsilon),(\\epsilon,B,\\epsilon),(\\epsilon,B,\\epsilon))\\)<\/p>\n<p style=\"padding-left: 30px;\">Es befand sich keine \\(1\\) auf der gleichen Position auf beiden B\u00e4ndern, so ist Band \\(0\\) am Ende der Berechnung ebenfalls leer.<\/p>\n<p>Fertig!<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: das Flussdiagramm einer Turingmaschine besteht aus vier verschiedenen Befehlen (gehe links\/rechts, schreibe Zeichen \\(a\\), pr\u00fcfe ob Zeichen \\(a\\) auf dem Band steht), die auf den B\u00e4ndern ausgef\u00fchrt werden k\u00f6nnen. Die initiale Belegung belegt immer nur Band \\(1-k\\), wobei das Ausgabeband \\(0\\) leer bleibt und erst w\u00e4hrend der Berechnung beschrieben wird (oder eben nicht).<\/p>\n<p>Die Worte, die auf den B\u00e4ndern stehen k\u00f6nnen, sind \u00fcber dem Alphabet \\(\\Sigma\\) gebildet. Zus\u00e4tzlich zu den Zeichen aus \\(\\Sigma\\) wird auch noch das Blank-Zeichen \\(B\\) im Arbeitsalphabet \\(\\Gamma\\) auf den B\u00e4ndern verwendet.<\/p>\n<h2>Lernziel 2<\/h2>\n<p style=\"padding-left: 30px;\"><em>Nachweis der Berechenbarkeit einfacher Wortfunktionen<br \/>\n<\/em><\/p>\n<p>Auch ist in <a href=\"https:\/\/fernuni.digreb.net\/?p=754\">diesem Beitrag<\/a> bereits beschrieben, wie man das nachweisen kann. Das Verfahren ist \u00e4hnlich dem <a title=\"TI: Einzelschritt- und Schrittzahlfunktion sowie \u00dcbergangsrelationen (Update)\" href=\"https:\/\/fernuni.digreb.net\/?p=512\">Beispiel f\u00fcr die Einzelschrittfunktion<\/a>\u00a0und dem <a title=\"TI: Beweis der Addition zweier Register mit einer Registermaschine\" href=\"https:\/\/fernuni.digreb.net\/?p=515\">Beweis der Addition mit einer Registermaschine<\/a>, wo man Behauptungen aufstellt und diese durch vollst\u00e4ndige Induktion beweist.<\/p>\n<p>Formal ausgedr\u00fcckt m\u00fcssen wir zeigen, dass eine Wortfunktion dann berechenbar ist wenn es eine Turingmaschine gibt, die sie berechnet.<\/p>\n<blockquote><p>Eine Wortfunktion \\(f:\\subseteq(\\Sigma^*)^k\\rightarrow\\Sigma^*\\) hei\u00dft berechenbar, gdw. es eine Turingmaschine \\(M\\) gibt mit \\(f=f_M\\).<\/p><\/blockquote>\n<p><strong>Beispiel<\/strong>: \\(f(x)=1^{\\#1(x)}\\)<\/p>\n<p style=\"padding-left: 30px;\">Wir haben als Ausgabe der Wortfunktion einfach nur die Anzahl der Einsen aus dem Wort \\(x\\).<\/p>\n<p style=\"padding-left: 30px; text-align: center;\">Um zu beweisen, dass die berechenbar ist, m\u00fcssen wir also eine Turingmaschine angeben, die den gleichen Ausgabewert hat wie unsere Funktion, so dass am Ende eben gilt: \\(f=f_M\\).<\/p>\n<p style=\"padding-left: 30px; text-align: left;\">Das ist unser Flussdiagramm f\u00fcr diese \u00e4u\u00dferst komplizierte Konstruktion:<\/p>\n<p style=\"padding-left: 30px; text-align: left;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/KE3LE2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter wp-image-2692\" style=\"margin-left: 0px; margin-right: 150px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2013\/06\/KE3LE2-300x216.png\" alt=\"KE3LE2\" width=\"320\" height=\"220\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Und nun stellen wir uns die Frage, was wir beweisen wollen:<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"text-decoration: underline;\">Behauptung<\/span>: F\u00fcr alle \\(x\\in\\Sigma^{*}\\) gilt<\/p>\n<p style=\"padding-left: 30px;\">\\((1,(\\epsilon,B,\\epsilon),(\\epsilon,B,x))\\vdash^*(6,(1^{\\#1(x)},B,\\epsilon),(x,B,\\epsilon),(\\epsilon,B,\\epsilon),&#8230;)\\)<\/p>\n<p style=\"padding-left: 30px;\">Wir landen also beider Eingabe von \\(x\\) nach endlich vielen Schritten in Marker \\(6\\) und haben auf dem Ausgabeband die Anzahl der Einsen von \\(x\\), w\u00e4hrend auf Band \\(1\\) links vom Kopf unsere Eingabe steht, die wir gelesen haben.<\/p>\n<p style=\"padding-left: 30px;\"><span style=\"text-decoration: underline;\">Beweis<\/span><\/p>\n<p style=\"padding-left: 30px;\">\\(n=lg(x)\\), d.h. wir zeigen die Korrektheit \u00fcber die L\u00e4nge unserer Eingabe \\(x\\).<\/p>\n<p style=\"padding-left: 30px;\">\\(n=0\\): dabei ist die Eingabe leer, d.h. \\(x=\\epsilon\\) und wir landen direkt in \\((6,(\\epsilon,B,\\epsilon),(\\epsilon,B,\\epsilon),(\\epsilon,B,\\epsilon),&#8230;)\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(n\\rightarrow n+1\\): nun nehmen wir an, dass wir f\u00fcr alle Worte der L\u00e4nge \\(n\\) \u00fcber \\(\\Sigma\\), d.h. f\u00fcr alle \\(x\\in W_n(\\Sigma)\\) die obige Behauptung gezeigt haben.<\/p>\n<p style=\"padding-left: 30px;\">Jetzt k\u00f6nnen wir einen Schritt weiter gehen und \\(x\\in{W_{n+1}}(\\Sigma)\\) setzen. Dann gibt es ein\u00a0\\(x^{&#8218;}\\in{W_{n}}(\\Sigma)\\) und ein \\(a\\) aus \\(\\Sigma\\) mit \\(x=x^{&#8218;}a\\) mit<\/p>\n<p style=\"padding-left: 30px;\">\\((1,(\\epsilon,B,\\epsilon),(\\epsilon,B,x^{&#8218;}a))\\vdash^*(6,(1^{\\#1(x^{&#8218;}a)},B,\\epsilon),(x^{&#8218;}a,B,\\epsilon),(\\epsilon,B,\\epsilon),&#8230;)\\)<\/p>\n<p style=\"padding-left: 30px;\">wenn \\(a=1\\) und<\/p>\n<p style=\"padding-left: 30px;\">\\((1,(\\epsilon,B,\\epsilon),(\\epsilon,B,x^{&#8218;}a))\\vdash^*(6,(1^{\\#1(x^{&#8218;})},B,\\epsilon),(x^{&#8218;}a,B,\\epsilon),(\\epsilon,B,\\epsilon),&#8230;)\\)<\/p>\n<p style=\"padding-left: 30px;\">wenn \\(a=0\\).<\/p>\n<p style=\"padding-left: 30px;\">Damit gilt die Behauptung f\u00fcr alle\u00a0\\(x\\in{W_{n+1}}(\\Sigma)\\). Und wir haben \\(f=f_M\\) bewiesen.<\/p>\n<p style=\"padding-left: 30px;\">Warum ist das so?<\/p>\n<p style=\"padding-left: 30px;\">Es sieht zwar etwas kompliziert aus, ist es aber nicht wirklich. Schauen wir uns den ersten Fall doch mal genauer an:<\/p>\n<p style=\"padding-left: 30px;\"><strong>Erkl\u00e4rung<\/strong>:<\/p>\n<p style=\"padding-left: 30px;\">Wir haben ein\u00a0\\(x\\in{W_{n}}(\\Sigma)\\), d.h. unser \\(x\\) mit der L\u00e4nge \\(n\\) endet entweder mit einer \\(1\\) oder einer \\(0\\). Mehr M\u00f6glichkeiten haben wir nicht, denn das sind die einzigen Zeichen in unserem Alphabet \\(\\Sigma\\).<\/p>\n<p style=\"padding-left: 30px;\">Nehmen wir unser\u00a0\\(x\\in{W_{n+1}}(\\Sigma)\\), d.h. es ist um ein Zeichen l\u00e4nger, \u00e4ndert sich an der Anzahl der M\u00f6glichkeiten etwas? Nein, unser &#8222;\\(+1\\)&#8220; endet immer noch\u00a0entweder mit einer \\(1\\) oder einer \\(0\\).<\/p>\n<p style=\"padding-left: 30px;\">Jetzt kommt unsere Fallunterscheidung ins Spiel mit einem Zeichen aus \\(a\\in\\Sigma\\), dass nur \\(1\\) oder \\(0\\) sein kann. Damit ist in jedem Fall\u00a0\\(x=x^{&#8218;}a\\), denn \\(lg(x)=n+1\\) und \\(lg(x^{&#8218;}a)=n+1\\).<\/p>\n<p style=\"padding-left: 30px;\">Wie sieht denn unsere Ausgabe am Ende aus wenn wir \\(a=1\\) haben? Auf dem Ausgabeband steht dann die Anzahl der Einsen von \\(x^{&#8218;}\\) und \\(a\\), also \\(1^{\\#1(x^{&#8218;}a)}\\). Und bei\u00a0\\(a=0\\)? Genau! Nur die Anzahl der Einsen von \\(x^{&#8218;}\\), genau\u00a0\\(1^{\\#1(x^{&#8218;})}\\).<\/p>\n<p>Wenn wir es nun genau nehmen, gilt \\(f=f_M\\) noch nicht, denn<\/p>\n<p style=\"padding-left: 30px;\">\\(f(10111)=1111\\), w\u00e4hrend<\/p>\n<p style=\"padding-left: 30px;\">\\(f_M=(6,(1111,B,\\epsilon),(10111,B,\\epsilon),(\\epsilon,B,\\epsilon),&#8230;)\\)<\/p>\n<p>Was tun? Hier hilft unsere Ausgabecodierung \\(AC\\) (Definition siehe oben), denn \\(AC((6,(1111,B,\\epsilon),(10111,B,\\epsilon),(\\epsilon,B,\\epsilon),&#8230;))=1111\\).<\/p>\n<p>Jetzt erst gilt \\(f=f_M\\)!<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: um eine Wortfunktion als berechenbar nachzuweisen, m\u00fcssen wir eine Turingmaschine angeben, die sie berechnet. Der formale Nachweis wird mittels vollst\u00e4ndiger Induktion erbracht, indem man zeigt, dass f\u00fcr alle Eingaben \u00a0das passende Ergebnis am Ende der Berechnung (unser geliebtes Zeichen \\(\\vdash^*\\)) auf dem Ausgabeband steht.<\/p>\n<h2>Lernziel 3<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung der Definition einer Bandmaschine<br \/>\n<\/em><\/p>\n<p>Hier hatten wir auch bereits in <a href=\"https:\/\/fernuni.digreb.net\/?p=754\">diesem Beitrag<\/a> Vorarbeit geleistet. Der Unterschied zu Turingmaschinen mit \\(k\\) Arbeitsb\u00e4ndern ist nicht gro\u00df. Wir passen die Ein- und Ausgabecodierung an und \u00e4ndern die Befehle so ab, dass sie nur auf Band \\(0\\) arbeiten.<\/p>\n<p>Aus der Eingabecodierung f\u00fcr Mehrbandmaschinen mit<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>\\(EC^{(k)}(x_1,&#8230;,x_k):=((\\epsilon,B,\\epsilon),(\\epsilon,B,x_1),&#8230;,(\\epsilon,B,x_k),(\\epsilon,B,\\epsilon))\\)<\/li>\n<\/ul>\n<p>wird ganz einfach<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>\\(EC^{(k)}(x_1,&#8230;,x_k):=(\\epsilon,B,x_1B&#8230;B,x_k)\\).<\/li>\n<\/ul>\n<p>Und nun zu den Befehlen:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>\\(i:L\\rightarrow L\\)<\/li>\n<li>\\(i:R\\rightarrow R\\)<\/li>\n<li>\\(i:a\\rightarrow a\\)<\/li>\n<li>\\(i:a?\\rightarrow a?\\)<\/li>\n<\/ul>\n<p><strong>Antwort zum Lernziel<\/strong>: die Befehle einer Turingmaschine (Mehrband) behalten auch bei Bandmachinen (Einband) ihre G\u00fcltigkeit. Nur arbeiten diese statt auf \\(k+1\\) (Ausgabeband + \\(k\\) Arbeitsb\u00e4nder) B\u00e4ndern nun auf einem einzigen Band \\(0\\).<\/p>\n<p>Ebenso verh\u00e4lt es sich mit der Eingabecodierung, die angepasst werden muss. F\u00fcr die Ausgabecodierung \u00e4ndert sich nichts, es bleibt auf Band \\(0\\) als das l\u00e4ngste Wort links vom Lesekopf.<\/p>\n<h2>Lernziel 4<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung der Grundidee des Beweises Turing-berechenbar = Band-berechenbar<br \/>\n<\/em><\/p>\n<p>Das ist Turings urspr\u00fcngliche Konstruktion.<\/p>\n<p>Wenn wir doch schon so sch\u00f6n mit Mehrbandmaschinen arbeiten k\u00f6nne, wozu dann Einband? Weil beide Maschinen von der Berechnungsst\u00e4rke \u00e4quivalent sind und letztere weniger kompliziert sind. Pers\u00f6nlich finde ich, dass man mit den Mehrbandmaschinen einfacher hantieren kann, aber sei es drum.<\/p>\n<p>Die Grundidee des Beweises habe ich bereits <a href=\"https:\/\/fernuni.digreb.net\/?p=754\">hier<\/a> beschrieben, so dass wir uns nur noch um das Lernziel k\u00fcmmern m\u00fcssen. Formal ausgedr\u00fcckt l\u00e4sst sich festhalten:<\/p>\n<blockquote><p>Zu jeder Einbandmaschine \\(M\\) gibt es eine Mehrbandmaschine \\(M^{&#8218;}\\) mit dem gleichen Bandalphabet wie \\(M\\), so dass gilt: \\(f_M=f_{M^{&#8218;}}\\).<\/p>\n<p>Zu jeder Mehrbandmaschine \\(M^{&#8218;}\\) gibt es eine Einbandmaschine \\(M\\), so dass gilt: \\(f_M=f_{M^{&#8218;}}\\).<\/p><\/blockquote>\n<p>Damit haben wir uns auch schon enttarnt: wir k\u00f6nnen die Mehrbandmaschine durch ein vergr\u00f6\u00dfertes Bandaphabet simulieren. Anders herum bleibt das Bandalphabet nat\u00fcrlich gleich, denn es ist ja bereits gro\u00df.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>:\u00a0die Simulation der Mehrband- in einer Einbandmaschine erfolgt auf Basis eines vergr\u00f6\u00dferten Alphabets f\u00fcr die Darstellung der Position der Lesek\u00f6pfe auf den simulierten B\u00e4ndern.<\/p>\n<p>Damit erhalten wir &#8222;Spuren&#8220; auf dem einen Band f\u00fcr die eig. Eingabe und zus\u00e4tzliche Spuren f\u00fcr die Position der Lesek\u00f6pfe um die getrennt beweglichen Lesek\u00f6pfe auf den vormals \\(k\\) Spuren zu simulieren.<\/p>\n<p>Diese neuen Symbole, die wir f\u00fcr die Markierung der Lesek\u00f6pfe brauchen werden Hilfssymbole genannt und bereichern unser Arbeitsalphabet \\(\\Gamma\\) wenn wir sie nicht durch eine Codierung eliminiert haben (siehe n\u00e4chstes Lernziel).<\/p>\n<h2>Lernziel 5<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung der Grundidee des Beweises, dass man bei Bandmaschinen ohne Hilfssymbole auskommt<br \/>\n<\/em><\/p>\n<p>Auch hier ist im <a href=\"https:\/\/fernuni.digreb.net\/?p=754\">alten Beitrag<\/a> die Grundidee bereits beschrieben worden. Ich fasse mich daher sehr schmallippig.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: die neuen Hilfssymbole f\u00fcr die simulierte Kopfpositionen der B\u00e4nder einer Mehrbandmaschine werden anstatt durch Aufbl\u00e4hen des Arbeitsalphabets mit neuen Zeichen einfach durch eine erweiterte L\u00e4nge der W\u00f6rter \u00fcber dem alten Arbeitsalphabet \\(\\Gamma\\) codiert.<\/p>\n<p>Dadurch ist es m\u00f6glich, dass das Bandalphabet einer Einbandmaschine bei \\(\\Gamma=\\Sigma\\cup\\{B\\}\\) bleibt.<\/p>\n<p>Diesen Beitrag habe ich etwas z\u00fcgig getippt, es k\u00f6nnten sich also ein paar Fehler eingeschlichen haben. Wer etwas sieht: ab damit in die Kommentare. Danke!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update 3: Korrektur nach Einwand von Phil. Finde ich super, dass Ihr nach fast 3 Jahren immer noch Fehler aufsp\u00fcrt und in den Kommentaren helft, die zu entfernen. Danke! Update 2: Bitte Kommentar von Steve beachten. Grafik habe ich nun ersetzt (Marke 9 hinzugef\u00fcgt), aber die Punkte f\u00fcr die &#8222;Endlosigkeit&#8220; der B\u00e4nder in den Beispielen &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=2133\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: Turingmaschinen, Bandmaschinen und berechenbare Wortfunktionen (Lernziele KE3, Update II)\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-2133","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\/2133","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=2133"}],"version-history":[{"count":49,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2133\/revisions"}],"predecessor-version":[{"id":3492,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2133\/revisions\/3492"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2133"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2133"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2133"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}