Moin Leute
Bei der Aufgabe 3.2 stehe ich aufm Schlauch ich hab mir im Skript die gödelisierung angeguckt aber werde daraus nich schlau.
Auf Seite 45 oben steht ja wie man vorgeht aber ich weiss nicht was das i bedeuten soll und wie man damit dann auf das Wort a2a3 als beispiel kommt kann mir das mal jemand an diesem Beispiel zeigen wie ich die gödelnummer dafür bekomme?

Hab zwar das Skript nicht zur Hand, aber das Konzept
kenn ich noch und manchmal ist es ja gerade hilfreich,
die Grundidee verstanden zu haben. Dann gehts vielleicht
mit der formalen Definition im Skript besser.

Also Gödelisierung war im Prinzip einfach,
dass man jedem Wort einer Sprache (=Menge von Wörtern)
eine natürliche Zahl zuweist.

So kann man ja alle Wörter lexikographisch (?)
ordnen ( a < b < aa < ab < ba < aba ….)
und so einfach jedem Wort die Position zuordnen.
Die Funktion, die das macht, ist dann eine
Gödelisierung.

So kann man ja alle Wörter lexikographisch (?)
ordnen ( a < b < aa < ab < ba < aba ….)

Das ist die lexikalische Ordnung, nicht lexikographisch.


Das i ist der Index für die Buchstaben im Wort. Der gibt also an, welche Stelle gemeint ist. m-k (der Index von i) gibt an, dass quasi "von hinten" im Wort angefangen werden soll zu zählen.

Ich weiß nicht, auf welches Beispiel du dich beziehst, aber nehmen wir an, du hast folgendes Alphabet: {a1, a2, a3, a4} und ein Wort a2a4a3. Es bietet sich an eine 4-adische Darstellung wählen. Dann ergibt sich folgende Gödelisierung:

[img]http://mokrates.de/cgi-bin/texstring?v_%7B4-adic%7D%20%3D%203%5Ccdot%204%5E0%20%2B%204%5Ccdot%204%5E1%20%2B%202%5Ccdot%204%5E2%20%3D%203%2B16%2B32%20%3D%2051[/img]