BuK-Kreativaufgabe11 G1
Gödelisierung und µ-rekursive Funktionen
Aufgabe
Sei h: S^{*} \rightarrow N_{0} eine Gödelisierung von S^{*}, d.h. h ist injektiv, total und berechenbar. h(S*) ist entscheidbar und h^{-1} : h(S^{*}) \rightarrow S^{*} ist berechenbar.
Dann können die Wörter aus S^{*} vermöge h gödelgeordnet werden, so dass w_{i} \prec w_{j} \Leftrightarrow h(w_{i}) < h(w_{j}), für alle w_{i},w_{j} \in S^{*} und w_{i} \neq w_{j}.
Die folgende µ-rekursive Funktion liefert die Folge der Gödelnummern h(w_{0}), h(w_{1}), . . . in aufsteigender Form.
g(1) = \mu f(n, i) = \begin{cases} \text{das kleinste } n \in N_{0}, \text{ mit } 1- p(0, n) = 0 & , \text{wenn}\\ & \text{(1) so ein n existiert und}\\ & \text{(2) }1-p(0,m) \text{ f\"ur alle } m <= n \text{ definiert ist} \\ \text{undefiniert} & , \text{sonst} \end{cases}Für i \geq 1 gilt:
g(i + 1) = \mu f(n, i) = \begin{cases} \text{das kleinste }n \in N_{0} \text{, mit }1 - p(g(i) + 1, n) = 0 &\text{, wenn} \\ & \text{(1) so ein }n\text{ existiert und}\\ & \text{(2) }1 - p(g(i) + 1,m)\text{ f\"ur alle }m \leq n\text{ definiert ist}\\ \text{undefiniert} &\text{, sonst}\\ \end{cases}Die zur Definition von g verwendete zahlentheoretische Funktion p ist
p(r, y) =\begin{cases} 1 & \text{, wenn }y \geq r\text{ und }y\text{ ist G\"odelnummer}\\ 0 & \text{, sonst} \end{cases}Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme- Prozeduren. Wählen Sie exemplarisch S = {a, b} und die Verschlüsselung im 3er-System, mit a \rightarrow 1, b \rightarrow 2 als Gödelisierung h mit h(w) = \Sigma ^{\|w\|-1}_{i=0} a_{i}*3^{i} mit a_{i} \in \{1,2\}. Das Wort aba erhält dann die Gödelnummer h(aba) = 1*3^{2}+2*3^{1}+1*3^{0} = 16. Nicht jede natürliche Zahl ist Gödelnummer eines Wortes aus S^{*}: Beispielsweise ist 10 = 1 * 3^{2} + 0 * 3^{1} + 1 * 3^{0} keine.
p: N_{0} \times N_{0} \rightarrow \{0,1\} ist ein total berechenbares Prädikat. (Hinweis: Hierzu benötigen Sie eine Scheme-Prozedur für ein total berechenbares Prädikat, das feststellt, ob eine gegebene Zahl y Gödelnummer ist, d.h. y muss in der Form \Sigma ^{n}_{i=0} a^{i}*3^{i} mit a_{i} \in \{1,2\} darstellbar sein.)
g: N \rightarrow N_{0} wächst streng monoton und ist total. (Hinweis: Verwenden Sie eine Scheme-Prozedur zur Berechnung der ersten 10 Gödelnummern.)
Mit Hilfe der Funktion k : N \rightarrow S^{*}, k(n) = h^{-1}(g(n)) kann man das n-te Wort in der gödelgeordneten Folge der Wörter aus S^{*} bestimmen. k ist total und injektiv. Die zugehörige Umkehrfunktion k^{-1} : S^{*} \rightarrow N liefert somit auch wieder die Gödelisierung mit k^{-1}(w_{n}) = h(n).
Lösung
Die Lösung für die Funktion h lautet:
Die Umkehrung der Funktion h, also h^{-1}, lautet:
Um heruaszufinden ob eine Zahl eine gültige Gödelnummer zu dem gegebenen System ist, kann die Funktion h? verwendet werden:
Lösung für Funktion g
die zahlentheoretische Funktion p, ist nur eine Erweiterung von h? mit der zusätzlichen Bedingung, dass y größer gleich r sein muss:
Funktion k muss nicht extra implementiert werden, da diese aus h^{-1}(also hinvers) und g(n) besteht:
In Scheme sieht die Funktion k^{-1} so aus: