{"id":1382,"date":"2013-05-16T15:37:35","date_gmt":"2013-05-16T13:37:35","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1382"},"modified":"2025-11-25T22:54:11","modified_gmt":"2025-11-25T21:54:11","slug":"tia-berechenbarkeit-auf-anderen-mengen-lernziele-ke7-22","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1382","title":{"rendered":"TIA: Berechenbarkeit auf anderen Mengen (Lernziele KE7, 2\/2)"},"content":{"rendered":"<p><strong>Update<\/strong>: mir sind einige Schnitzer beim Halteproblem aufgefallen, die ich mittlerweile ausger\u00e4umt haben sollte. Hoffe ich. Auch habe ich den Beitrag um den Beweis zum Bild- und Projektionssatz erweitert (der nun in einem eigenen Beitrag steht), was ihn leider um ein paar Seiten verl\u00e4ngert hat.<\/p>\n<p>Es gibt insg. <del>drei<\/del> vier Beitr\u00e4ge zur KE6.<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=2313\">TIA: Rekursive und rekursiv-aufz\u00e4hlbare Mengen (Lernziele KE6, 1\/4)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=2368\">TIA: Bild- und Projektionssatz (Lernziele KE6 2\/4)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=1117\">TIA: Halte- \u00c4quivalenz- und Korrektheitsproblem, Reduzierbarkeit, Satz von Rice (Lernziele KE6, 3\/4)<\/a><\/li>\n<li><a href=\"https:\/\/fernuni.digreb.net\/?p=1178\">TIA: G\u00f6del&#8217;scher Unvollst\u00e4ndigkeitssatz (Lernziele KE6, 4\/4)<\/a><\/li>\n<\/ul>\n<p>Es sind nur noch ein paar Lernziele \u00fcbrig, halten wir uns also ran.<\/p>\n<h2>Lernziel 7a<\/h2>\n<p style=\"padding-left: 30px;\"><em>Halte- und Selbstanwendbarkeitsproblem<\/em><\/p>\n<p>Die beiden Probleme sind definiert als die Mengen:<\/p>\n<blockquote>\\(K_\\varphi := \\{i \\in \\mathbb{N} \\mid \\varphi_i(i) \\mbox{ existiert}\\}\\)\n\\({K_{\\varphi}}^0 := \\{(i,x) \\in \\mathbb{N}^2 \\mid \\varphi_i(x) \\mbox{ existiert}\\}\\)\n<p><strong>Wichtig<\/strong>: Komplemente \\(\\mathbb{N}\\setminus{}K_\\varphi\\) und&nbsp;\\(\\mathbb{N}^2\\setminus{K_{\\varphi}}^0\\) <strong>sind<\/strong> nicht r.a.<\/p><\/blockquote>\n<p>In den meisten F\u00e4llen wird zun\u00e4chst gezeigt, dass das spezielle Halteproblem nicht entscheidbar ist. Anschlie\u00dfend wird das spezielle Problem auf das allgemeine zur\u00fcckgef\u00fchrt (&#8222;Wenn schon nicht entscheidbar ist, ob eine Maschine auf ihrem eigenen Wort h\u00e4lt, wie kann man dann entscheiden ob es das f\u00fcr alle Eingabeworte tut?&#8220;).<\/p>\n<p>Fangen wir daher auch zun\u00e4chst mit dem speziellen Halteproblem an.<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>Spezielles Halteproblem<\/strong><\/span><\/p>\n<p style=\"padding-left: 30px;\">Das ist die Fragestellung ob Die Maschine mit der Nr. \\(i\\) bei der Eingabe von \\(i\\) (die Maschine k\u00f6nnen wir ja als Eingabewort codieren, wie wir ja durch die Standardnummerierung und das utm-Theorem wissen) h\u00e4lt oder nicht.<\/p>\n<p style=\"padding-left: 30px;\">Diese Problem wird auch das Selbstanwendbarkeitsproblem genannt. Im Skript steht dazu:<\/p>\n<blockquote>\n<p style=\"padding-left: 30px;\"><em>&#8222;<strong>Das Selbstanwendbarkeitsproblem<\/strong>&nbsp;f\u00fcr \\(\\varphi\\) ist rekursiv unl\u00f6sbar&#8220;.<\/em><\/p>\n<\/blockquote>\n<p style=\"padding-left: 30px;\">Es bedeutet nichts anderes, als dass die Menge \\(K_\\varphi\\) zwar r.a. ist, aber nicht rekursiv\/entscheidbar. Wir k\u00f6nnen n\u00e4mlich nicht entscheiden ob eine Maschine existiert, die bei der Eingabe ihrer eigenen G\u00f6delnummer h\u00e4lt oder nicht. Warum?<\/p>\n<p style=\"padding-left: 30px;\">Es gibt hier, nehmen wir es genau, zwei M\u00f6glichkeiten. Beide funktionieren durch Widerspruch, indem gezeigt wird, dass es so eine Maschine nicht geben kann, die dieses Problem entscheidet. Ihr k\u00f6nnt euch also entscheiden welche Art von Darstellung euch eher zusagt.<\/p>\n<p style=\"padding-left: 30px;\">Da ich einen anschaulichen Beweis f\u00fcr das allgemeine Problem brauchte, habe ich mir die graphische Variante daf\u00fcr aufgespart und vertr\u00f6ste euch auf h\u00fcbsche Bildchen im n\u00e4chsten Abschnitt.<\/p>\n<p style=\"padding-left: 30px;\">Zun\u00e4chst ein sehr sch\u00f6ner (wie ich finde) Widerspruchsbeweis f\u00fcr das spezielle Halteproblem.<\/p>\n<p style=\"padding-left: 30px;\"><strong>Klassischer Widerspruchsbeweis f\u00fcr das spezielle Halteproblem<\/strong><\/p>\n<p style=\"padding-left: 60px;\">Es gibt also noch eine Methode, die weniger graphischen Umgang mit Open Office Produkten erfordert, wir damit aber dennoch eine sch\u00f6ne, logische Kette von Schl\u00fcssen ziehen k\u00f6nnen und dabei zu einem Widerspruch gelangen.<\/p>\n<p style=\"padding-left: 60px;\">Dazu bem\u00fche ich das Barbier-Paradoxon wie Socher in seinem Buch (siehe oben rechts) und zitiere ihn:<\/p>\n<p style=\"padding-left: 60px;\">Dieser klassische Widerspruchsbeweis hat gro\u00dfe&nbsp;\u00c4hnlichkeit mit dem&nbsp;<a href=\"http:\/\/de.wikipedia.org\/wiki\/Barbier-Paradoxon\">Barbier-Problem<\/a>, der sog.&nbsp;<a href=\"http:\/\/de.wikipedia.org\/wiki\/Russellsche_Antinomie\">Russelschen Antinomie<\/a>:<\/p>\n<blockquote style=\"padding-left: 30px;\">\n<p style=\"padding-left: 60px;\"><i>Man kann einen Barbier als einen definieren, der all jene und nur jene rasiert, die sich nicht selbst rasieren.<\/i><\/p>\n<p style=\"padding-left: 60px;\"><i>Die Frage ist: Rasiert der Barbier sich selbst?<\/i><\/p>\n<\/blockquote>\n<p style=\"padding-left: 60px;\">Wenn man versucht die Frage zu beantworten, landet man stets in einem Widerspruch. Wie bei der folgenden \u00dcberlegung f\u00fcr das spezielle Halteproblem:<\/p>\n<ul style=\"list-style-type: square; padding-left: 60px;\">\n<li>Nehmen wir an die M\u00e4nner, die sich selbst rasieren sind unsere Turing-Maschinen \\(M_i\\), die sich selbst, also \\(i\\), akzeptieren. Sie halten bei der Eingabe ihrer eigenen G\u00f6delnummer. Formal:<\/li>\n<\/ul>\n<p style=\"padding-left: 60px;\">\\(M_i(i)\\) existiert.<\/p>\n<p style=\"padding-left: 60px;\">Annahme: es gibt eine Maschine \\(H\\), die \\(1\\) ausgibt wenn die Maschine \\(M_i\\) bei ihrer G\u00f6delnummer h\u00e4lt und ansonsten in eine Endlosschleife ger\u00e4t. Formal:<\/p>\n<p style=\"padding-left: 60px;\">\\(H(i)=\\begin{cases} 1, &amp; \\mbox{ falls } M_i(i)\\mbox{ existiert} \\\\ \\perp, &amp; \\mbox{ sonst}\\end{cases}\\)<\/p>\n<ul style=\"list-style-type: square; padding-left: 60px;\">\n<li>Nun konstruieren wir die Maschine \\(B\\) (den Barbier), diese sagt uns ob die Maschine \\(M_i\\) bei der Eingabe ihrer G\u00f6delnummer \\(i\\) h\u00e4lt oder nicht indem er die Maschine \\(H\\) mit einer G\u00f6delnummer startet. Gibt uns \\(H\\) eine \\(1\\) zur\u00fcck, so ger\u00e4t \\(B\\) in eine Endlosschleife. Ger\u00e4t \\(H\\) in eine Endlosschleife, akzeptiert \\(B\\) die Ausgabe. Formal:<\/li>\n<\/ul>\n<p style=\"padding-left: 60px;\">\\(B(i)=\\begin{cases} 1, &amp; \\mbox{ falls } H(i)=\\perp \\\\ \\perp, &amp; \\mbox{ falls }H(i)=1\\end{cases}\\)<\/p>\n<p style=\"padding-left: 60px;\">In anderen Worten:<\/p>\n<p style=\"padding-left: 90px;\"><em>\\(B\\) akzeptiert \\(M\\) genau dann wenn \\(M\\) sich nicht selbst akzeptiert<\/em><\/p>\n<p style=\"padding-left: 60px;\">Da wir im Endeffekt ja \\(M=B\\) haben wenn wir \\(B\\) auf sich selbst ausf\u00fchren, so ist das Dilemma, in welches wir laufen genau das <a href=\"http:\/\/de.wikipedia.org\/wiki\/Russellsche_Antinomie\">Barbier-Paradoxon von Russel<\/a>:<\/p>\n<p style=\"padding-left: 90px;\"><em>\\(B\\) akzeptiert \\(B\\) genau dann wenn \\(B\\) sich nicht selbst akzeptiert<\/em><\/p>\n<p style=\"padding-left: 60px;\"><strong>Fall 1<\/strong>: \\(B\\) h\u00e4lt, wir starten \\(B\\) mit seiner eigenen Nr. \\(i\\)<\/p>\n<p style=\"padding-left: 90px;\">\\(B(i)=1\\Rightarrow H(i)=\\perp\\Rightarrow M_i(i)=\\perp\\Rightarrow B(i)=\\perp\\). Widerspruch!<\/p>\n<p style=\"padding-left: 60px;\"><strong>Fall 2<\/strong>:&nbsp;\\(B\\) h\u00e4lt nicht, wir starten \\(B\\) also mit seiner eigenen Nr. \\(i\\)<\/p>\n<p style=\"padding-left: 90px;\">\\(B(i)=\\perp\\Rightarrow H(i)=\\perp\\Rightarrow M_i(i)=1\\Rightarrow B(i)=1\\). Widerspruch!<\/p>\n<p style=\"padding-left: 60px;\">Denn in beiden F\u00e4llen ist ja \\(B=M\\)<\/p>\n<p style=\"padding-left: 60px;\">Damit kann es keine Maschine geben, die das spezielle Halteproblem entscheidet.<\/p>\n<p style=\"padding-left: 60px;\">Obwohl wir den Regeln der Logik gefolgt sind, stie\u00dfen wir auf einen Widerspruch. Das bedeutet, dass unsere Grundannahme, so eine Maschine \\(B\\) k\u00f6nne existieren, falsch war.<\/p>\n<p style=\"padding-left: 60px;\">Kommen wir nun zum allgemeinen Halteproblem.<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>Allgemeines Halteproblem<\/strong><\/span><\/p>\n<p style=\"padding-left: 30px;\">Zum speziellen Halteproblem, also der Frage ob eine Maschine \\(M_i\\) angewendet auf sich selbst h\u00e4lt oder nicht gibt es noch die allgemeine Version mit folgender, formalen Definition (Wiederholung von oben):<\/p>\n<blockquote>\n<p style=\"padding-left: 30px;\">\\({K_{\\varphi}}^0 := \\{(i,x) \\in \\mathbb{N}^2 \\mid \\varphi_i(x) \\mbox{ existiert}\\}\\)<\/p>\n<\/blockquote>\n<p style=\"padding-left: 30px;\">Anders ausgedr\u00fcckt:<\/p>\n<blockquote>\n<p style=\"padding-left: 30px;\"><em>H\u00e4lt die Maschine \\(M_i\\) bei der Eingabe von \\(x\\)?<\/em><\/p>\n<\/blockquote>\n<p style=\"padding-left: 30px;\">Zuerst nochmal die Wiederholung: wann ist eine Menge \\(A\\subseteq{B}\\) entscheidbar? Genau dann wenn neben \\(A\\) auch das Komplement \\(B\\setminus{A}\\) semi-entscheidbar ist.<\/p>\n<p style=\"padding-left: 30px;\">Die Menge \\({K_{\\varphi}}^0\\)&nbsp;ist selbst r.a.. Warum? Wenn eine Maschine \\(i\\) bei der Eingabe \\(x\\) h\u00e4lt, dann h\u00e4lt sie. Wir haben in jedem Fall bei einem positiven Entscheid eine Ausgabe und damit einen positiven Entscheid (sofern es den gibt). Ansonsten rechnet die Maschine ewig weiter.<\/p>\n<p style=\"padding-left: 30px;\">Wir k\u00f6nnen die Elemente der positiven Menge \\((i,x)\\) (&#8222;H\u00e4lt Maschine \\(i\\) bei Eingabe von \\(x\\)&#8222;) also &#8222;aufz\u00e4hlen&#8220;. Wenn sie denn wirklich h\u00e4lt. Die Elemente der anderen Menge, die Menge der Kombinationen von \\((i,x)\\), wo eine Maschine \\(M_i\\) bei der Eingabe von \\(x\\) <strong>nicht h\u00e4lt<\/strong> aber eben nicht (im ung\u00fcnstigsten Fall rechnet die Maschine \\(i\\) bei der Eingabe von \\(x\\) n\u00e4mlich ewig).<\/p>\n<p style=\"padding-left: 30px;\">Diese positive Menge nennen wir eben<\/p>\n<p style=\"padding-left: 60px;\">\\({K_{\\varphi}}^0\\)<\/p>\n<p style=\"padding-left: 30px;\">Die negative Menge ist das Komplement davon, n\u00e4mlich:<\/p>\n<p style=\"padding-left: 60px;\">\\(\\mathbb{N}^2\\setminus{K_{\\varphi}}^0\\)<\/p>\n<p style=\"padding-left: 30px;\">W\u00e4hrend die obere, wie erw\u00e4hnt, semi-entscheidbar\/rekursiv-aufz\u00e4hlbar ist, ist es das Komplement leider nicht. W\u00e4re sie das, so w\u00e4ren alle unsere Probleme gel\u00f6st und die Menge&nbsp;\\({K_{\\varphi}}^0\\) w\u00e4re entscheidbar\/rekursiv.<\/p>\n<p style=\"padding-left: 30px;\">Formal ausgedr\u00fcckt m\u00fcsste f\u00fcr die Semi-Entscheidbarkeit von&nbsp;\\(\\mathbb{N}^2\\setminus{K_{\\varphi}}^0\\) die &#8222;halbe&#8220; charakteristische Funktion berechenbar sein:<\/p>\n<p style=\"padding-left: 60px;\">\\(\\chi^{&#8218;}_{{{K_{\\varphi}}^0}(i,x)}=\\begin{cases} 1, &amp; \\mbox{ falls }i\\text{ bei der Eingabe von }x\\text{ haelt}\\\\ \\perp, &amp; \\mbox{sonst}\\end{cases}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(\\chi^{&#8218;}_{{K_{\\varphi}}^0}\\) ist, wie wir gemerkt haben berechenbar.&nbsp;Damit ist unsere Menge \\({K_{\\varphi}}^0\\) aber leider nur r.a.<\/p>\n<p style=\"padding-left: 30px;\">W\u00e4re aber nicht schlimm: Wenn wir zeigen k\u00f6nnen, dass \\(\\mathbb{N}\\setminus{K_{\\varphi}}^0\\) auch r.a. ist, so w\u00e4re \\({K_{\\varphi}}^0\\) der Definition nach entscheidbar. Warum das nicht geht, zeigen wir jetzt.<\/p>\n<p style=\"padding-left: 60px;\">\\(\\chi^{&#8220;}_{{{\\mathbb{N}^2\\setminus K_{\\varphi}}}^0(i,x)}=\\begin{cases} 1, &amp; \\mbox{ falls }i\\text{ bei der Eingabe von }x\\text{ nicht haelt}\\\\ \\perp, &amp; \\mbox{sonst}\\end{cases}\\)<\/p>\n<p style=\"padding-left: 30px;\">Da wir nicht wissen, ob die Maschine \\(i\\) bei der Eingabe von \\(x\\) niemals h\u00e4lt oder einfach nur&nbsp;<strong>noch nicht<\/strong> gehalten hat weil sie noch rechnet, k\u00f6nnen wir die Funktion&nbsp;\\(\\chi^{&#8220;}_{{{\\mathbb{N}^2\\setminus K_{\\varphi}}}^0(i,x)}\\) nicht berechnen. Das leuchtet eig. schon direkt ein.<\/p>\n<p style=\"padding-left: 30px;\">Aber um das alles noch komplett ad absurdum zu f\u00fchren tun wir folgendes:<\/p>\n<p style=\"padding-left: 30px;\"><strong>Beweis anhand des speziellen Halteproblems<\/strong><\/p>\n<p style=\"padding-left: 60px;\">Wie wir gesehen haben, ist das spezielle Halteproblem nicht l\u00f6sbar. Daraus folgt auch ganz simpel, dass es keine Maschine \\(H(i,x)\\) geben kann, die f\u00fcr <strong>jedes<\/strong> \\(x\\) entscheidet ob Maschine \\(M_i\\) bei der Eingabe von \\(x\\) h\u00e4lt oder nicht.<\/p>\n<p style=\"padding-left: 60px;\">Warum? Weil eines der \\(x\\) auch die Nummer der Maschine \\(M_i\\) selbst ist, d.h. \\(x=i\\). Und wir wir haben im letzten Abschnitt gesehen, dass genau das nicht geht.<\/p>\n<p style=\"padding-left: 60px;\">Einfach, nicht? Und wenn wir die Unl\u00f6sbarkeit des allgemeinen Halteproblems beweisen wollen, ohne zuerst die Unl\u00f6sbarkeit des speziellen Halteproblems bewiesen zu haben? Dann machen wir das mit einem klassischen, graphischen Widerspruchsbeweis durch Diagonalisierung.<\/p>\n<p style=\"padding-left: 30px;\"><strong>Graphischer Widerspruchsbeweis mittels Diagonalisierung<\/strong><\/p>\n<p style=\"padding-left: 60px;\">Dieser Beweis ist dem Diagonalverfahren von Cantor sehr \u00e4hnlich und ist im Grunde auch ein Beweis f\u00fcr das spezielle Halteproblem.<\/p>\n<p style=\"padding-left: 60px;\">Was haben wir vor? Wir machen hier einfach eine Annahme, dass es eine best. Maschine gibt und zeigen, dass es sie nicht geben kann. Wir f\u00fchren unsere Annahme also zu einem Widerspruch. Ganz einfach.<\/p>\n<p style=\"padding-left: 60px;\">Konstruieren wir zun\u00e4chst eine Matrix, wo wir auf der \\(y\\)-Achse alle unsere Maschinen aufsteigend ihrer G\u00f6delnummer \\(0,&#8230;,n\\) auflisten. Auf der \\(x\\)-Achse stehen alle Eingabeworte \\(1^0, &#8230;, 1^x\\). In den Zellen steht dann drin ob die Maschine f\u00fcr die Eingabe des Wortes h\u00e4lt oder nicht:<\/p>\n<p style=\"padding-left: 90px;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/halteproblem3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone\" style=\"margin-left: 10px; margin-right: 200px;\" title=\"halteproblem\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/halteproblem3.png\" alt=\"\" width=\"300\" height=\"250\"><\/a><\/p>\n<p style=\"padding-left: 60px;\">\n<p style=\"padding-left: 60px;\">G\u00e4be es eine Maschine, die entscheiden k\u00f6nnte ob eine andere Maschine bei der Eingabe h\u00e4lt, so w\u00fcrde sie uns genau diese Matrix konstruieren.<\/p>\n<p style=\"padding-left: 60px;\">In dieser Matrix stehen alle Maschinen und alle Worte drin. Nun basteln wir uns eine neue Maschine \\(H\\), welche zum Eingabewort \\(1^i\\) das Matrixelement \\((i,i)\\) berechnet und sich genau entgegengesetzt zur Maschine \\(T_i\\) verh\u00e4lt (sie h\u00e4lt wenn dort \\(T_i\\) bei der Eingabe von \\(i\\) nicht halten w\u00fcrde und l\u00e4uft in eine Endlosschleife wenn dort \\(T_i\\) halten w\u00fcrde).<\/p>\n<p style=\"padding-left: 60px;\">Diese neue Maschine \\(H\\) ist ja selbst eine Turing-Maschine. Damit m\u00fcssten wir sie ja in unserer Matrix vorfinden. Tun wir aber nicht, denn egal wo wir nachschauen: unsere neue Maschine hat bei seinen Berechnungen immer&nbsp;mindestens einen unterschiedlichen Ergebniswert als Maschine \\(T_i\\) beim Wort \\(i\\) und ist daher tats\u00e4chlich neu. Was aber nicht sein kann, denn wir haben in der Matrix nach Definition alle Turingmaschinen bereits drin.<\/p>\n<p style=\"padding-left: 60px;\">Widerspruch!<\/p>\n<p>Etwas abstrakt, aber durchaus logisch nachvollziehbar. Das ist das sch\u00f6ne an Widerspruchsbeweisen.&nbsp;Falls Ihr das nicht direkt beim Lesen nachvollziehen konntet: schreibt euch das einfach auf&#8217;s Papier. Dann kommt der &#8222;Aha-Effekt&#8220;, versprochen.<\/p>\n<p>Wem das zu abstrakt war, der schaue sich nochmal&nbsp;<a title=\"TI: Entscheidbarkeit und charakteristische Funktion\" href=\"https:\/\/fernuni.digreb.net\/?p=909\">folgenden Beitrag<\/a>&nbsp;an. Dort wird die \u00dcberabz\u00e4hlbarkeit von \\(\\mathbb{R}\\) mit dem gleichen Verfahren bewiesen.<\/p>\n<p>Zusammenfassend wird die Beweisf\u00fchrung h\u00e4ufig nach folgendem Muster gef\u00fchrt:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li><span style=\"line-height: 13px;\">spezielles Halteproblem (auch Diagonalsprache genannt), wo die Maschine auf sich selbst angewendet wird, ist nicht entscheidbar. Gezeigt wird es meist durch Diagonalisierung.&nbsp;<\/span><\/li>\n<li>Komplement dieser Menge ist nicht einmal semi-entscheidbar, da wir dazu diese &#8222;Diagonalisierungsmaschine&#8220; br\u00e4uchten. Und diese kann es ja nicht geben.<\/li>\n<li>Daraus folgt, dass das allgemeine Halteproblem auch nicht entscheidbar ist. Denn sonst w\u00e4re sein Komplement semi-entscheidbar. Das geht aber nicht, da eine Eingabe das eigene Wort der Maschine ist. Und wie wir bewiesen haben, kann es keine Maschine geben, die entscheidet ob eine Maschine angewendet auf sich selbst h\u00e4lt oder nicht.<\/li>\n<\/ul>\n<p><strong>Antwort zum Lernziel<\/strong>: das Halteproblem bezeichnet die Fragestellung ob eine Maschine bei der Eingabe eines Eingabewertes h\u00e4lt oder nicht. Es ist nur semi-entscheidbar\/rekursiv-aufz\u00e4hlbar.<\/p>\n<p>Bei dem speziellen Halteproblem ist die Fragestellung ob eine Maschine angewendet auf seine eigene G\u00f6delnummer h\u00e4lt oder nicht. Diese Menge ist ebenfalls nur semi-entscheidbar\/rekursiv-aufz\u00e4hlbar.<\/p>\n<p>Die Komplemente dieser Fragestellungen sind nicht semi-entscheidbar\/rekursiv-aufz\u00e4hlbar (wir k\u00f6nnen nicht wissen ob die Maschine nie h\u00e4lt oder nur noch rechnet und doch noch halten wird). W\u00e4ren sie das, so w\u00e4ren auch die Halteprobleme entscheidbar\/rekursiv.<\/p>\n<h2>Lernziel 8<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erkl\u00e4rung der Reduzierbarkeit und Methode der Reduktion<\/em><\/p>\n<p>Reduzierbarkeit, formal definiert hei\u00dft:<\/p>\n<blockquote>\\(A \\leq B : \\Longleftrightarrow \\exists f \\in R^{(1)}. A = f^{-1}[B]\\)\n<p><em>\\(A\\) ist reduzierbar auf \\(B\\) genau dann wenn die Menge \\(A\\) eine Urbildmenge von \\(B\\) unter \\(f\\) ist<\/em>.<\/p><\/blockquote>\n<p>Schon wieder sowas komisches. Das bekommen wir aber auch noch klein. Zun\u00e4chst einmal haben wir eine wundersch\u00f6ne, einstellige, rekursive Funktion \\(f\\), welches uns zu einem \\(x\\) aus \\(A\\) ein Bild liefert, welches selbst in \\(B\\) liegt. Damit ist \\(A\\) die Urbildmenge von \\(B\\).<\/p>\n<p>Etwas formaler ausgedr\u00fcckt und wortw\u00f6rtlich aus dem Skript:<\/p>\n<blockquote><p>\\((x \\in A \\Rightarrow f(x) \\in B)\\) und \\((x \\notin A \\Rightarrow f(x) \\notin B)\\).<\/p><\/blockquote>\n<p>Liegt ein \\(x\\) in \\(A\\), so liegt auch sein Bild (Funktionswert) \\(f(x)\\) in \\(B\\). Liegt ein \\(x\\) nicht in \\(A\\), so liegt auch sein Bild nicht in \\(B\\).<\/p>\n<p>Die Abschlusseigenschaften der Reduzierbarkeit sind (wir haben als Annahme 3 Mengen \\(A,B,C \\subseteq \\mathbb{N}\\)) sind \u00e4hnlich denen aus Abschlusseigenschaften rekursiver Mengen:<\/p>\n<blockquote><p>1. \\(A \\leq B\\) und&nbsp;\\(B \\leq C \\Rightarrow A \\leq C\\)<\/p>\n<p><em><em>Erl\u00e4uterung:&nbsp;<\/em>Ist \\(A\\) reduzierbar auf \\(B\\) und \\(B\\) reduzierbar auf \\(C\\), so ist auch \\(A\\) reduzierbar auf \\(C\\). Simple Transitivit\u00e4t.<\/em><\/p>\n<p>2.&nbsp;\\(A \\leq B\\Longleftrightarrow\\mathbb{N}\\setminus{A}\\leq\\mathbb{N}\\setminus{B}\\)<\/p>\n<p><em>Erl\u00e4uterung: Die Transitivit\u00e4t gilt auch f\u00fcr Komplemente von \\(A\\) und \\(B\\).<\/em><\/p>\n<p>3. \\(A \\leq B\\) und \\(B\\) rekursiv \\(\\Rightarrow A\\) rekursiv<\/p>\n<p>4. \\(A \\leq B\\) und \\(B\\) rekursiv aufz\u00e4hlbar \\(\\Rightarrow A\\) rekursiv aufz\u00e4hlbar<\/p>\n<p><em><em>Erl\u00e4uterung:&nbsp;<\/em>Auch \u00fcbernimmt die reduzierte Menge \\(A\\) die Eigenschaften der Menge \\(B\\). Ist Menge \\(B\\) r.a. oder rekursiv, so ist es auch die Menge \\(A\\) wenn man sie erfolgreich auf \\(B\\) reduzieren konnte.<\/em><\/p><\/blockquote>\n<p>Die Reduktion ist ein wichtiges Hilfsmittel. Nicht nur jetzt, sondern &#8211; wie gesagt &#8211; auch f\u00fcr die Reduktion in den Komplexit\u00e4tsklassen \\(P\\), \\(NP\\), usw. Dazu aber in den n\u00e4chsten Beitr\u00e4gen mehr.<\/p>\n<p>Was k\u00f6nnen wir derweil damit tun?<\/p>\n<p><strong>Beispiel<\/strong>: Reduktion des spezielle Halteproblem auf das&nbsp;allgemeinen Halteproblems<\/p>\n<p style=\"padding-left: 30px;\">Ist doch ein nettes Beispiel f\u00fcr eine Reduktion, oder?<\/p>\n<p style=\"padding-left: 30px;\">Formal suchen wir daher eine totale Funktion \\(f:\\mathbb{N}\\rightarrow\\mathbb{N}^2\\), die unser spezielles Halteproblem auf das allgemeine reduziert. Es muss gelten:<\/p>\n<p style=\"padding-left: 60px;\">\\(B(i)=H(f(i))\\)<\/p>\n<p style=\"padding-left: 30px;\">Erinnerungshilfe: \\(B\\) ist unsere Maschine (der Barbier), die unser spezielles Halteproblem entscheiden sollte. Und \\(H\\) die Maschine, die unser allgemeines Halteproblem entscheiden durfte.<\/p>\n<p style=\"padding-left: 30px;\">Wir definieren nun \\(f\\) mit<\/p>\n<p style=\"padding-left: 60px;\">\\(f(i)=(i,i)\\)<\/p>\n<p style=\"padding-left: 30px;\">Damit gilt auch:&nbsp;\\(B(i)=H(i,i)\\) und wir&nbsp;haben damit das spezielle Halteproblem auf das allgemeine reduziert.<\/p>\n<p>Nicht vergessen: die Reduktion ist transitiv, reflexiv aber nicht antisymmetrisch.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Die Reduktion ist ein m\u00e4chtiges Werkzeug um Probleme auf ein anderes zur\u00fcckzuf\u00fchren. Gibt es einen Algorithmus, der das Problem entscheidet, worauf reduziert wurde, so kann auch das reduzierte Problem entschieden werden.<\/p>\n<p>Aber nicht nur f\u00fcr die Berechenbarkeit hat es Auswirkungen, sondern auch auf die Eigenschaften der reduzierten Mengen und ihre Komplemente. &nbsp;Ist die Menge, auf die reduziert wurde rekursiv oder rekursiv-aufz\u00e4hlbar, so ist die reduzierte Menge ebenfalls rekursiv oder rekursiv-aufz\u00e4hlbar.<\/p>\n<p>War die Reduzierung der Mengen m\u00f6glich, so ist auch die Reduzierung ihrer Komplemente m\u00f6glich.<\/p>\n<h2>Lernziel 9<\/h2>\n<p style=\"padding-left: 30px;\"><em>Satz von Rice<\/em><\/p>\n<p>Kommen wir nun zu einem der wichtigsten S\u00e4tze der theoretischen Informatik, den <a href=\"http:\/\/de.wikipedia.org\/wiki\/Henry_Gordon_Rice\">Hr. Gordon Rice<\/a> im Jahre 1953 aussprach.<\/p>\n<p>Im Skript ist er formal definiert als:<\/p>\n<blockquote><p>F\u00fcr jede Menge \\(F\\subseteq P^{(1)}\\) &nbsp;mit \\(F\\neq\\emptyset\\) und \\(F\\neq P^{(1)}\\) ist die Menge \\(\\varphi^{-1}[F]\\) nicht rekursiv\/entscheidbar.<\/p><\/blockquote>\n<p>In der <a href=\"http:\/\/de.wikipedia.org\/wiki\/Satz_von_Rice\">Wikipedia<\/a> ist der Satz in einer anderen Form zu lesen.<\/p>\n<p>Zun\u00e4chst: was ist unser Wunsch? Wir w\u00fcrden gerne wissen, ob eine Funktion eine Eigenschaft hat oder nicht. Was w\u00e4re so eine Eigenschaft? Zum Beispiel:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Programm \\(P\\) berechnet die Identit\u00e4tsfunktion<\/li>\n<li>Die Ausgabe des Programms \\(P\\) ist maximal \\(n\\) Zeichen lang<\/li>\n<li>&#8230;<\/li>\n<\/ul>\n<p>Denkt euch einfach was nicht triviales (was nicht trivial genau bedeutet erkl\u00e4re ich auch gleich) aus.<\/p>\n<p>Es kann durchaus mehrere Programme (und damit auch mehrere Maschinen) geben, die Funktionen berechnen. Sagen wir einfach mal, wir betrachten<\/p>\n<p style=\"padding-left: 30px;\">\\(F:=\\{f\\in{P^{(1)}}\\mid{f(x)=x}\\}\\).<\/p>\n<p>Da die Identit\u00e4tsfunktion berechenbar ist, gibt es eine Programm, die sie berechnet. Sagen wie auch: Es ist das kleinste Programm \\(P_f\\), das sie berechnet.<\/p>\n<p>Nun konstruieren wir ein weiteres Programm \\(P_{f_2}\\), das zus\u00e4tzlich zum Programmcode von \\(P_f\\) noch eine sinnlose Schleife besitzt, die eine ungenutzte Variable bis \\(5\\) hochz\u00e4hlt. Offensichtlich berechnet auch \\(P_{f_2}\\) die Identit\u00e4tsfunktion. Programm \\(P_{f_2}\\) ist von \\(P_f\\) aber verschieden und beide haben auch verschiedene G\u00f6delnummern.<\/p>\n<p>Wir reden aber nicht explizit von Programmen, sondern von den Funktionen, die sie berechnen. Obwohl die Programme \\(P_{f}\\) und \\(P_{f_2}\\) verschieden sind, berechnen sie ein und die selbe Funktion: \\(f_P=f_{P_2}=Id\\). Damit erf\u00fcllen sie unsere &#8222;Eigenschaft&#8220; \\(F\\) und wir&nbsp;haben schon mindestens zwei Programme, bzw. ihre G\u00f6delnummern in unserer Menge<\/p>\n<p style=\"padding-left: 30px;\">\\(\\varphi^{-1}[F]\\) bzw.<\/p>\n<p style=\"padding-left: 30px;\">\\(\\{i\\mid{\\varphi_i\\in{F}}\\}\\)<\/p>\n<p>Was \\(\\varphi\\) ist, wisst Ihr noch? Im Beitrag zur <a title=\"TIA: Standardnummerierung und -Komplexit\u00e4t Phi und das Phi-Theorem (Lernziele KE5, 1\/3, Update)\" href=\"https:\/\/fernuni.digreb.net\/?p=991\">Standardnummerierung<\/a> hatten wir das bereits. Damit hatten wir alle Funktionen aus \\(P^{(1)}\\), der Menge der einstelligen, berechenbaren, evtl. partiellen Funktionen nummeriert. Die G\u00f6delnummern \\(i\\) und \\(i_2\\) von \\(P_{f}\\) und \\(P_{f_2}\\) befinden sich daher in dieser Menge&nbsp;\\(\\varphi^{-1}[F]\\). Und auch noch viele weitere G\u00f6delnummern von Programmen, die unsere Identit\u00e4tsfunktion \\(f(x)=x\\) berechnen.<\/p>\n<p style=\"padding-left: 30px;\">Das Problem ist: <em>diese Menge von G\u00f6delnummern, die die Eigenschaft \\(F\\) besitzt, ist nach dem Satz von Rice nicht entscheidbar!<\/em><\/p>\n<p>Das ist die Kernaussage des Satzes. Nach diesen Erl\u00e4uterungen k\u00f6nnen wir die Definition von oben St\u00fcck f\u00fcr St\u00fcck auseinander nehmen:<\/p>\n<blockquote><p>Sei \\(F\\) eine nicht leere (\\(F\\neq\\emptyset\\))&nbsp;echte Teilmenge (\\(F\\neq P^{(1)}\\) und gleichzeitig&nbsp;\\(F\\subseteq P^{(1)}\\))&nbsp;der Turing-berechenbaren, einstelligen Funktionen. Es ist nicht entscheidbar welche Funktionen, die durch das Programm \\(i\\) gegeben ist, die Eigenschaft \\(F\\) hat und welche nicht&nbsp;(\\(\\varphi^{-1}[F]\\) ist nicht rekursiv).<\/p><\/blockquote>\n<p>Diese beiden Eigenschaften der Menge&nbsp;\\(F=\\emptyset\\) (es ist die leere Menge) oder&nbsp;\\(F=P^{(1)}\\) (das ist die komplette Menge der berechenbare, einstelligen Funktionen) werden auch <strong>triviale<\/strong> Eigenschaften genannt. Es bedeutet, dass es min. ein Programm geben muss, die diese Funktion berechnet und eines, das sie nicht berechnet.<\/p>\n<p>Wann ist der Satz von Rice also anwendbar? Wenn es um die Eigenschaften von Funktionen (und nicht um die konkreten Maschinen selbst) geht und wenn die Menge der Programme, die diese Funktion berechnen nicht leer ist oder die Klasse der betrachteten Funktionen nicht komplett alle berechenbaren, einstelligen Funktionen umfasst.<\/p>\n<p><strong>Exkurs: Maschine\/Programm?!<\/strong><\/p>\n<p style=\"padding-left: 30px;\">Warum wird manchmal auch von den Eigenschaften von Turingmaschinen und nicht von Funktionen gesprochen? Erinnert Ihr euch noch an die <a title=\"TIA: Berechenbarkeit (Lernziele aus KE4, Update 5)\" href=\"https:\/\/fernuni.digreb.net\/?p=837\">Church&#8217;sche These<\/a>? Die Klasse der intuitiv berechenbaren Funktionen stimmt der der Klasse der Turing-berechenbaren Funktionen \u00fcberein.<\/p>\n<p style=\"padding-left: 30px;\">Damit k\u00f6nnen alle intuitiv berechenbaren Funktionen von Turingmaschinen berechnet werden und so die Eigenschaften von Funktionen auch die Eigenschaften der Turingmaschinen sein.<\/p>\n<p style=\"padding-left: 30px;\">Da die Programme, die eine Funktion aus \\(P^{(1)}\\) berechnen im Endeffekt also blo\u00df Turingmaschinen sind, die die Funktion aus \\(P^{(1)}\\) berechnen, sind die G\u00f6delnummern der Programme auch die G\u00f6delnummern der zugeh\u00f6rigen Bandmaschinen.<\/p>\n<p style=\"padding-left: 30px;\">Lasst euch also von den Worten Funktion, Programm, Maschine nicht verwirren \ud83d\ude09<\/p>\n<p>Noch nicht so recht greifbar, oder? Macht nichts. Versuchen wir es mit ein paar Negativbeispielen:<\/p>\n<p><strong>Negativbeispiele<\/strong><\/p>\n<p style=\"padding-left: 30px;\">\\(F_1=\\{i\\mid{M_i}\\text{ haelt bei der Eingabe von }x\\text{ in }5\\text{ Schritten }\\}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(F_2=\\{i\\mid{M_i}\\text{ hat 20 Zustaende}\\}\\)<\/p>\n<p style=\"padding-left: 30px;\">Diese Mengen \\(F_1\\) und \\(F_2\\) sind entscheidbar.<\/p>\n<p style=\"padding-left: 30px;\">In beiden F\u00e4llen ist der Satz von Rice nicht anwendbar, da sich die Aussage nicht auf die Funktionen, d.h. die Maschinenmenge, die sie berechnet, sondern auf die konkreten Eigenschaften einer Maschinen bezieht.<\/p>\n<p>Und nun ein paar Positivbeispiele:<\/p>\n<p><strong>Positivbeispiele<\/strong><\/p>\n<p style=\"padding-left: 30px;\">\\(F_3=\\{i\\mid{M_i}\\text{ haelt nur bei endlich vielen Eingaben}\\}\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(F_4=\\{i\\mid{M_i}\\text{ berechnet }0\\text{ bei Eingabe von }1\\}\\)<\/p>\n<p style=\"padding-left: 30px;\">Hier l\u00e4sst sich der Satz von Rice anwenden.<\/p>\n<ul style=\"list-style-type: square; padding-left: 60px;\">\n<li>Wir pr\u00fcfen Voraussetzungen \\(F\\subseteq{P^{(1)}}\\) und \\(F\\neq{P^{(1)}}\\):<\/li>\n<\/ul>\n<p style=\"padding-left: 60px;\">In \\(P^{(1)}\\) liegt z.B. \\(f(x)=x^2\\), damit gilt \\(F_3\\subseteq{P^{(1)}}\\)&nbsp;und \\(F_3\\neq{P^{(1)}}\\).<\/p>\n<ul style=\"list-style-type: square; padding-left: 60px;\">\n<li>Wir pr\u00fcfen Voraussetzung&nbsp;\\(F_3\\neq\\emptyset\\):<\/li>\n<\/ul>\n<p style=\"padding-left: 60px;\">Zudem gilt auch&nbsp;\\(F_3\\neq\\emptyset\\), denn&nbsp;es gibt min. eine Maschine, die nur bei endlich vielen Eingaben h\u00e4lt, z.B. \\(M(x)=1\\text{ falls } x&lt;5,\\text{ sonst }\\perp\\). Damit h\u00e4lt Maschine \\(M\\) nur f\u00fcr \\(x&lt;5\\).<\/p>\n<p style=\"padding-left: 30px;\">Die Menge \\(F_3\\) ist nach Rice somit nicht entscheidbar.<\/p>\n<p style=\"padding-left: 30px;\">F\u00fcr \\(F_4\\) gilt das ebenfalls. Die Pr\u00fcfung der Voraussetzungen geht analog zu \\(F_3\\). Auch diese Menge ist nach Rice nicht entscheidbar.<\/p>\n<p>Fazit: Wann k\u00f6nnen wir den Satz von Rice anwenden? Wenn mindestens eine Maschine (ein Programm) gibt, die die Funktionen aus der zu untersuchenden Menge \\(F\\) berechnet und es Maschinen (Programme) gibt, die die Funktionen aus \\(F\\) nicht berechnen.<\/p>\n<p>Genau das ist es, was uns vor Augen f\u00fchrt, dass das <strong>Halteproblem<\/strong> unentscheidbar ist.&nbsp;Es ist n\u00e4mlich eine nicht triviale Eigenschaft und wir k\u00f6nnen sie nach dem Satz von Rice nicht entscheiden. Damit ist die Menge&nbsp;\\(K_{\\varphi}^0\\) nicht rekursiv\/entscheidbar.<\/p>\n<p>Der Satz hat auch weitreichende Folgen im realen Leben. Denn er bedeutet z.B., dass es kein Verifikationswerkzeug in der Softwareentwicklung geben kann, welches <strong>alle<\/strong> Programme algorithmisch auf Korrektheit bzgl. ihrer Spezifikation pr\u00fcft. Es kann welche geben, die bestimmte, ggf. auch alle praktisch relevanten Programme testen k\u00f6nnen, aber alle? Das geht nach dem Satz von Rice eben nicht.<\/p>\n<p>Aber Achtung: f\u00fcr Teilmengen von \\(F\\) ist es evtl. m\u00f6glich, diese zu entscheiden. Daher auch das Beispiel mit der Verifikationssoftware: wir k\u00f6nnen nicht f\u00fcr jedes Programm entscheiden ob es der Spezifikation entspricht, aber evtl. durchaus f\u00fcr eine Teilmenge davon. Vielleicht ist das gerade die f\u00fcr uns relevante (praxisrelevante) Teilmenge.<\/p>\n<p>Auch wenn die soeben genannte Eigenschaft &#8222;<em>Das Programm arbeitet bzgl. seiner Spezifikation korrekt<\/em>&#8220; bereits praxistauglich ist, so gibt es eine weitere nicht triviale Eigenschaft von Programmen, mit der wir es tagt\u00e4glich zu tun haben: die Frage ob ein Programm eine sch\u00e4dliche Funktion hat oder nicht!<\/p>\n<p>Genau diese Fragestellung hat auch weitreichende Folgen f\u00fcr die Antiviren-Hersteller. Aus dem Satz von Rice l\u00e4sst sich schlie\u00dfen, dass es kein Antiviren-Programm geben kann, dass f\u00fcr alle Programme entscheiden kann ob sie sch\u00e4dlich sind oder nicht.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: &nbsp;Der Satz von Rice hat weitreichende Auswirkungen auf die Praxis.&nbsp;Er besagt, dass nicht triviale Aussagen \u00fcber eine von einer Turingmaschine berechnete Funktion (ein Programm) nicht entscheidbar sind.<\/p>\n<p>Diese nicht trivialen Aussagen sind Aussagen der Form \\(F\\neq{P^{(1)}}\\) und \\(F\\neq\\emptyset\\). Es muss also min. eine Maschine geben, die die Eigenschaft besitzt und min. eine, die sie nicht besitzt.<\/p>\n<p>Um den Satz anwenden zu k\u00f6nnen, muss man die zu \u00fcberpr\u00fcfende Eigenschaft auf diese Voraussetzungen zun\u00e4chst testen. Werden die Voraussetzungen bzg. der Nicht-Trivialit\u00e4t erf\u00fcllt und bezieht sich die Aussage auf eine Funktion und nicht auf die konkrete Maschine, so kann der Satz angewandt werden.<\/p>\n<p>Vielleicht nochmal in anderen Worten (diese habe ich aus irgendeiner Vorlesung, ich wei\u00df aber nicht mehr welcher):<\/p>\n<blockquote><p>Geben ist eine nicht-triviale Eigenschaft \\(F\\). Die Menge der Programme, die diese Eigenschaft erf\u00fcllen ist unentscheidbar.<\/p><\/blockquote>\n<p>Aber Achtung: f\u00fcr eine Teilmenge k\u00f6nnte die Eigenschaft durchaus entscheiden werden, jedoch eben nicht f\u00fcr alle!<\/p>\n<h2>Lernziel 7b<\/h2>\n<p style=\"padding-left: 30px;\"><em>\u00c4quivalenz- und&nbsp;Korrektheitsproblem<\/em><\/p>\n<p>Kommen wir nun zum \u00c4quivalenz- und Korrektheitsproblem. Das sind beides nicht triviale Eigenschaften von Programmen und damit nicht f\u00fcr alle entscheidbar.<\/p>\n<p>Aber zun\u00e4chst wieder die Definition, dann die Erkl\u00e4rung:<\/p>\n<blockquote><p>Es sei \\(d:\\subseteq \\mathbb{N} \\rightarrow \\mathbb{N}\\) definiert durch \\(d(i) = div\\) f\u00fcr alle \\(i \\in \\mathbb{N}\\)<\/p>\n<p>1. F\u00fcr jedes \\(f \\in P^{(1)}\\setminus \\{d\\}\\) sind die Mengen \\(M_f := \\{i\\mid\\varphi_i = f\\}\\) und \\(\\mathbb{N}\\setminus M_f = \\{i\\mid\\varphi_i \\neq f\\}\\) nicht rekursiv aufz\u00e4hlbar.<\/p>\n<p>2. Die Mengen \u00c4q \\(:= \\{(i,j)\\mid\\varphi_i = \\varphi_j\\}\\) und \\(\\mathbb{N}^2\\setminus\\) \u00c4q = \\(\\{(i,j)\\mid\\varphi_i \\neq \\varphi_j\\}\\) nicht rekursiv aufz\u00e4hlbar.<\/p><\/blockquote>\n<p>Als erstes haben wir eine Funktion \\(d\\), welche f\u00fcr jedes Argument divergent ist.<\/p>\n<p><strong>Punkt 1, Korrektheitsproblem<\/strong>: f\u00fcr jede Funktion \\(f\\) aus den einstelligen, evtl. partiellen, berechenbaren Funktionen \\(P^{(1)}\\) ohne die \u00fcberall undefinierten Funktionen \\(d\\), sind die Mengen \\(M_f\\), welche aus den G\u00f6delnummern der Programme\/Maschinen bestehen, welche die Funktion \\(f\\) berechnen und der Menge \\(\\mathbb{N}\\setminus M_f = \\{i\\mid\\varphi_i \\neq f\\}\\), der Menge aus den G\u00f6delnummern, welche die Funktion nicht berechnen nicht rekursiv aufz\u00e4hlbar.<\/p>\n<p>Diese Menge ist also nicht einmal semi-entscheidbar, d.h. wir haben keinen Algorithmus, der uns zu einem gegebenen \\(f\\) f\u00fcr alle \\(\\varphi_i\\) entscheidet ob&nbsp;\\(\\varphi_i\\) die Funktion \\(f\\) korrekt berechnet. Auch das Komplement davon, die Menge der Programme die die Funktion \\(f\\) nicht berechnen ist nicht semi-entscheidbar.<\/p>\n<p>In der Praxis w\u00fcrde man das Beispiel aus dem Skript bem\u00fchen, wo eine Korrektor ein Testprogramm &nbsp;entwerfen m\u00f6chte, welches entscheidet ob ein gegebenes Programm die Funktion \\(f\\) berechnet.<\/p>\n<p><strong>Punkt 2, \u00c4quivalenzproblem<\/strong>: Die Menge \u00c4q, welche aus Tupel \\((i,j)\\) der G\u00f6delnummern von Maschinen besteht, welche die gleiche Funktion berechnen (\\(\\varphi_i=\\varphi_j\\), sie sind \u00e4quivalent zueinander) und der Menge \\(\\mathbb{N}^2\\setminus\\)\u00c4q, die aus Tupeln besteht, welche nicht die gleiche Funktion berechnen sind nicht semi-entscheidbar\/rekursiv aufz\u00e4hlbar.<\/p>\n<p>Das \u00c4quivalenzproblem kann auf das Halteproblem zur\u00fcckgef\u00fchrt werden. Eine Maschine, die uns eine \\(1\\) ausgibt, wenn zwei Maschinen die gleiche Funktion berechnen, kann uns auch das Halteproblem l\u00f6sen. Da die Korrektheit und die \u00c4quivalenz eine nichttriviale Eigenschaft eines (oder mehrerer) Maschinen sind, gilt mit dem Satz von Rice (siehe oben), dass man beides nicht entscheiden kann (nur f\u00fcr regul\u00e4re Sprachen geht das, aber das wird sp\u00e4ter noch durchgekaut).<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Das Korrektheitsproblem besagt, dass die Menge der Programme, die eine Funktion berechnen nicht einmal semi-entscheidbar ist. Diese Feststellung gilt ebenfalls f\u00fcr die Menge der Programme, welche die gleiche Funktion berechnen (\u00c4quivalenzproblem).<\/p>\n<p>Man kann das Korrektheitsproblem auf das \u00c4quivalenzproblem durch \\(f(i)=(i,j)\\) reduzieren.<\/p>\n<h2>Lernziel 10<\/h2>\n<p style=\"padding-left: 30px;\"><em>G\u00f6del&#8217;scher Unvollst\u00e4ndigkeitssatz<\/em><\/p>\n<p>Der Unvollst\u00e4ndigkeitssatz von G\u00f6del besteht aus zwei Teilen (zitiert nach Wikipedia).<\/p>\n<blockquote><p>Der&nbsp;<strong><i>Erste Unvollst\u00e4ndigkeitssatz<\/i><\/strong>&nbsp;besagt, dass es in hinreichend starken widerspruchsfreien Systemen immer unbeweisbare Aussagen gibt.<\/p>\n<p>Der&nbsp;<strong><i>Zweite Unvollst\u00e4ndigkeitssatz<\/i><\/strong>&nbsp;besagt, dass hinreichend starke widerspruchsfreie Systeme ihre eigene Widerspruchsfreiheit nicht beweisen k\u00f6nnen<\/p><\/blockquote>\n<p>Der Teil ist im Skript wirklich gut beschrieben. Es ist einer der wichtigsten S\u00e4tze der Logik (Formulierung geklaut aus <a href=\"http:\/\/de.wikipedia.org\/wiki\/Unvollst%C3%A4ndigkeitssatz\">Wikipedia<\/a>). Daher w\u00fcrde diesem Lernziel gerne einen <a title=\"Peano und G\u00f6del\" href=\"https:\/\/fernuni.digreb.net\/?p=1178\">eigenen Beitrag<\/a> widmen.<\/p>\n<p>Also: bitte dort lesen und dann hierher zur\u00fcck um den Beitrag mit der Antwort zum letzten Lernziel von Kurseinheit 6 abzuschlie\u00dfen \ud83d\ude09<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Mit dem Unvollst\u00e4ndigkeitssatz kann man sagen, dass nicht jeder mathematische Satz aus den Axiomen formal abgeleitet oder widerlegt werden kann. Kurz gesagt:<\/p>\n<p style=\"padding-left: 30px;\"><em>Jedes hinreichend m\u00e4chtige formale System ist entweder&nbsp;widerspr\u00fcchlich oder unvollst\u00e4ndig.<\/em><\/p>\n<p>Durch ein Paradoxon k\u00f6nnen selbst in so einfachen Systemen, wie z.B. Peano, Widerspr\u00fcche konstruiert und bewiesen werden, so dass es unvollst\u00e4ndig bzw. widerspr\u00fcchlich ist.<\/p>\n<p>Wir haben im Endeffekt also entweder ein widerspr\u00fcchliches oder ein unvollst\u00e4ndiges System (mit letzterem k\u00f6nnen wir jedoch besser leben).<\/p>\n<p><span style=\"font-size: 13px;\">Und damit haben wie die Kurseinheit 6 auch schon durch. Wer Fehler findet, sofort melden bevor sie sich in den K\u00f6pfen einnisten \ud83d\ude09<\/span><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: mir sind einige Schnitzer beim Halteproblem aufgefallen, die ich mittlerweile ausger\u00e4umt haben sollte. Hoffe ich. Auch habe ich den Beitrag um den Beweis zum Bild- und Projektionssatz erweitert (der nun in einem eigenen Beitrag steht), was ihn leider um ein paar Seiten verl\u00e4ngert hat. Es gibt insg. drei vier Beitr\u00e4ge zur KE6. TIA: Rekursive &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=1382\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: Berechenbarkeit auf anderen Mengen (Lernziele KE7, 2\/2)\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-1382","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\/1382","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=1382"}],"version-history":[{"count":48,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1382\/revisions"}],"predecessor-version":[{"id":3524,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/1382\/revisions\/3524"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1382"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1382"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1382"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}