{"id":2313,"date":"2012-12-09T09:52:24","date_gmt":"2012-12-09T07:52:24","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=2313"},"modified":"2025-11-25T22:49:04","modified_gmt":"2025-11-25T21:49:04","slug":"tia-rekursive-und-rekursiv-aufzahlbare-mengen-lernziele-ke6-13","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=2313","title":{"rendered":"TIA: Rekursive und rekursiv-aufz\u00e4hlbare Mengen (Lernziele KE6, 1\/4) (Update)"},"content":{"rendered":"<p><strong>Update<\/strong>: Index-Fehler zu \\(I_1\\) (Danke, Martin!)<\/p>\n<p><strong>Update<\/strong>: auch hier habe mich mich noch strikter an die Lernziele gehalten. Zus\u00e4tzlich dazu wurden noch ein paar Beispiele zu entscheidbaren und semi-entscheidbaren Funktionen eingepflegt um das Verst\u00e4ndnis zu erleichtern, was mir hoffentlich gelungen ist \ud83d\ude09<\/p>\n<p><strong>Update 2<\/strong>: ich merke gerade, dass die Eintr\u00e4ge zu lang sind. Selbst die Ladezeiten vom Chrome sind bei den Mathe-Symbolen f\u00fcr 10 Seiten exorbitant hoch. Ich habe daher beschlossen die Beitr\u00e4ge daher zu trennen.<\/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>Da die Lernziele im Skript etwas verstreut sind, kann es sein, dass ich etwas springen muss und nicht alles der Reihe nach abhake. Lasst euch davon nicht verwirren.<\/p>\n<p>Dieser Eintrag befasst sich mit rekursiven und rekursiv-aufz\u00e4hlbaren Mengen und ihren Eigenschaften. Wir hatten bereits in den anderen Beitr\u00e4gen viel mit Mengen zu tun. Ich werde die Erkl\u00e4rungen hier einfach Copy&amp;Pasten, falls sie passen.<\/p>\n<h2>Lernziel 1 und 3<\/h2>\n<p style=\"padding-left: 30px;\"><em>Definition rekursiver und rekursiv aufz\u00e4hlbarer Mengen von Zahlen und W\u00f6rtern<\/em><\/p>\n<p>Zun\u00e4chst einmal hilft es sich wie Bart bei den Simpsons 100x &#8222;Rekursiv = entscheidbar. Rekursiv aufz\u00e4hlbar = Semi entscheidbar&#8220; wahlweise in das Parkett zu kratzen, die Wand zu tapezieren oder sich auf die Stirn t\u00e4towieren zu lassen. Nachdem das erledigt ist, wiederholt man das Gleiche dann noch mit der Definition (welche ich aus diesem <a title=\"TI: Entscheidbarkeit und charakteristische Funktion\" href=\"https:\/\/fernuni.digreb.net\/?p=909\">Beitrag zur Entscheidbarkeit<\/a> einfach Copy&amp;Paste):<\/p>\n<blockquote><p>Eine Menge \\( T \\subseteq M\\) ist\u00a0<strong>entscheidbar\/rekursiv<\/strong>\u00a0wenn die charakteristische Funktion \\(\\chi_T: M \\rightarrow \\{0,1\\}\\) definiert durch<\/p>\n\\(\\chi_T(t)=\\begin{cases} 1, &amp; \\mbox{ falls } t \\in T \\\\ 0, &amp; \\mbox{ sonst}\\end{cases}\\)\n<p>berechenbar ist (Achtung: sie muss <strong>berechenbar<\/strong> sein und nicht einfach nur existieren!).<\/p><\/blockquote>\n<p>Achtung: die charakteristische Funktion existiert immer und ist im Falle der Entscheidbarkeit auch immer total!<\/p>\n<p>Dann nochmal f\u00fcr r.a.:<\/p>\n<blockquote><p>Eine Menge \\(T\\) ist\u00a0<strong>semi-entscheidbar\/rekursiv<\/strong><strong>\u00a0aufz\u00e4hlbar<\/strong>\u00a0wenn die partielle charakteristische Funktion \\(\\chi^{&#8218;}_T: M \\rightarrow \\{1\\}\\) definiert durch<\/p>\n\\(\\chi^{&#8218;}_T(t)=\\begin{cases} 1, &amp; \\mbox{ falls } t \\in T \\\\ \\perp, &amp; \\mbox{ sonst}\\end{cases}\\)\n<p>berechenbar ist.<\/p><\/blockquote>\n<p>Achtung: hier existiert die charakteristische Funktion ebenfalls, sie ist aber nicht mehr total!<\/p>\n<p>Manchmal sagt man auch, dass die &#8222;halbe&#8220; charakteristische Funktion berechenbar ist. Oder wie im Skript ausgedr\u00fcckt:<\/p>\n<blockquote><p>Eine Menge \\(T\\subseteq\\mathbb{N}^k\\) ist\u00a0<strong>semi-entscheidbar\/rekursiv<\/strong><strong>\u00a0aufz\u00e4hlbar<\/strong>\u00a0wenn es eine partielle berechenbare Funktion \\(f:\\subseteq\\mathbb{N}^k\\rightarrow\\mathbb{N}\\) gibt mit \\(T=Def(f)\\).<\/p><\/blockquote>\n<p>W\u00e4hrend sich die Definition f\u00fcr r.a. Mengen \u00fcber die charakteristische Funktion noch erschlie\u00dfen mag, ist es bei dieser hier ein bisschen abstrakter.<\/p>\n<p>Denkt euch eine Menge \\(T\\), wo Ihr nur entscheiden k\u00f6nnt ob ein Element zu dieser Menge geh\u00f6rt, aber nicht ob es nicht dazu geh\u00f6rt (sie ist also offensichtlich nur semi-entscheidbar). Und nun lasst Ihr die charakteristische Funktion \\(f\\) aus der 2. Definition auf jedem Element \\(x\\) dieser Menge \\(A\\) laufen.<\/p>\n<p>Geh\u00f6rt das Element \\(x\\) zu dieser Menge \\(T\\), so ist die Ausgabe der Funktion \\(f(x)=1\\). Und das f\u00fcr jedes \\(x\\in{A}\\), dass zur Menge \\(T\\) geh\u00f6rt. Geh\u00f6rt es nicht zur Menge \\(T\\), so rechnet die Funktion unendlich lange weiter. Damit sind alle positiv entschiedenen Elemente \\(x\\in A\\) in der Menge \\(T\\) und ganz \\(T\\) damit der Definitionsbereich der Funktion \\(f\\), eben \\(T=Def(f)\\).<\/p>\n<p>Wenn wir also entscheiden k\u00f6nnen ob ein Element in einer Menge ist oder nicht, ist die Menge rekursiv (z.B. bei der Entscheidung auf Primzahlen). K\u00f6nnen wir nur positive (oder nur negative, aber nie beides) Entscheidungen treffen ob sich das Element in der Menge befindet (z.B. bei dem Halteproblem), dann ist die Menge nur rekursiv aufz\u00e4hlbar. Nicht vergessen: eine rekursive Menge ist auch rekursiv aufz\u00e4hlbar, aber eine rekursiv aufz\u00e4hlbare Menge nicht zwingend rekursiv.<\/p>\n<p>Sp\u00e4ter kommen wir noch zu ein paar Beispielen f\u00fcr diese Mengen.<\/p>\n<p>Eine weitere, wichtige Eigenschaft f\u00fcr rekursive Funktionen ist die folgende:<\/p>\n<blockquote><p>Eine unendliche Menge \\(A\\subseteq\\mathbb{N}\\) ist rekursiv, gwd. es eine <strong>wachsende, totale Funktion<\/strong> \\(f\\) gibt mit \\(A = Bild(f)\\). Wachsend bedeutet: \\(f(n) &lt; f(n+1)\\)<\/p><\/blockquote>\n<p>H\u00f6re ich euch die Augenbrauen zusammenziehen? M\u00fcsst Ihr nicht. Es ist nicht schwer: was eine wachsende Funktion ist, wisst Ihr sicherlich: es ist eine Funktion, dessen Funktionswert bei der Eingabe vom Parameter \\(n\\) stets kleiner ist als bei der Eingabe von \\(n+1\\).<\/p>\n<p><strong>Beispiel<\/strong>: \\(f(n)=n^2\\)<\/p>\n<p style=\"padding-left: 30px;\">Stellen wir f\u00fcr \\(1\\leq{n}\\leq{5}\\) mal die Funktionswerte zusammen:<\/p>\n<p style=\"padding-left: 30px;\">\\(f(1)=1,f(2)=4,f,(3)=9,f(4)=16,f(5)=25\\)<\/p>\n<p style=\"padding-left: 30px;\">Kein Funktionswert von \\(f(n+1)\\) ist kleiner als \\(f(n)\\). Damit ist sie wachsend.<\/p>\n<p>Schaffen wir es also so eine Funktion \\(f\\) anzugeben, wo die Ausgabe (sog. Bildmenge) von \\(f\\) unsere komplette Menge \\(A\\) ist, so ist die Menge \\(A\\) entscheidbar\/rekursiv.<\/p>\n<p><strong>Exkurs Nr. 2<\/strong>: weiterhin sind alle endlichen Mengen rekursiv\/entscheidbar. Warum? Nehmen wir einfach eine beliebige, endliche Menge \\(A\\subseteq\\mathbb{N}\\). Egal welche Eigenschaften wir dieser Menge zuordnen, so k\u00f6nnen wir (theoretisch) einfach eine riesige charakteristische Funktion angeben, die f\u00fcr jedes Element entscheidet ob es zu \\(A\\) geh\u00f6rt oder nicht. Denn die Menge ist endlich.<\/p>\n<p>Nun solltet Ihr einen kleinen Eindruck davon bekommen haben was entscheidbar\/rekursiv und was semi-entscheidbar\/rekursiv-aufz\u00e4hlbar ist.<\/p>\n<p><strong>Exkurs Nr. 3<\/strong>: Zusammenhang zu W\u00f6rtern<\/p>\n<p>Der Zusammenhang zwischen Zahlen und W\u00f6rtern sollte nach der\u00a0<a title=\"TI: Berechenbarkeit (Lernziele aus KE4, Update II)\" href=\"https:\/\/fernuni.digreb.net\/?p=837\">Standardnummerierung<\/a>\u00a0\\(\\sigma\\) der W\u00f6rter \u00fcber \\(\\Sigma^*\\) sollte euch bereits klar sein. Denn alles, was wir \u00fcber Mengen auf \\(\\mathbb{N}^k\\) oder \\(\\mathbb{N}\\)\u00a0aufz\u00e4hlen, gilt selbstverst\u00e4ndlich auch f\u00fcr Mengen \u00fcber einem Alphabet\u00a0\\(\\Sigma^{*}\\).<\/p>\n<p>Mittels Standardnummerierung k\u00f6nnen wir Worte aus einem Alphabet \\(\\Sigma\\) nummerieren und umgekehrt. Das haben wir im\u00a0<a title=\"TI: Berechenbarkeit (Lernziele aus KE4, Update II)\" href=\"https:\/\/fernuni.digreb.net\/?p=837\">Beitrag<\/a>\u00a0\u00fcber \\(\\nu_\\Sigma\\) bereits erfolgreich getan.<\/p>\n<p>Ebenfalls konnten wir Bandprogramme \\(BP\\) erfolgreich mit \\(\\nu_P\\) nummerieren und entscheiden ob ein Wort \u00fcber dem &#8222;Programmiersprachenalphabet&#8220; \\(\\Omega^{*}\\) ein Bandprogramm ist oder nicht. Damit ist die Menge der Bandprogramme \\(BP\\), der PASCAL-Programme und die Menge der \\(WHILE\\)-Programme entscheidbar\/rekursiv.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Antwort zum Lernzie<\/strong>l: eine Menge ist rekursiv\/entscheidbar wenn ihre (volle) charakteristische Funktion berechenbar ist. F\u00fcr eine nur semi-entscheidbare\/rekursiv-aufz\u00e4hlbare Menge muss nur die &#8222;halbe&#8220; charakteristische Funktion berechenbar sein.<\/p>\n<p>Im ersten Fall k\u00f6nnen wir damit die vollst\u00e4ndige Menge \\(A\\) entscheiden, d.h. ob ein Element zu dieser geh\u00f6rt oder nicht (formal ausgedr\u00fcckt: \\(x\\in{A}\\) <strong>und<\/strong> \\(x\\notin{A}\\)). Im letzten Fall k\u00f6nnen wir nur positiv oder negativ entscheiden, aber nie beides gleichzeitig (formal ausgedr\u00fcckt: \\(x\\in{A}\\)\u00a0<strong>oder<\/strong>\u00a0\\(x\\notin{A}\\), aber nicht beides gleichzeitig).<\/p>\n<p>Eine Art Ausnahme bildet das Komplement einer semi-entscheidbaren Menge: k\u00f6nnen wir dieses ebenfalls semi-entscheiden, so ist die komplette Menge entscheidbar. Denn damit haben wir im Endeffekt die positive und negative Antwort, d.h. die &#8222;volle&#8220; charakteristische Funktion berechnet.<\/p>\n<h2>Lernziel 4<\/h2>\n<p style=\"padding-left: 30px;\"><em>Abschlusseigenschaften rekursiver und rekursiv aufz\u00e4hlbarer Mengen<\/em><\/p>\n<p>Im Skript werden die folgenden, abschlie\u00dfenden Eigenschaften von <strong>rekursiven\/entscheidbaren<\/strong> Mengen genannt:<\/p>\n<blockquote><p>1. \\(A_1, A_2 \\subseteq \\mathbb{N}^k\\) rekursiv. Damit ist auch \\(\\mathbb{N}^k\\setminus A_1, A_1 \\cup A_2\\) und \\(A_1 \\cap A_2\\) rekursiv.<\/p>\n<p>2. Sei \\(A \\subseteq \\mathbb{N}\\) rekursiv, sei \\(f \\in R^{(1)}\\). Dann ist \\(f^{-1}[A]\\) rekursiv.<\/p>\n<p>3. Sei \\(A \\subseteq \\mathbb{N}^k\\), dann gilt: \\(A\\) rekursiv \\(\\Longleftrightarrow \\pi^{(k)}[A]\\) rekursiv.<\/p><\/blockquote>\n<p>Die 1. Eigenschaft ist soweit deutlich: \\(A_1\\) und \\(A_2\\) sind Teilmengen aus \\(\\mathbb{N}^k\\) mit eben der Stelligkeit \\(k\\). Restmenge, Vereinigungsmenge und\u00a0Schnittmenge sind damit auch rekursiv.<\/p>\n<p>Eigenschaft Nr. 2 ist etwas aufw\u00e4ndiger wenn Ihr mit der Schreibweise nicht vertraut seid und (wie ich) Abschnitt 1.3 \u00fcberlesen habt. Daher hier zur Auffrischung nochmal. Einer Korrespondenz wird eine Funktion \\(f\\) zugeordnet, die Mengen transformiert.\u00a0Die Umkehrfunktion davon\u00a0\\(f^{-1}[A]\\). Wenn die Menge \\(A\\) nun rekursiv ist und es eine totale Funktion \\(f\\) gibt, so ist auch die Umkehrfunktion rekursiv.<\/p>\n<p>Durch die <a title=\"TI: Cantorsche Tupelfunktion\" href=\"https:\/\/fernuni.digreb.net\/?p=580\">Cantorfunktion<\/a> aus Eigenschaft Nr. 3 k\u00f6nnen wir uns bei unseren Untersuchungen auf die rekursiven Teilmengen von \\(\\mathbb{N}\\) beschr\u00e4nken. Wir erinnern uns: wie k\u00f6nnen mit dieser Funktion \\(\\pi\\) beliebige \\(k\\)-stellige Tupel auf eine nat\u00fcrliche Zahl aus \\(\\mathbb{N}\\) abbilden. Wer sich nicht dran erinnert, sollte sich nochmal den Beitrag zu Gem\u00fcte f\u00fchren.<\/p>\n<p>Wir haben damit sichergestellt, dass Operatoren die rekursiven Mengen auch wieder in rekursive Mengen transformieren.<\/p>\n<p>Anschlie\u00dfend folgen die Abschlusseigenschaften der <strong>rekursiv aufz\u00e4hlbaren\/semi-entscheidbaren<\/strong>\u00a0(r.a.) Mengen:<\/p>\n<blockquote><p>1. \\(A_1, A_2 \\subseteq \\mathbb{N}^k\\) r.a. Damit ist auch \\(A_1\\cup A_2\\) und \\(A_1 \\cap A_2\\) r.a.<\/p>\n<p>2. Sei \\(A \\subseteq \\mathbb{N}\\) r.a., sei \\(f \\in P^{(k)}\\). Dann ist \\(f^{-1}[A]\\) r.a.<\/p>\n<p>3. Sei \\(A \\subseteq \\mathbb{N}^k\\), dann gilt: \\(A\\) r.a. \\(\\Longleftrightarrow \\pi^{(k)}[A]\\) r.a.<\/p><\/blockquote>\n<p>Die Erl\u00e4uterung erfolgt analog zu rekursiven Mengen. Bitte aber beachten, dass wir nun auf den partiellen, mehrstelligen, berechenbaren Funktionen \\(P^{(k)}\\) arbeiten und nicht mehr auf den totalen \\(R^{k}\\).<\/p>\n<p>Zusammenfassend zitiere ich aus der <a href=\"http:\/\/de.wikipedia.org\/wiki\/Rekursiv_aufz%C3%A4hlbare_Menge\">Wikipedia<\/a> f\u00fcr die rekursiven\/entscheidbaren und rekursiv-aufz\u00e4hlbare\/semi-entscheidbare Mengen:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Jede\u00a0<a title=\"Entscheidbare Menge\" href=\"http:\/\/de.wikipedia.org\/wiki\/Entscheidbare_Menge\">entscheidbare Menge<\/a>\u00a0ist rekursiv aufz\u00e4hlbar, aber es gibt rekursiv aufz\u00e4hlbare Mengen, die nicht entscheidbar sind.<\/li>\n<li>Eine Menge ist genau dann\u00a0<a title=\"Entscheidbare Menge\" href=\"http:\/\/de.wikipedia.org\/wiki\/Entscheidbare_Menge\">entscheidbar<\/a>, wenn sie und ihr\u00a0<a title=\"Komplement (Mengenlehre)\" href=\"http:\/\/de.wikipedia.org\/wiki\/Komplement_(Mengenlehre)\">Komplement<\/a>\u00a0rekursiv aufz\u00e4hlbar sind.<\/li>\n<li>Jede endliche Menge ist rekursiv aufz\u00e4hlbar.<\/li>\n<li>Jede rekursiv aufz\u00e4hlbare Menge ist\u00a0<a title=\"Abz\u00e4hlbar\" href=\"http:\/\/de.wikipedia.org\/wiki\/Abz%C3%A4hlbar\">abz\u00e4hlbar<\/a>, aber nicht alle abz\u00e4hlbaren Mengen sind rekursiv aufz\u00e4hlbar.<\/li>\n<li>Jede unendliche rekursiv aufz\u00e4hlbare Menge besitzt Teilmengen, die nicht rekursiv aufz\u00e4hlbar sind.<\/li>\n<li>Der Schnitt von endlich vielen rekursiv aufz\u00e4hlbaren Mengen ist rekursiv aufz\u00e4hlbar; die Vereinigung einer rekursiv aufz\u00e4hlbaren Menge von rekursiv aufz\u00e4hlbaren Mengen ist rekursiv aufz\u00e4hlbar. Es gibt rekursiv aufz\u00e4hlbaren Mengen, deren Komplement nicht rekursiv aufz\u00e4hlbar ist.<\/li>\n<\/ul>\n<p><strong>Antwort zum Lernziel<\/strong>: die entscheidbaren Mengen sind abgeschlossen bzgl. Komplement, Schnitt und Vereinigung. Die semi-entscheidbaren mengen jedoch nur bzgl. Schnitt und Vereinigung, das Komplement ist nicht semi-entscheidbar (w\u00e4re es das, so w\u00e4re die Menge vollst\u00e4ndig entscheidbar. Siehe vorheriges Lernziel).<\/p>\n<h2>Lernziel 2a<\/h2>\n<p style=\"padding-left: 30px;\"><em>Nachweis der Rekursivit\u00e4t\/Entscheidbarkeit von Mengen<\/em><\/p>\n<p>Was tun wir um die Rekursivit\u00e4t von Mengen zu beweisen? Wir geben ein Flussdiagramm einer verallgemeinerten Registermaschine an, welches die charakteristische Funktion f\u00fcr die zu untersuchende Menge berechnet. Wir entscheiden nun wirklich ob ein Element in der rekursiven Menge ist oder nicht. Dazu verwenden wir alle bereits als berechenbar bewiesenen Funktionen. Mehr nicht.<\/p>\n<p>Hilfreich ist hierf\u00fcr die Auflistung der berechenbaren Funktionen aus Satz 3.2.5:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>Nullfunktion<\/li>\n<li>Nachfolger- und Vorg\u00e4ngerfunktion<\/li>\n<li>Projektion<\/li>\n<li>konstante Funktion<\/li>\n<li>Summe<\/li>\n<li>arithmetische Differenz<\/li>\n<li>Produkt<\/li>\n<li>Quotient und Rest<\/li>\n<li>Exponentation<\/li>\n<li>Wurzel<\/li>\n<li>max\/min<\/li>\n<li>Primzahltest und \\(x\\)-te Primzahl<\/li>\n<\/ul>\n<p>K\u00f6nnt ihr alle f\u00fcr euer Flussdiagramm benutzen \ud83d\ude09<\/p>\n<p><strong>Beispiel<\/strong>? Sicher: \\(T=\\{x\\in\\mathbb{N}\\mid x\\text{ ist Primzahl}\\}\\)<\/p>\n<p style=\"padding-left: 30px;\">Die dazu notwendige, charakteristische Funktion ist:<\/p>\n<p style=\"padding-left: 30px;\">\\(\\chi_T(x)=\\begin{cases} 1, &amp; \\mbox{ falls } x\\text{ Primzahl} \\\\ 0, &amp; \\mbox{ sonst}\\end{cases}\\)<\/p>\n<p style=\"padding-left: 30px;\">Test auf Primzahl: F\u00fcr alle \\(y\\) mit \\(1&lt;y&lt;x\\) wird getestet ob es bei der Division von \\(x\\) durch \\(y\\) einen Rest gibt. Gibt es bei einem \\(y\\) keinen Rest, so ist es keine Primzahl (dann ist \\(y\\) n\u00e4mlich ein legitimer Teiler von \\(x\\)).<\/p>\n<p style=\"padding-left: 30px;\">Damit k\u00f6nnen wir f\u00fcr jedes \\(x\\in\\mathbb{N}\\) entscheiden ob es eine Primzahl ist oder nicht. Das Flussdiagramm f\u00fcr den Test d\u00fcrft Ihr selbst angeben \ud83d\ude09<\/p>\n<p>Ein weiteres Beispiel w\u00e4re z.B. der Test auf die <a href=\"http:\/\/de.wikipedia.org\/wiki\/Goldbachsche_Vermutung\">Goldbach-Eigenschaft<\/a> einer Zahl.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: um zu zeigen, dass eine Menge entscheidbar\/rekursiv ist, muss die (volle) charakteristische Funktion berechenbar sein.<\/p>\n<p>Dazu gibt man das Flussdiagramm einer verallgemeinerten Maschine (wenn man streng ist, muss man f\u00fcr jeden verallgemeinerten Test seine Berechenbarkeit ebenfalls nachweisen und letztendlich seine Maschine auf die drei Grundoperationen Addition\/Subtraktion von \\(1\\) und Test auf \\(0\\) zur\u00fcckf\u00fchren) an, die diese berechnet und in jedem Fall mit einem Ergebnis h\u00e4lt.<\/p>\n<h2>Lernziel 2b<\/h2>\n<p style=\"padding-left: 30px;\"><em>Nachweis der rekursiven Aufz\u00e4hlbarkeit\/Semi-entscheidbarkeit von Mengen<\/em><\/p>\n<p>Auch hier ist es nicht allzu schwierig. Jede rekursiv aufz\u00e4hlbare (semi entscheidbare) Menge\u00a0ist auch gleichzeitig aufz\u00e4hlbar und jede aufz\u00e4hlbare Menge ist auch rekursiv aufz\u00e4hlbar (semi entscheidbar). Daher m\u00fcssen wir es nur schaffen, die Elemente der Menge irgendwie \u00a0aufzuz\u00e4hlen. Man macht sich leicht klar, dass der Definitionsbereich und Wertebereich von berechenbaren Funktionen rekursiv aufz\u00e4hlbar ist.<\/p>\n<p>Aber was ist mit \\(n\\)-Tupeln? Die sind dank\u00a0<a title=\"TI: Cantorsche Tupelfunktion\" href=\"https:\/\/fernuni.digreb.net\/?p=580\">Cantor&#8217;schen Tupelfunktion<\/a>\u00a0auf ein Element reduzierbar, d.h. wir k\u00f6nnen \\(n\\)-Tupel auf einelementige Mengen reduzieren und unseren Schabernack mit ihnen treiben.<\/p>\n<p>Wird also gefragt, ob eine Menge rekursiv aufz\u00e4hlbar ist, so geben wir einfach eine charakteristische Funktion an, die die Eigenschaft der Menge nur positiv (oder nur negativ) beantwortet. F\u00fcr die gegens\u00e4tzliche Antwort muss unsere charakteristische Funktion (im Gegensatz zur vollen charakteristischen Funktion f\u00fcr entscheidbare Mengen) nicht halten, Hauptsache sie sagt uns zuverl\u00e4ssig eine der beiden Antworten. Ein gutes Beispiel ist das Post&#8217;sche Korrespondenzproblem.<\/p>\n<p><strong>Beispiel<\/strong>: <strong>Post&#8217;sches Korrespondenzproblem<\/strong><\/p>\n<p style=\"padding-left: 30px;\">Das\u00a0<strong>Post&#8217;sche Korrespondenzproblem<\/strong>\u00a0beschreibt das Problem bei Wortpaaren \\((x_1,y_1),&#8230;,(x_n,y_n)\\) eine Folge \\(i_1,&#8230;,i_k\\) mit der Eigenschaft: \\(x_{i_1}x_{i_2}&#8230;x_{i_k} = y_{i_1}y_{i_2}&#8230;y_{i_k}\\) zu finden. Ist nat\u00fcrlich wieder etwas abstrakt, aber probieren wir das mal an einem Beispielproblem:<\/p>\n<p style=\"padding-left: 30px;\"><strong>Beispielproblem<\/strong>\u00a0\\(P=((01,1),(0,000),(01000,01))\\)<\/p>\n<p style=\"padding-left: 30px;\">\\(P\\) nennt man Problemfall oder Instanz.<\/p>\n<p style=\"padding-left: 30px;\"><strong>Fragestellung<\/strong>: gibt es eine L\u00f6sung (d.h. eine Folge von Indices) \\(I\\) zum Problemfall \\(P\\)? Wenn ja, ist die Folge eine L\u00f6sung von \\(P\\).<\/p>\n<p style=\"padding-left: 30px;\">Wir m\u00fcssen hier also eine Kombination von zwei Wortkombinationen \\(\\omega_1 = \\omega_2\\) finden und die folgenden Regeln einhalten:<\/p>\n<ul style=\"list-style-type: square; padding-left: 30px;\">\n<li>\\(\\omega_1\\) darf nur aus den 1. Elementen der 3 Wortpaare bestehen: \\(01,0\\) und \\(01000\\).<\/li>\n<li>Das Wort\u00a0\\(\\omega_2\\) darf nur aus den 2. Elementen der 3 Wortpaare bestehen: \\(1,000\\) und \\(01\\).<\/li>\n<li>Die Wortkombinationen\u00a0\\(\\omega_1\\) und \\(\\omega_2\\) d\u00fcrfen beliebig lang sein.<\/li>\n<\/ul>\n<p style=\"padding-left: 30px;\">Was Indices sind, ist euch klar? Nein, keine Sorge. Kommt gleich.\u00a0Es liegt also an unserer Kombinationsgabe eine passende Index-Kombination zu finden, so dass am Ende gilt: \\(\\omega_1=\\omega_2\\).<\/p>\n<p style=\"padding-left: 30px;\">Eine m\u00f6gliche L\u00f6sung w\u00e4re \\(\\omega_1 = 01000\\mid{0}\\mid{0}\\mid{01}\\) und\u00a0\\(\\omega_2=01\\mid{000}\\mid{000}\\mid{1}\\). (die \\(\\mid\\) sind nur optische Trennzeichen damit Ihr die Elemente identifizieren k\u00f6nnt aus denen die Worte bestehen).<\/p>\n<p style=\"padding-left: 30px;\">Die zugeh\u00f6rigen Indices w\u00e4ren: \\(I_1=(3,2,2,1)\\). Damit ist \\(I_1\\) eine L\u00f6sung f\u00fcr \\(P\\) und \\(P\\) damit gel\u00f6st.<\/p>\n<p style=\"padding-left: 30px;\">Die Indices sind nichts weiter als die Nummer des Tupels, dass zur Bildung herangezogen wird. Da wir f\u00fcr das erste Wort \\(\\omega_1\\) nur die ersten und f\u00fcr das zweite Wort \\(\\omega_2\\) nur die zweiten Elemente aus den Tupeln benutzen d\u00fcrfen, reicht uns als Angabe einfach nur die Nummer des Tupels.<\/p>\n<p style=\"padding-left: 30px;\">W\u00fcrden wir z.B. die folgende L\u00f6sung austesten wollen: \\(I_2=(2,3,1,1)\\), so w\u00e4ren die Worte \\(\\omega_1\\) und \\(\\omega_2\\):<\/p>\n<p style=\"padding-left: 60px;\">\\(\\omega_1=0\\mid{01000}\\mid{01}\\mid{01}\\) und<\/p>\n<p style=\"padding-left: 60px;\">\\(\\omega_2=000\\mid{01}\\mid{1}\\mid{1}\\)<\/p>\n<p style=\"padding-left: 30px;\">Da \\(\\omega_1\\neq\\omega_2\\), ist die m\u00f6gliche L\u00f6sung \\(I_2\\) falsch und \\(P\\) noch nicht gel\u00f6st. Aber was nicht ist, kann ja noch werden!<\/p>\n<p style=\"padding-left: 30px;\">Um zu zeigen, dass die Menge dieser Worttupel rekursiv aufz\u00e4hlbar\/semi entscheidbar ist brauchen wir nur zu zeigen, dass die Menge der Definitionsbereich einer partiellen Funktion ist und die dazugeh\u00f6rige Maschine anzugeben, welche die charakteristische Funktion f\u00fcr diese Menge berechnet und in jedem Fall mit einer \\(1\\) terminiert wenn das Element in der Menge ist oder nicht terminiert, wenn es das nicht ist.<\/p>\n<p style=\"padding-left: 30px;\">Die charakteristische Funktion f\u00fcr dieses Problem w\u00e4re:<\/p>\n<p style=\"padding-left: 30px;\">\\(\\chi^{&#8218;}_P(I)=\\begin{cases} 1, &amp; \\mbox{ falls }\\omega_1=\\omega_2 \\\\ \\perp, &amp; \\mbox{ sonst}\\end{cases}\\)<\/p>\n<p style=\"padding-left: 30px;\">Das Flussdiagramm beschreibe ich hier ebenfalls am besten in Pseudocode:<\/p>\n<ol style=\"padding-left: 30px;\">\n<li>Setze \\(n=1\\)<\/li>\n<li>Fange mit einer Indexfolge \\(I\\) der L\u00e4nge \\(n\\) an<\/li>\n<li>Erstelle durch den Index \\(I\\) die Worte \\(\\omega_1\\) und \\(\\omega_2\\) mit L\u00e4nge \\(n\\)<\/li>\n<li>Pr\u00fcfe ob \\(\\omega_1=\\omega_2\\).\n<p>Wenn <strong>ja<\/strong>, so ist eine L\u00f6sung f\u00fcr \\(P\\) gefunden: HALT!<\/p>\n<p>Wenn <strong>nein<\/strong>, setze \\(n=n+1\\) und gehe zu Punkt 2.<\/li>\n<\/ol>\n<p style=\"padding-left: 30px;\">Wie man am Pseudocode gut erkennen kann, kann man zu einer gegebenen Probleminstanz \\(P\\) eine L\u00f6sung durch systematisches ausprobieren finden.<\/p>\n<p style=\"padding-left: 30px;\">Es ist damit sichergestellt, dass wir so tats\u00e4chlich eine korrekte L\u00f6sung finden <strong>wenn<\/strong> es eine gibt. Und wenn nicht? Da die L\u00e4nge der Indexfolge unendlich ist und unsere Worte somit unendlich lang werden, kann es sein, dass wir niemals anhalten. Im ung\u00fcnstigsten Fall l\u00e4uft unser Programm f\u00fcr eine Kombination also ewig.<\/p>\n<p style=\"padding-left: 30px;\">So k\u00f6nnen wir nur schlussfolgern ob eine konkrete Belegung von \\(I\\) eine L\u00f6sung darstellt oder nicht. Aber wir werden\u00a0<strong>nie<\/strong> wissen ob \\(P\\) nicht doch vielleicht eine L\u00f6sung hat.<\/p>\n<p style=\"padding-left: 30px;\"><strong>Kleiner Exkurs<\/strong>: Tats\u00e4chlich k\u00f6nnen wir das Problem f\u00fcr eine kleine Anzahl an Paaren wirklich entscheiden (f\u00fcr ein oder zwei Paare ist das Problem nach Ehrenfeucht und Rozenberg (1981)\u00a0entscheidbar)!\u00a0F\u00fcr die Anzahl zwischen zwei und drei Paaren ist es noch nicht ganz gekl\u00e4rt, w\u00e4hrend die Anzahl von sieben paaren bereits ausreicht um von Unentscheidbarkeit zu sprechen (Matiyasevich, 1996).<\/p>\n<p style=\"padding-left: 30px;\"><strong>Noch ein Exkurs<\/strong>: Eine weitere M\u00f6glichkeit zu zeigen, dass das Post&#8217;sche Korrespondenzproblem nicht entscheidbar ist die Reduktion einer nicht entscheidbaren Menge auf dieses. Aber zum Thema Reduktion kommen wir noch in Teil B der theoretischen Informatik.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Um zu zeigen, dass eine Menge semi-entscheidbar\/rekursiv-aufz\u00e4hlbar ist, muss die &#8222;halbe&#8220; charakteristische Funktion berechenbar sein. Wir m\u00fcssen also mit Gewissheit sagen k\u00f6nnen, ob ein Element zur Menge geh\u00f6rt. Das Gegenteil ist uns hier aber verg\u00f6nnt und wir nehmen es in Kauf, dass unsere Testmaschine f\u00fcr eine Eingabe im ung\u00fcnstigsten Fall ewig rechnet.<\/p>\n<p>Dazu gibt muss man ebenfalls man das Flussdiagramm einer verallgemeinerten Maschine angeben, aus der ersichtlich ist, dass sie eine Eingabe in jedem Fall positiv bewertet wenn es denn eine L\u00f6sung zum gestellten Problem ist und so lange weiterrechnet bis eine L\u00f6sung gefunden ist. Im schlimmsten Fall eben ewig.<\/p>\n<h2>Lernziel 6<\/h2>\n<p style=\"padding-left: 30px;\"><em>Erl\u00e4uterung des Zusammenhangs zwischen rekursiven und rekursiv-aufz\u00e4hlbaren Mengen<\/em><\/p>\n<p>Eine spannende, aber offensichtliche Beziehung zwischen entscheidbaren und semi-entscheidbaren Mengen ist: eine Menge ist entscheidbar wenn die Menge selbst und ihr Komplement semi-entscheidbar sind. Formal ausgedr\u00fcckt:<\/p>\n<blockquote><p>Eine Menge \\(A \\subseteq \\mathbb{N}^k\\) ist rekursiv, gdw. \\(A\\) und \\(\\mathbb{N}^k\\setminus A\\) r.a. sind.<\/p><\/blockquote>\n<p>Nehmen wir also an, wir haben eine semi-entscheidbare Menge \\(A\\subseteq\\mathbb{N}\\). Wie wir wissen, ist sie semi-entscheidbar, d.h. wir k\u00f6nnen entscheiden ob ein Element zu dieser Menge geh\u00f6rt. Aber nicht das Gegenteil.<\/p>\n<p>Und was w\u00e4re dann die Menge \\(\\mathbb{N}\\setminus{A}\\)? In dieser Menge w\u00e4ren genau die Elemente, die zwar aus \\(\\mathbb{N}\\) sind, sich aber nicht in \\(A\\) befinden.<\/p>\n<p>Im Endeffekt haben wir so quasi zwei &#8222;halbe&#8220; charakteristische Funktionen, die jeweils einen Teil entscheiden, welchen die andere charakteristische Funktion nicht entschieden hat. Beide zusammen bilden dann eine &#8222;volle&#8220; charakteristische Funktion f\u00fcr \\(A\\).<\/p>\n<p><strong>Beispiel<\/strong>: \\(A\\subseteq{B}\\)<\/p>\n<p style=\"padding-left: 30px; text-align: center;\"><a href=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/mengen_ab.png\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter  wp-image-2305\" style=\"margin-left: 20px; margin-right: 270px;\" src=\"https:\/\/fernuni.digreb.net\/wp-content\/uploads\/2012\/12\/mengen_ab.png\" alt=\"mengen_ab\" width=\"197\" height=\"207\" \/><\/a><\/p>\n<p style=\"padding-left: 30px;\">Wir k\u00f6nnen also die Menge \\(A=\\{a,b,c,d,e\\}\\) semi-entscheiden. Ob ein Element <strong>nicht<\/strong> in der Menge \\(A\\) ist hingegen nicht.<\/p>\n<p style=\"padding-left: 30px;\">Und was w\u00e4re wenn wir das Komplement\u00a0\\({B\\setminus{A}}\\) entscheiden k\u00f6nnten? Also nur die Elemente \\({B\\setminus{A}}=\\{f,g,h,i,j\\}\\)? Dann k\u00f6nnten wir f\u00fcr alle Elemente aus \\(A\\) sagen, ob sie zu Menge \\(A\\) geh\u00f6ren und f\u00fcr den Rest bestimmen ob sie zu \\({B\\setminus{A}}\\) geh\u00f6ren. Damit w\u00fcrde f\u00fcr jedes Element eine positive und negative Entscheidung gef\u00e4llt werden k\u00f6nne.<\/p>\n<p style=\"padding-left: 30px;\">Und wenn das der Fall ist, ist \\(A\\) was? Genau! Komplett entscheidbar\/rekursiv.<\/p>\n<p style=\"padding-left: 30px;\">Die charakteristische Funktion \\(cf_A\\) f\u00fcr \\(A\\) w\u00e4re also:<\/p>\n<blockquote>\\(\\chi_A(x)=\\begin{cases} 1, &amp; \\mbox{ falls } x \\in A \\\\ 0, &amp; \\mbox{ wenn } x\\in B\\end{cases}\\)<\/blockquote>\n<p>Fertig. Damit ist die Menge \\(A\\) (und nat\u00fcrlich auch\u00a0\\(B\\)) rekursiv\/entscheidbar.<\/p>\n<p><strong>Antwort zum Lernziel<\/strong>: Ist es uns m\u00f6glich die Teilmenge einer anderen Menge \\(A\\subseteq{B}\\) positiv (aber nicht negativ) zu entscheiden, so ist diese semi-entscheidbar. K\u00f6nnen wir f\u00fcr den Rest, d.h. die Menge ohne die bereits positiv entschiedene Menge\u00a0\\(B\\setminus A\\) ebenfalls entscheiden, so ist die gesamte Menge \\(A\\) damit rekursiv\/entscheidbar.<\/p>\n<p>Weiter geht es mit den n\u00e4chsten Lernzielen im <a href=\"https:\/\/fernuni.digreb.net\/?p=2368\">Beitrag zum Bild- und Projektionssatz<\/a>.<\/p>\n<p>Bei Fehlern gilt wie immer: ASAP in die Kommentare damit.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Update: Index-Fehler zu (Danke, Martin!) Update: auch hier habe mich mich noch strikter an die Lernziele gehalten. Zus\u00e4tzlich dazu wurden noch ein paar Beispiele zu entscheidbaren und semi-entscheidbaren Funktionen eingepflegt um das Verst\u00e4ndnis zu erleichtern, was mir hoffentlich gelungen ist \ud83d\ude09 Update 2: ich merke gerade, dass die Eintr\u00e4ge zu lang sind. Selbst die Ladezeiten &hellip; <\/p>\n<p class=\"link-more\"><a href=\"https:\/\/fernuni.digreb.net\/?p=2313\" class=\"more-link\"><span class=\"screen-reader-text\">\u201eTIA: Rekursive und rekursiv-aufz\u00e4hlbare Mengen (Lernziele KE6, 1\/4) (Update)\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-2313","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\/2313","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=2313"}],"version-history":[{"count":9,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2313\/revisions"}],"predecessor-version":[{"id":3520,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/2313\/revisions\/3520"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2313"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2313"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2313"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}