{"id":909,"date":"2012-11-12T12:11:50","date_gmt":"2012-11-12T10:11:50","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=909"},"modified":"2012-11-12T16:45:57","modified_gmt":"2012-11-12T14:45:57","slug":"ti-entscheidbarkeit-und-charakteristische-funktion","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=909","title":{"rendered":"TI: Entscheidbarkeit und charakteristische Funktion"},"content":{"rendered":"

Inhaltsverzeichnis<\/strong><\/p>\n

    \n
  1. Berechenbarkeit von Zahlen- und Wortfunktionen<\/li>\n
  2. Entscheidbarkeit (rekursiv) und Semi-Entscheidbarkeit (rekursiv aufz\u00e4hlbar)<\/li>\n
  3. Erstes und zweites Diagonalargument von Cantor<\/li>\n<\/ol>\n

    Im Skript wird dieses Thema schnell durchgekauft. Pers\u00f6nlich halte ich es jedoch f\u00fcr sehr wichtig, sich diese Begrifflichkeiten unbedingt zu merken. Also fangen wir auch direkt an:<\/p>\n

    Berechenbarkeit<\/h2>\n

    Noch einmal kurz als Wiederholung bzgl. Berechenbarkeit: dem Begriff selbst liegen Berechnungsmodelle zugrunde. Wir haben hier die LOOP-Berechenbarkeit (primitiv rekursive Funktionen) und die WHILE-Berechenbarkeit ($$\\mu$$-rekursive Funktionen). W\u00e4hrend jedes LOOP-Programm durch ein WHILE-Programm ersetzt werden kann, kann nicht jedes WHILE-Programm durch ein LOOP-Programm ersetzt werden, d.h. die LOOP-Programme sind eine echte Untermenge der WHILE-Programme. Wann ist eine Funktion denn nun berechenbar? Genau dann:<\/p>\n

    Eine (ggf. partielle) Zahlenfunktion<\/strong> $$f : \\subseteq \\mathbb{N}^k \\rightarrow \\mathbb{N}$$ ist genau dann berechenbar, wenn es eine Registermaschine $$M$$ gibt, die die Funktion berechnet. Wenn also $$f = f_M$$ gilt.<\/p><\/blockquote>\n

    Und was ist mit Wortfunktionen f\u00fcr Turing-Maschinen?<\/p>\n

    Eine (ggf. partielle) Wortfunktion<\/strong> $$g : \\subseteq (\\Sigma^*)^k \\rightarrow \\Sigma^*$$ ist genau dann berechenbar, wenn es eine Turing-Maschine $$T$$ gibt, die die Funktion berechnet. Wenn also $$g =g_T$$ gilt.<\/p><\/blockquote>\n

    Aber eig. brauchen wir die Turing-Maschinen garnicht. Warum? Zauberwort: Standardnummerierung. Wir k\u00f6nnen dadurch die Berechenbarkeit von Worten auf die Berechenbarkeit von Zahlen zur\u00fcckf\u00fchren indem wir die Wortfunktionen mittels Standardnummerierung in Zahlen codieren und diese mit Registermaschinen berechnen. Da die Standardnummerierung bijektiv ist, k\u00f6nnen wir den Spa\u00df auch anders herum aufziehen und unsere Zahlenfunktionen durch Turing-Maschinen berechnen lassen nachdem wir die Zahlenfunktionen in Worte codiert haben.<\/p>\n

    Schaut dazu in den entsprechenden Beitrag f\u00fcr die Kurseinheit 4<\/a>. Dort wird das Thema dann etwas genauer behandelt. Wichtig ist, dass man sich den Zusammenhang zwischen Wort- und Zahlenfunktionen und das Bindeglied (Standardnummerierung) zwischen diesen merkt.<\/p>\n

    (Semi-) Entscheidbarkeit<\/h2>\n

    Wir unterscheiden hier die Entscheidbarkeit und die Semi-Entscheidbarkeit. Ihr Kern ist die charakteristische Funktion. Wozu brauchen wir sie? Der Begriff „Entscheidbarkeit“ ist auf Mengen fokusiert, f\u00fcr uns sind aber eher Funktionen spannend, wo nur der Begriff „Berechenbarkeit“ verwendet wird. Die charakteristische Funktion ist das Bindelglied zwischen diesen Mengen und der Funktionen (den Satz habe ich aus dem Buch von Dirk W. Hoffmann geklaut). Formalisieren wir das:<\/p>\n

    Eine Menge $$ T \\subseteq M$$ ist entscheidbar\/rekursiv<\/strong> wenn die charakteristische Funktion $$\\chi_T: M \\rightarrow \\{0,1\\}$$ definiert durch<\/p>\n

    $$\\chi_T(t)=\\begin{cases} 1, & \\mbox{ falls } t \\in T \\\\ 0, & \\mbox{ sonst}\\end{cases}$$<\/p>\n

    berechenbar ist (Achtung: sie muss berechenbar sein!)<\/p><\/blockquote>\n

    Was ist damit gemeint? Damit ist gemeint, dass man hier eindeutig entscheiden kann ob ein Element $$t$$ aus der Menge $$M$$ in der Menge $$T$$ sind. Es wird nach endlicher Zeit also eindeutig entschieden ob JA<\/strong> oder NEIN<\/strong>.<\/p>\n

    Beispiel<\/strong>: ob eine Zahl gerade ist oder eine Primzahl ist, ist entscheidbar\/rekursiv (Wikipedia). Diese Zahlen sind auch rekursiv aufz\u00e4hlbar (denn ich kann sie ja aufz\u00e4hlen).<\/p>\n

    Und nun zur Semi-Entscheidbarkeit\/rekursiver Aufz\u00e4hlbarkeit.<\/p>\n

    Eine Menge $$T$$ ist semi-entscheidbar\/rekursiv<\/strong> aufz\u00e4hlbar<\/strong> wenn die partielle charakteristische Funktion $$\\chi^{‚}_T: M \\rightarrow \\{1\\}$$ definiert durch<\/p>\n

    $$\\chi^{‚}_T(t)=\\begin{cases} 1, & \\mbox{ falls } t \\in T \\\\ \\perp, & \\mbox{ sonst}\\end{cases}$$<\/p><\/blockquote>\n

    Diesen Spa\u00df nennt man also semi-entscheidbar.\u00a0 D.h. wenn das Element $$t$$ aus $$M$$ in $$T$$ liegt, so wird nach endlicher Zeit ein JA<\/strong> (oder auch NEIN <\/strong>wenn man anders herum testen m\u00f6chte) ausgegeben. Wenn nicht, so h\u00e4ngen wir ggf. in einer Endlosschleife. Der Unterschied hier ist, dass wir nicht wissen ob wir einfach noch l\u00e4nger warten m\u00fcssen bis wir (irgendwann) ein JA\/NEIN<\/strong> bekommen oder wir tats\u00e4chlich in einer Endlosschleife sind.<\/p>\n

    Beispiel<\/strong>: Das Halteproblem<\/a> (ob alle Paare (Turingmaschine, Eingabe)) f\u00fcr alle Eingaben und Turingmaschinen halten ist semi-entscheidbar\/rekursiv aufz\u00e4hlbar, aber nicht entscheidbar\/rekursiv. Denn f\u00fcr einige Eingaben kann eine Turingmaschine in eine Endlosschleife laufen und wir k\u00f6nnen nicht mit Sicherheit sagen ob sie nicht doch vielleicht irgendwann h\u00e4lt. Damit ist das Halteproblem eben nur rekursiv aufz\u00e4hlbar, denn wir k\u00f6nnen die Menge der Paare mit der Eigenschaft ja aufz\u00e4hlen.<\/p>\n

    Achtung<\/em>: jede rekursiv aufz\u00e4hlbare\/semi-entscheidbare Menge ist abz\u00e4hlbar. Aber nicht jede abz\u00e4hlbare Menge ist rekursiv aufz\u00e4hlbar\/semi-entscheidbar. Z.B. ist die Menge der falschen Formeln einer PL1-Sprache (dazu in einem sp\u00e4teren Beitrag mehr) abz\u00e4hlbar, jedoch nicht entscheidbar\/rekursiv aufz\u00e4hlbar. Ebenso ergeht es uns mit dem Busy Beaver<\/a> Problem (auch hierzu folgt sp\u00e4ter ein Beitrag). Das Halteproblem, wie im Abschnitt vorher angegeben, ist ein Beispiel f\u00fcr die andere Richtung.<\/p>\n

    Abz\u00e4hlbarkeit: erstes und zweites Diagonalargument (Cantor)<\/h2>\n

    Wir bezeichnen Mengen als abz\u00e4hlbar<\/em> wenn diese die gleiche M\u00e4chtigkeit hat, wie $$\\mathbb{N}$$. In dem Eintrag f\u00fcr die Cantorsche Tupelfunktion<\/a> wir beschrieben, wie man pr\u00fcft ob zwei Mengen gleichm\u00e4chtig sind. Wir pr\u00fcfen also den Fall $$\\left| M \\right| = \\left| \\mathbb{N} \\right|$$? Um das zu tun m\u00fcssen wir eine bijektive Abbildung $$f: M \\rightarrow \\mathbb{N}$$ aufzeigen, die jedem Element aus $$M$$ eindeutig ein Element aus $$\\mathbb{N}$$ zuordnet. Durch die Bijektivit\u00e4t ist diese Funktion nat\u00fcrlich umkehrbar und wir k\u00f6nnen zu einem Element aus $$\\mathbb{N}$$ wieder eindeutig ein Element aus $$M$$ zuordnen. Das nennt man das erste Diagonalisierungsargument<\/a> von Cantor.<\/p>\n

    Wie in dem oben verlinkten Beitrag k\u00f6nnen wir z.B. eine bijektive Abbildung $$f: \\mathbb{Z} \\rightarrow \\mathbb{N}$$ angeben und so zeigen, dass die ganzen Zahlen ($$\\mathbb{Z}$$) genauso m\u00e4chtig sind wie die nat\u00fcrlichen Zahlen ($$\\mathbb{N}$$) obwohl die ganzen Zahlen gef\u00fchlt mehr Zahlen enthalten als die nat\u00fcrlichen Zahlen. Ebenso k\u00f6nnen wir durch diese Cantorsche Tupelfunktion $$n$$-Tupel aus $$\\mathbb{N}^n$$, z.B. $$(1,5)$$ aus $$\\mathbb{N}^2$$ auf eine einzige Zahl aus $$\\mathbb{N}$$ abbilden. Das gleiche geht f\u00fcr Tripel usw. Damit ist bewiesen, dass der $$n$$-dimensionale Raum $$\\mathbb{N}^n$$ gleichm\u00e4chtig zu $$\\mathbb{N}$$ ist, egal welches $$n$$ wir w\u00e4hlen.<\/p>\n

    Gibt es ein Beispiel f\u00fcr nicht abz\u00e4hlbare Mengen? Ja: die reellen Zahlen<\/a> sind nicht gleichm\u00e4chtig zu $$\\mathbb{N}$$ und damit auch nicht abz\u00e4hlbar. Es gibt also keine bijektive Abbildung $$f: \\mathbb{R} \\rightarrow \\mathbb{N}$$. Cantor bewies dies 2x. Sein letzter Beweis ist einfacher, deswegen m\u00f6chte ich diesen hier kurz skizzieren: es ist sein zweites Diagonalisierungsargument<\/a>.<\/p>\n

    Beispiel: zweites Diagonalisierungsargument von Cantor<\/h3>\n

    Zun\u00e4chst einmal sollten wir uns klar machen, was wir mit einer bijektiven Abbildung denn eigentlich machen. Eine bijektive Abbildung kann es nur zwischen zwei gleichm\u00e4chtigen Mengen geben. Im vorherigen Beitrag hatten wir z.B. $$M_1 = \\{a,z,d\\}$$ und $$M_2 = \\{5,1,9\\}$$. Wir geben eine bijektive Abbildung f\u00fcr diese Mengen an: $$f: M_1 \\rightarrow M_2$$ definiert durch $$a=5, z=1, d=9$$ (Umkehrabbilung $$f^{-1}$$ ist dann genau umgekehrt).<\/p>\n

    \"\"<\/a><\/p>\n

    Wir wir sehen k\u00f6nnen wir zu einem Element aus $$M_1$$ eindeutig ein Element aus $$M_2$$ zuordnen und aufgrund der Eindeutigkeit geht es auch anders herum und wir bekommen ein eindutiges Element aus $$M_1$$ zu einem Element aus $$M_2$$. Damit sind die beiden Mengen gleichm\u00e4chtig.<\/p>\n

    Eine bijektive Abbildung k\u00f6nnen wir auch f\u00fcr $$\\mathbb{Z}$$ und $$\\mathbb{N}$$ angeben und zeigen, dass diese Mengen ebenfalls gleichm\u00e4chtig sind. Wir verwenden wieder das Beispiel aus dem Beitrag f\u00fcr die Cantorsche Tupelfunktion: $$ f:\\mathbb{Z} \\rightarrow \\mathbb{N}$$ definiert durch:<\/p>\n

    $$f(x) = \\begin{cases} -2x, & \\mbox{ falls } x<0\\\\ 2x+1, & \\mbox{ falls } x\\geq 0\\end{cases}$$+<\/p>\n

    Die Umkehrabbildung ist:<\/p>\n

    $$f^{-1}(x) = \\begin{cases} -x\/2, & \\mbox{ wenn x gerade }\\\\ (x-1)\/2, & \\mbox{ wenn x ungerade}\\end{cases}$$<\/p>\n

    Unsere Abbildung sieht nun f\u00fcr ein paar Zahlen so aus:<\/p>\n

    \"\"<\/a><\/p>\n

    Wie wir sehen, sind auch diese Mengen gleichm\u00e4chtig. Wir haben wieder eine eindeutige Zuordnung zwischen den Elementen aus $$\\mathbb{R}$$ und $$\\mathbb{N}$$. Probieren wir das gleiche doch f\u00fcr $$\\mathbb{N} \\rightarrow \\mathbb{R}$$. Es reicht uns sogar einfach nur alle reellen Zahlen zwischen 0 und 1 anzuschauen (also: 0,72636…, 0,12238383…., …). F\u00fcr eine bijektive Abbildung m\u00fcssen wir allen diesen Zahlen dann nat\u00fcrliche Zahlen zuordnen. Dazu basteln wir uns eine Matrix und eine willk\u00fcrliche Abbildungsfunktion, die allen Zahlen aus $$\\mathbb{N}$$ eine Zahl aus dem Intervall $$(0,1)$$ aus $$\\mathbb{R}$$ zuordnet.<\/p>\n

    \"\"<\/a><\/p>\n

    Wir weisen z.B. dem Definitionswert $$0$$ aus $$N$$ den Funktionswert $$0,1574…$$, dem Definitionswert $$1$$ die $$0,0701…$$ usw. zu. Mit $$…$$ haben wir angedeutet, dass die Matrix aus unendlich vielen Zeilen und die Dezimalbruchdarstellung aus unendlich vielen Nachkommastellen besteht. Lasst euch von den K\u00e4stchen nicht verwirren, $$0,1574…$$ ist ein Element, die K\u00e4stchen dienen nur dem, was wir gleich vor haben: wir zeigen jetzt mit dem Diagonalisierungsargument, dass die Matrix nie vollst\u00e4ndig sein kann, dass es also einen Wert zwischen $$0$$ und $$1$$ aus $$\\mathbb{R}$$ gibt, auf den wir nicht abbilden.<\/p>\n

    Wir f\u00fchren einen Widerspruchsbeweis: nehmen wir an die Matrix sein vollst\u00e4ndig und wir haben alle Zahlen aus $$\\mathbb{R}$$ zwischen 0 und 1 in Dezimaldarstellung durchnumemriert. Wir basteln uns einen neuen Funktionswert, der von allen anderen Funktionswerten verschieden ist: wir verwenden die diagonalen Elemente der Matrix (gr\u00fcne Markierung) und erh\u00f6hen oder erniedrigen sie um 1 ($$<5$$: neue Zahl wird erh\u00f6ht, $$\\geq 5 $$: neue Zahl wird erniedrigt) und verwenden diese Zahlen als Nachkommastellen unseres neuen Eintrags. Damit ist sichergestellt, dass wir diesen Eintrag noch nicht als Funktionswert in unserer Matrix haben, denn die reelle Zahl in der $$i$$-ten Zeile unserer Matrix unterscheidet sich min. in der $$i$$-ten Stelle von unserer neuen Zahl (wir haben sie ja erniedrigt oder erh\u00f6ht).<\/p>\n

    \"\"<\/a><\/p>\n

     <\/p>\n

    Damit ist $$0,2658…$$ unser neuer Eintrag, der definitiv noch nicht un unserer Matrix ist. Soweit so gut, nur wie wird er jetzt mit einer Zahl aus $$\\mathbb{N}$$ nummeriert?! Wir sind doch von der Vollst\u00e4ndigkeit unserer Matrix ausgegangen und haben damit doch alle unsere Elemente aus $$\\mathbb{N}$$ ausgesch\u00f6pft, haben aber trotzdem ein neues aus $$\\mathbb{R}$$, dass wir nummerrieren m\u00fcssen! Also: Widerspruch<\/strong>! Damit sind $$\\mathbb{R}$$ und $$\\mathbb{N}$$ nicht gleich m\u00e4chtig, $$\\mathbb{R}$$ ist sogar deutlich gr\u00f6\u00dfer, da wir ja nicht einmal das Intervall $$(0,1)$$ mit allen Elementen aus $$\\mathbb{N}$$ nummerrieren konnten. $$\\mathbb{R}$$ und $$\\mathbb{N}$$ stehen also f\u00fcr zwei unterschiedliche Unendlichkeiten. Ein sehr cooler Beitrag<\/a> auf youtube zeigt das nochmal in bewegten Bildern.<\/p>\n

    So schlie\u00dft sich auch der Kreis zu den Funktionen: die Menge aller berechenbaren mehrstelligen Wortfunktionen ist ebenfalls abz\u00e4hlbar. Warum? Weil wir die Menge der mehrstelligen Wortfunktionen in einstellige Wortfunktionen \u00fcberf\u00fchren k\u00f6nnen, diese durch die Standardnummerierung<\/a> in einstellige Zahlenfunktionen \u00fcberf\u00fchrt wird und wir diese anschlie\u00dfend durchnummerieren k\u00f6nnen.<\/p>\n","protected":false},"excerpt":{"rendered":"

    Inhaltsverzeichnis Berechenbarkeit von Zahlen- und Wortfunktionen Entscheidbarkeit (rekursiv) und Semi-Entscheidbarkeit (rekursiv aufz\u00e4hlbar) Erstes und zweites Diagonalargument von Cantor Im Skript wird dieses Thema schnell durchgekauft. Pers\u00f6nlich halte ich es jedoch f\u00fcr sehr wichtig, sich diese Begrifflichkeiten unbedingt zu merken. Also fangen wir auch direkt an: Berechenbarkeit Noch einmal kurz als Wiederholung bzgl. Berechenbarkeit: dem Begriff … <\/p>\n

    \u201eTI: Entscheidbarkeit und charakteristische Funktion\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":[1,4],"tags":[],"class_list":["post-909","post","type-post","status-publish","format-standard","hentry","category-fernuni","category-theoretische-informatik"],"_links":{"self":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/909","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=909"}],"version-history":[{"count":22,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/909\/revisions"}],"predecessor-version":[{"id":938,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=\/wp\/v2\/posts\/909\/revisions\/938"}],"wp:attachment":[{"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=909"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=909"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/fernuni.digreb.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=909"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}