Gödelisierung v_prim von Zeichenketten
2006-06-17 23:39
f0k
Hallo!
Ich hab mal 'ne Frage zur Folie 12 von Vorlesung 19 (nur im Informatiknetz).
Und zwar wird dort ein Alphabet mit drei Zeichen x_0, x_1, x_2 definiert und v_prim als Gödelisierung genommen. Dann gilt z.B. [img]http://mokrates.de/cgi-bin/texstring?v_%7Bprim%7D(x_1%20x_2%20x_0%20x_0)%20%3D%202%5E1%20%5Ccdot%203%5E2%20%5Ccdot%205%5E0%20%5Ccdot%207%5E1%20-1%20%3D%20125[/img]. Kurze Erklärung des Prinzips, wer nicht erst die Folien lesen will: Man geht Zeichen für Zeichen vor, nimmt als Basis immer eine Primzahl (beginnend bei 2 und dann immer die nächstgrößere) und als Exponent das, was unten am x steht - außer beim letzten Zeichen des Wortes, da addiert man noch 1 drauf auf den Exponenten. Am Ende zieht man 1 ab. [img]http://www.fb18.de/gfx/22.gif[/img]
Jetzt wird behauptet, v_prim sei dann eine Bijektion zwischen den Wörtern des Alphabetes und den natürlichen Zahlen, da zu jeder Zahl eine Primfaktorzerlegung existiert.
Die Zahl 2^4 - 1 = 15 beispielsweise entspricht meines Verständnisses nach aber keinem Wort, dass sich aus {x_0, x_1, x_2} bilden lässt.
Ich hab mal 'ne Frage zur Folie 12 von Vorlesung 19 (nur im Informatiknetz).
Und zwar wird dort ein Alphabet mit drei Zeichen x_0, x_1, x_2 definiert und v_prim als Gödelisierung genommen. Dann gilt z.B. [img]http://mokrates.de/cgi-bin/texstring?v_%7Bprim%7D(x_1%20x_2%20x_0%20x_0)%20%3D%202%5E1%20%5Ccdot%203%5E2%20%5Ccdot%205%5E0%20%5Ccdot%207%5E1%20-1%20%3D%20125[/img]. Kurze Erklärung des Prinzips, wer nicht erst die Folien lesen will: Man geht Zeichen für Zeichen vor, nimmt als Basis immer eine Primzahl (beginnend bei 2 und dann immer die nächstgrößere) und als Exponent das, was unten am x steht - außer beim letzten Zeichen des Wortes, da addiert man noch 1 drauf auf den Exponenten. Am Ende zieht man 1 ab. [img]http://www.fb18.de/gfx/22.gif[/img]
Jetzt wird behauptet, v_prim sei dann eine Bijektion zwischen den Wörtern des Alphabetes und den natürlichen Zahlen, da zu jeder Zahl eine Primfaktorzerlegung existiert.
Die Zahl 2^4 - 1 = 15 beispielsweise entspricht meines Verständnisses nach aber keinem Wort, dass sich aus {x_0, x_1, x_2} bilden lässt.