FB18 - Das Forum für Informatik

fb18.de / Bachelorstudieng / PM Formale Informatik

Gödelisierung v_prim von Zeichenketten

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.

Re: Gödelisierung v_prim von Zeichenketten 2006-06-18 15:03
georg
Da würde ich dir recht geben. Für ein endliches
Alphabet ist die Gödelisierung zwar injektiv, aber
surjektiv wäre sie nur für eine unendliche Menge
von Symbolen.

Edit: s/"u/ü/ [img]http://www.fb18.de/gfx/7.gif[/img]