{"id":1321,"date":"2013-04-15T22:24:25","date_gmt":"2013-04-15T20:24:25","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=1321"},"modified":"2025-11-25T22:55:02","modified_gmt":"2025-11-25T21:55:02","slug":"tia-berechenbarkeit-auf-anderen-mengen-lernziele-ke7-12","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=1321","title":{"rendered":"TIA: Berechenbarkeit auf anderen Mengen (Lernziele KE7, 1\/2)"},"content":{"rendered":"

Update<\/strong>: auch diesen Beitrag habe ich auf die Lernziele gem\u00fcnzt und ein paar Fehler behoben.<\/p>\n

Bei dieser KE f\u00fchlt es sich leicht an wie ein kleiner Bruch. Es ist ein komplett neues Thema und so erschlie\u00dft sich auf den ersten Seiten nicht unbedingt der Sinn dahinter. Zumindest mir nicht. Erst gegen Ende der Kurseinheit sieht man, wo die Reise hingegangen ist: zu der Berechenbarkeit der reellen Zahlen. Denn vorher haben wir nur die Berechenbarkeit von Wort- und Zahlenfunktionen betrachtet.<\/p>\n

Ich werde daher immer ein St\u00fcck vorgreifen wenn ich denke, dass es dem Verst\u00e4ndnis f\u00f6rderlich ist und mir nicht die Pointe f\u00fcr den Schluss aufheben.<\/p>\n

Lernziel 1<\/h2>\n

Definition der Berechenbarkeitskonzepte, welche durch eien Nummerierung auf einer Menge \\(M\\)induziert werden: \\(\\nu\\)-rekursiv, \\(\\nu\\)-r.a, \\((\\nu,{\\nu}^{‚})\\)-berechenbar<\/em><\/p>\n

Wir erinnern uns noch an die Churchsche These<\/a>? Wenn nicht, bitte nochmal nachlesen. Wird hier noch einmal wichtig werden. Im Grunde geht es hier wieder um die Verschl\u00fcsselung von Elementen aus abz\u00e4hlbaren Mengen<\/a> (hier sei nochmal erw\u00e4hnt: eine Menge ist abz\u00e4hlbar wenn sie die gleiche M\u00e4chtigkeit wie \\(\\mathbb{N}\\) hat) durch Zahlen oder W\u00f6rter, da wir Zahlen mit Register- und W\u00f6rter mit Turingmaschinen berechnen k\u00f6nnen.<\/p>\n

Wir erinnern uns auch an unsere Standardnummerierung \\(\\nu_\\Sigma\\) oder die Nummerierung der einstelligen berechenbaren Zahlenfunktionen \\(\\varphi\\). Diese sind total (\u00fcberall definiert) und sogar bijektiv (bis auf \\(\\varphi\\)). Nun f\u00fchren wir ein weiteres Berechenbarkeitskonzept ein, dass nicht weit weg von dem ist, was wir schon haben. Nehmen wir die Definition also St\u00fcck f\u00fcr St\u00fcck auseinander.<\/p>\n

Es seien \\(\\nu: \\subseteq \\mathbb{N} \\rightarrow M\\) und \\(\\nu: \\subseteq \\mathbb{N} \\rightarrow M_1\\) Nummerierungen.<\/p>\n

Eine Menge \\(X \\subseteq M\\) hei\u00dft \\(\\nu\\)–rekursiv<\/strong>, gdw. es eine berechenbare Funktion \\(g: \\subseteq \\mathbb{N} \\rightarrow \\mathbb{N}\\) gibt mit:<\/p>\n\\(g(i)=\\begin{cases}1&\\text{falls } \\nu(i) \\in X \\\\0&\\text{sonst }\\end{cases}\\)\n

f\u00fcr alle \\(i \\in Def(\\nu)\\).<\/p><\/blockquote>\n

Das ist das \u00c4quivalent zu unserer Entscheidbarkeit\/Rekursivit\u00e4t<\/a> f\u00fcr Zahlen- und Wortfunktionen. Durch die Nummerierung \\(\\nu\\) nummerieren wir alle Elemente aus der Menge \\(M_1\\) und die Funktion \\(g\\) entscheidet f\u00fcr uns ob die gegebene Nummer eines Elements aus \\(M_1\\) uns zu einem Element bringt, dass in der Menge \\(X\\) liegt oder nicht.<\/p>\n

 <\/p>\n

Es geht uns also im Endeffekt nur darum die Elemente aus der Menge \\(X\\) zu entscheiden.<\/p>\n

Machen wir erst einmal weiter im Text. Anschlie\u00dfend folgt ein Beispiel um es etwas „greifbarer“ zu machen.<\/p>\n

Eine Menge \\(X \\subseteq M\\) hei\u00dft \\(\\nu\\)–rekursiv-aufz\u00e4hlba<\/strong>r, gdw. es eine berechenbare Funktion \\(g: \\subseteq \\mathbb{N} \\rightarrow \\mathbb{N}\\) gibt mit:<\/p>\n\\(g(i)=\\begin{cases}existiert&\\text{falls } \\nu(i) \\in X \\\\div&\\text{sonst }\\end{cases}\\)\n

f\u00fcr alle \\(i \\in Def(\\nu)\\).<\/p><\/blockquote>\n

Und hier haben wir das \u00c4quivalent zu unserer Semi-Entscheidbarkeit\/rekursiver Aufz\u00e4hlbarkeit.<\/p>\n

Wir k\u00f6nnen zwar immer sagen, ob ein Element zu einer Menge \\(X\\) geh\u00f6rt, haben aber bei der gegenteiligen Aussage ein Problem. Denn hier divergiert die Funktion, sie gibt uns also kein Ergebnis und kann unendlich laufen. Es ist also festgelegt, dass wir im positiven Fall (irgendwann) eine Antwort erhalten, im negativen Fall aber nicht. Prominente Beispiele f\u00fcr die Semi-Entscheidbarkeit sind – wie im verlinkten Beitrag erw\u00e4hnt – das Halteproblem<\/a> und der Busy Beaver<\/a>.<\/p>\n

Und nun die letzte Definition f\u00fcr diesen Abschnitt. Hier geht es nicht um eine Menge, sondern um eine Funktion:<\/p>\n

Eine Funktion \\(f \\subseteq M_1 \\rightarrow M\\) hei\u00dft \\((\\nu_1,\\nu)\\)-berechenbar, gdw. es eine berechenbare Funktion \\(g: \\subseteq \\mathbb{N} \\rightarrow \\mathbb{N}\\) gibt mit:<\/p>\n

\\(f \\circ \\nu_1(i) = \\nu \\circ g(i)\\) f\u00fcr alle \\(i\\) mit \\(\\nu_1(i) \\in Def(f)\\).<\/p><\/blockquote>\n

Wenn man es ausklammert, hat man vielleicht einen besseren Blick auf die Funktion: \\(f(\\nu_1(i)) = \\nu(g(i))\\) f\u00fcr alle \\(i\\) mit \\(\\nu_1(i)\\in Def(f)\\). Okay, das hat nicht unbedingt super geklappt. Diese definition bedeutet, dass eine Menge \\((\\nu_1,\\nu)\\)-berechenbar ist wenn es ein Verfahren gibt, dass uns zu jeder \\(\\nu_1\\)-Nummer eines Elements der Definitionsmenge von \\(f\\) eine \\(\\nu\\)-Nummer der Bildmenge von \\(f\\) berechnet.<\/p>\n

W\u00e4hrend also die Funktion \\(f\\) auf ihren Mengen (zu einem Definitionswert aus \\(M_1\\) gibt es durch die Funktion einen Funktionswert aus \\(M\\)) herumrechnet, k\u00fcmmern wir uns mit der Funktion \\(g\\) um die Umrechnung der „Nummerierungsnummern“ \\(\\nu\\) und \\(\\nu_1\\) der beiden Mengen \\(M_1\\) und \\(M\\).<\/p>\n

Okay, das ist wahrscheinlich nicht sonderlich einleuchtend. Ich w\u00fcrde sagen, wir suchen uns ein nettes Beispiel.<\/p>\n

Was wir zum Durchspielen der Definition brauchen sind<\/p>\n