{"id":837,"date":"2012-11-12T12:13:57","date_gmt":"2012-11-12T10:13:57","guid":{"rendered":"http:\/\/fernuni.digreb.net\/?p=837"},"modified":"2025-11-25T22:39:47","modified_gmt":"2025-11-25T21:39:47","slug":"ti-berechenbarkeit-ke4","status":"publish","type":"post","link":"https:\/\/fernuni.digreb.net\/?p=837","title":{"rendered":"TIA: Berechenbarkeit (Lernziele aus KE4, Update 6)"},"content":{"rendered":"

Update:\u00a0<\/b>ich modelliere auch diesen Beitrag auf die Lernziele um. Evtl. kann es sein, dass der Beitrag nicht ganz fertig wird, so dass ein paar Antworten (noch) leer sind. Da ich ihn aber nicht speichern kann ohne ihn zu aktualisieren oder ihn offline nehmen m\u00fcsste, habe ich keine andere Wahl als das zun\u00e4chst so zu handhaben.<\/del><\/p>\n

Update 6<\/strong>: Nachdem ich nun schon zwei Mails zum Thema \\(\\mu\\)-Rekursion bekommen habe, m\u00f6chte ich das hier noch einmal ausf\u00fchren. F\u00fcr die Details zum Thema Nullstellen m\u00f6chte ich mich hier auch bei Oliver bedanken. Lernziel 5 also.<\/p>\n

Update 5<\/strong>: mir ist was zur Standardnummerierung von \\(\\Sigma^{*}\\) und \\(P^{(1)}\\) aufgefallen, dass ich hier passend unbedingt noch erw\u00e4hnen musste.<\/p>\n

Riesen Update<\/strong>: alle Lernziele habe ich nun \u00fcberarbeitet und einige Ungenauigkeiten korrigiert. Der Beweis der nicht-berechenbaren Funktionen ist wohl auf das 10-fache des urspr\u00fcnglichen Texts angewachsen. Irgendwie konnte ich mich mit dem alten Verweis auf das Diagonalrgument von Cantor f\u00fcr die \u00dcberabz\u00e4hlbarkeit der reellen Zahlen nicht anfreunden (beim ersten Erstellen hielt ich das noch f\u00fcr ausreichend) und habe den Skriptbeweis nun komplett auseinander genommen. Hoffentlich hilft es euch.<\/p>\n

Kurseinheit 4 ist wieder ein Rundumschlag. Einige Dinge, die hier drin sind, h\u00e4tten sich auch in Kurseinheit 2 wiederfinden m\u00fcssen (LOOP, WHILE, Churchsche These und Zusammenhang zu \\(\\mu\\)-rekursiven Funktionen. Taten sie aber nicht. W\u00e4re wahrscheinlich einfach zu einfach gewesen. Ich w\u00fcrde daher vorschlagen, dass wir uns ausnahmsweise nicht thematisch, sondern anhand der Lernziele entlang hangeln.<\/p>\n

Rekapitulation: Zahlen, W\u00f6rter<\/strong><\/span><\/p>\n

Nochmal als Wiederholung bevor wir loslegen.<\/p>\n

Zahlenfunktionen<\/strong>: \\(f:\\subseteq \\mathbb{N}^k \\rightarrow \\mathbb{N}\\). D.h. Abbildung von ggf. mehrstelligen (unser \\(k\\)) Eingabewerten von nat\u00fcrlichen Zahlen auf einen einzigen Ausgabewert, eine einzige nat\u00fcrliche Zahl. Berechenbar mit Registermaschinen, nicht mit Turingmaschinen.<\/p>\n

Konkretes Beispiel<\/strong>: \\(f\\subseteq\\mathbb{N}^3\\rightarrow\\mathbb{N}\\) mit \\(f(x,y,z)=x+y-z\\),<\/p>\n

z.B. \\(f(431,469,899)=1\\)<\/p>\n

Wortfunktionen<\/strong>: \\(g:\\subseteq \\Sigma^{*k} \\rightarrow \\Sigma^{*}\\). D.h. Abbildung von ggf. mehreren\u00a0(wieder unser \\(k\\))\u00a0Eingabewerten von beliebig langen (unser \\(*\\)) Worten \u00fcber einem Alphabet (unser \\(\\Sigma\\)) auf einen einzigen Ausgabewert: ein einziges, beliebig langes Wort. \\(\\Sigma^{*}\\) ist hier die Wortmenge \u00fcber dem Alphabet \\(\\Sigma\\). Berechenbar mit Turingmaschinen, nicht mit Registermaschinen.<\/p>\n

Konkretes Beispiel<\/strong>: \\(g:\\subseteq \\Sigma^{*2}\\rightarrow \\Sigma^{*}\\) mit \\(g(x,y)=xy\\),<\/p>\n

z.B. \\(g(abbb,aaaa)=abbbaaaa\\)<\/p>\n

Wir k\u00f6nnen Zahlenfunktionen nicht auf Turingmaschinen und Wortfunktionen nicht auf Registermaschinen berechnen. Es gibt jedoch einen Weg: Erst wenn man W\u00f6rter in Zahlen codiert und Zahlen in W\u00f6rter (bijektive Abbildung zwischen zwei Mengen: W\u00f6rtern und Zahlen) kann man diese mit den entsprechend anderen Maschinen berechnen.<\/p>\n

Ausgenutzt wird dabei, dass Registermaschinen und Turingmaschinen \u00fcber Flussdiagramme definiert sind. Aber k\u00fcmmern wir uns zun\u00e4chst um die Standardnummerierung selbst.<\/p>\n

Das ist die sogenannte Standardnummerierung<\/em> (bijektive Abbildung zwischen den nat\u00fcrlichen Zahlen und einer Mengen). Definition kommt gleich. Es gibt jedoch einen wesentlichen Unterschied zu einer Nummerierung, der nicht verschwiegen werden darf.<\/p>\n

Eine Nummerierung<\/em>\u00a0ist nicht bijektiv;\u00a0Surjektivit\u00e4t<\/a> reicht. Wir k\u00f6nnen in der Nummerierung dann jedem Wort mindestens eine Zahl zuordnen, aber wir haben keine eindeutige Umkehrabbildung, d.h. wenn wir dann zu einem Wort die zugeh\u00f6rige Zahl suchen, k\u00f6nnten wir diese mit etwas Pech auf mehrere Zahlen abbilden.<\/p>\n

Achtung<\/strong>: w\u00e4hrend die Standardnummerierung von \\(\\Sigma^{*}\\) durch \\(\\nu_\\Sigma\\) bijektiv ist, ist die Standardnummerierung der berechenbaren, einstelligen Funktionen \\(P^{(1)}\\) aus dem n\u00e4chsten Beitrag<\/a> das nicht! Warum, sage ich dann dort. Bitte behaltet das unbedingt im Hinterkopf.<\/p>\n

Formal definiert ist eine Nummerierung<\/em>\u00a0also:<\/p>\n

\\(\\nu:\\subseteq\\mathbb{N}\\rightarrow{M}\\)<\/blockquote>\n

Sie kann partiell sein und ist – wie gesagt – surjektiv. Damit hat zwar jedes Element aus der nummerierten Menge \\(M\\) eine Zahl aus \\(\\mathbb{N}\\), aber nicht zu jeder Zahl aus \\(\\mathbb{N}\\)\u00a0gibt ein Element aus der Menge \\(M\\).<\/p>\n

Und weil Marco mich in den Kommentaren zu KE5 auf die Idee gebracht hat, noch eine kleine Nebeninfo: Haben wir eine bijektive Abbildung zwischen zwei Mengen, gelten diese als gleichm\u00e4chtig und die Eigenschaften der einen, gelten auch f\u00fcr die andere Menge. Bilden wir also die nat\u00fcrlichen Zahlen mittels einer bijektiven Funktion auf eine andere Menge ab, wie wir das mit der Standardnummerierung tun, so \u00fcbernimmt diese Menge eine wunderbare Eigenschaft der nat\u00fcrlichen Zahlen \\(\\mathbb{N}\\): sie ist dann ebenfalls abz\u00e4hlbar unendlich<\/a>.<\/p>\n

Lernziel 1<\/h2>\n

Angabe und Erl\u00e4uterung der Definition einer Standardnummerierung von \\(\\Sigma^{*}\\)<\/em><\/p>\n

Nehmen wir als Beispiel ein Alphabet \\(\\Sigma\\)\u00a0 mit \\(n\\) Symbolen, welches eine totale Ordnung hat (d.h. die \\(n\\) Symbole innerhalb des Alphabets sind – wie auch immer – eindeutig sortiert), so beinhaltet \\(\\Sigma^*\\) alle Worte \u00fcber dem Alphabet \\(\\Sigma\\).<\/p>\n

\\(\\nu_\\Sigma(i)\\) ist das \\(i\\)-te Wort aus dieser sortierten Liste. Die Sortierung nennt man Ordnungsfunktion<\/em>. Das spannende an dieser Nummerierung ist, dass sie bijektiv<\/strong> ist. Wir haben also eine eindeutige Abbildung von einem Wort in eine Zahl und eine Inverse, die uns zu einer Zahl ein eindeutiges Wort liefert. Lasst uns die Definition mal formalisieren:<\/p>\n

\\(\\Sigma\\) ist ein Alphabet mit \\(card(\\Sigma) >= 1\\).<\/p>\n

\\(a: \\{1,…,n\\} \\rightarrow \\Sigma\\) die Ordnungsfunktion \\(a\\) mit \\(a_i := a(i)\\) und \\(\\Sigma = \\{a_1, …, a_n\\}\\).<\/p>\n

\\(\\sigma:\\Sigma^* \\rightarrow \\mathbb{N}\\) mit \\(\\sigma(\\varepsilon):=0\\) sowie<\/p>\n

\\(\\sigma ({a_{i}}_{k} {a_{i}}_{k-1} … {a_{i}}_{1} {a_{i}}_{0}) := i_k n^k + i_{k-1} n^{k-1} + … i_1 n+i_0\\) f\u00fcr alle \\( k \\in \\mathbb{N}, i_0,…,i_k \\in \\{1,…,n\\}\\).<\/p>\n

\\(\\nu_\\Sigma : \\mathbb{N} \\rightarrow \\Sigma^*\\) ist unsere Inverse der Funktion \\(\\sigma\\) und damit \\(\\nu_\\Sigma := \\sigma^{-1}\\). Sie gibt uns zu einer gegebenen Zahl das entsprechende, eindeutige Wort zur\u00fcck und wird Standardnummerierung<\/strong> von \\(\\Sigma^{*}\\) genannt.<\/p><\/blockquote>\n

Keine Sorge, wir gehen das direkt an einem Beispiel durch.<\/p>\n

Beispiel<\/strong>:<\/p>\n

\\(\\Sigma = \\{a,b\\}\\) mit \\(card(\\Sigma) = 2\\) (Kardinalit\u00e4t<\/a>, M\u00e4chtigkeit einer Menge). Ein Alphabet mit den Buchstaben \\(a\\) und \\(b\\), d.h. nur \\(2\\) Elementen und damit der Kardinalit\u00e4t \\(2\\).<\/p>\n

Wir haben zwei Elemente \\(a\\) und \\(b\\) im Alphabet, also ist \\(n = 2\\) und wir haben \\(a_1 = a(1) = a\\) und \\(a_2 = a(2) = b\\): innerhalb der Wortmenge werden die Elemente wie im Skript nach L\u00e4nge und dann lexikographisch geordnet. Die Menge \\(\\Sigma^*\\) w\u00e4re dann<\/p>\n

\\(\\Sigma^*=\\{a,b,aa,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,bbb,…\\}\\).<\/p>\n

Wir haben nun jedem unserer zwei Elemente eine Ordnungszahl zugewiesen. Das ist unsere Ordnungsfunktion \\(a\\).<\/p>\n

Der letzte Teil ist jetzt etwas ekelig, aber halb so wild. Erinnert mich irgendwie an SIMPLEX. Die Funktion \\(\\sigma\\) macht nichts anderes, als zu einem bestimmten Wort die eindeutige Zahl anhand der definierten Ordnung zu bestimmen. Wir suchen z.B. die zugewiesene Zahl zu \\(abb\\). \\(abb\\) steht an 10. Stelle in der Reihenfolge und wir erwarten die \\(10\\) auch als Ergebnis.<\/p>\n

\\(n = 2\\) (ist klar, die Kardinalit\u00e4t von \\(\\Sigma\\), d.h. Anzahl der Elemente)<\/p>\n

\\(k = 2\\) (das Wort \\(abb\\) besteht aus drei Elementen, wir z\u00e4hlen von \\(0\\) und haben damit \\(k=2\\))<\/p>\n

\\(i\\) ist unsere Ordnungszahl. Da \\(a\\) zuerst kommt, ist \\(a=1\\) und da \\(b\\) an zweiter Stelle in unserer Ordnung kommt, ist \\(b=2\\). H\u00e4tten wir noch \\(c\\), so w\u00e4re \\(c=3\\) unserer festgelegten Ordnung nach.<\/p>\n

\\(\\begin{array} {lcl}\\sigma(abb)&=&1\\cdot2^2 + 2\\cdot2 + 2\\\\{}&=&4+4+2\\\\{}&=&10\\end{array}\\)<\/p>\n

Und ja, \\(abb\\) steht an 10. Stelle in unserer Ordnung.<\/p>\n

Man mache sich einfach klar, dass ein beliebiges Alphabet \\(\\Sigma\\) definieren k\u00f6nnen, solange wir nur eine numerische Ordnung auf den Elementen des Alphabets definieren. Da wir aus den Elementen des Alphabets Worte bauen k\u00f6nnen, k\u00f6nnen wir auch aus den Ordnungszahlen, die den Elementen zugeordnet sind Kombinationen herstellen.<\/p>\n

Die Ordnung ist ja nichts weiter als die Festlegung der Reihenfolge der verwendeten Elemente in unserem Alphabet. Damit rechnen wir statt mit den Buchstaben, nun mit ihren „Ordnungszahlen“. Und da auf den verwendeten, nat\u00fcrlichen Zahlen f\u00fcr unsere Reihenfolge auch eine nat\u00fcrliche Ordnung herrscht (\\(1<2<3<4<…\\)), k\u00f6nnen wir damit wunderbar rechnen.<\/p>\n

Unser \\(a\\) im Alphabet repr\u00e4sentiert unsere „Ordnungszahl“ \\(1\\) und \\(b\\) unsere „Ordnungszahl“ \\(2\\), welche wir dann oben in der Gleichung f\u00fcr \\(\\sigma(abb)\\) verwendet haben und damit auf den Rechenweg \\(1\\)<\/span> \\(\\cdot2^2 +\\) \\(2\\)<\/span> \\(\\cdot2^1 +\\) \\(2\\)<\/span> \\(\\cdot2^0\\)<\/span> kommen. Die gr\u00fcne 1 ist daher die Ordnungszahl unseres \\(a\\) und die rote 2 die unseres \\(b\\).<\/p>\n

Die Inverse zu \\(\\sigma(a)\\) (\\(a\\) ist ein Wort) ist \\(\\sigma^{-1}=\\nu_\\Sigma(i)\\) und gibt uns f\u00fcr eine Zahl \\(i\\) das dazugeh\u00f6rige Wort. Das 10. Wort w\u00e4re also \\(\\nu_\\Sigma(10) = abb\\).<\/p>\n

Damit ist \\(\\nu_{\\Sigma}\\) eine Standardnummerierung<\/strong> von \\(\\Sigma^{*}\\), also aller Worte \u00fcber dem Alphabet \\(\\Sigma\\).<\/p>\n

Antwort zum Lernziel<\/strong>: die Standardnummerierung \\(\\nu_{\\Sigma}\\) der Worte \u00fcber einem Alphabet \\(\\Sigma\\) ist eine bijektive Abbildung zwischen den nat\u00fcrlichen Zahlen \\(\\mathbb{N}\\) und den Worten aus \\(\\Sigma^{*}\\). Die Bijektivit\u00e4t ist wichtig damit wir einer Zahl eindeutig ein Wort und einem Wort eindeutig eine Zahl zuweisen k\u00f6nnen.<\/p>\n

Diese Zuweisung funktioniert aufgrund einer sog. Ordnungsfunktion \\(a\\) auf dem Alphabet \\(\\Sigma\\), welches jedem Zeichen aus den Alphabet eine eindeutige Nummer (Ordnungszahl) aus den nat\u00fcrlichen Zahlen zuordnet. Durch die nat\u00fcrliche Ordnung auf den nat\u00fcrlichen Zahlen \\(\\mathbb{N}\\) haben wir auch eine nat\u00fcrliche Ordnung auf den Elementen aus unserem Alphabet \\(\\Sigma\\), die wir vorher nicht hatten.<\/p>\n

Mit \\(\\sigma(a)\\) bekommen wir somit zu einem Wort \\(a\\) die zugeh\u00f6rige Ordnungszahl \\(i\\) und mit \\(\\nu_{\\Sigma}(i)\\) zu einer Zahl \\(i\\) das zugeh\u00f6rige Wort aus den Worten \u00fcber dem Alphabet \\(\\Sigma\\): \\(\\Sigma^{*}\\).<\/p>\n

Lernziel 2<\/h2>\n

Formulierung und Erl\u00e4uterung der Beziehung zwischen Zahlen- und Wortfunktionen<\/em><\/p>\n

Zun\u00e4chst noch einmal die Definition wann Wortfunktionen berechenbar sind:<\/p>\n

Eine\u00a0(ggf. partielle) Wortfunktion<\/strong>\u00a0\\(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

Das gleiche Spiel f\u00fcr Zahlenfunktionen.<\/p>\n

Eine\u00a0(ggf. partielle) Zahlenfunktion<\/strong>\u00a0\\(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

Kennen wir schon aus den alten Beitr\u00e4gen. Registermaschinen f\u00fcr Zahlen- und Turingmaschinen f\u00fcr Wortfunktionen. Langweilig. But wait, there’s more! Im Zusammenhang mit der Standardnummerierung hatten wir das noch nicht. Denn wir k\u00f6nnen Wortfunktionen durchaus mit Registermaschinen und Zahlenfunktionen mit Turingmaschinen berechnen.<\/p>\n

Man macht sich zun\u00e4chst noch einmal folgenden Zusammenhang klar: Unsere (\\(k\\)-steligen) Wortfunktionen, welche die Turingmaschinen (Mehrbandmaschinen mit \\(k\\) B\u00e4ndern) berechnen k\u00f6nnen, k\u00f6nnen auch auf Einbandmaschinen berechnet werden (Ihr erinnert euch: Spuren, Hilfssymbole, etc.<\/a>?). Wir k\u00f6nnen uns also auf die Betrachtung der Einbandmaschinen f\u00fcr die Berechnung der Wortfunktionen beschr\u00e4nken.<\/p>\n

Und hier kommt die Standardnummerierung ins Spiel: wollen wir eine Wortfunktion auf einer Registermaschine berechnen, geht das zun\u00e4chst nicht. Die Registermaschine rechnet ja mit Zahlen und nicht mit Worten. Und auch als Ausgabe bekommen wir eine Zahl und kein Wort. Aber hey! Wir k\u00f6nnen die Worte ja mit unserer Standardnummerierung eindeutig auf Zahlen und Zahlen eindeutig auf Worte abbilden. Damit gelingt es uns die Eingabeworte f\u00fcr unsere Turingmaschine in eine Zahl zu verwandeln, damit die Registermaschine zu f\u00fcttern und die Ausgabe dieser (die ja auch eine Zahl ist) wieder in ein Wort zu verwandeln.\u00a0<\/span><\/p>\n

Die Standardnummerierung erledigt das. Was uns hier noch fehlt ist die Umwandlung der Flussdiagramm der Turing- in eine passende Registermaschine. Das geschieht wie folgt:<\/p>\n