BuK/IIm10/BuK-Kreativaufgabe11 G1

Wiki-Quelltext dieser Seite.

Sei <math>h: S^{*} \rightarrow N_{0}</math> eine Gödelisierung von S*, d.h. h ist injektiv, total und berechenbar;
h(S*) ist entscheidbar und <math>h^{-1} : h(S^{*}) \rightarrow S*</math> ist berechenbar.

Dann können die Wörter aus S* vermöge h gödelgeordnet werden, so dass <math>w_{i} \prec w_{j} \Leftrightarrow
h(w_{i}) < h(w_{j})</math>, für alle <math>w_{i},w_{j} \in S^{*}</math> und <math>w_{i} \neq w_{j}</math>.

Die folgende µ-rekursive Funktion liefert die Folge der Gödelnummern <math>h(w_{0}), h(w_{1}), . . . </math>
in aufsteigender Form.

<math>g(1) = \mu f(n, i) = \begin{cases}
  \text{das kleinste } n \in N_{0}, \text{ mit } 1- p(0, n) = 0 & , \text{wenn so ein n existiert und } 1-p(0,m) \text{ für alle } m <= n \text{ definiert ist;} \\

  \text{undefiniert} & , \text{sonst}
\end{cases}</math>

Für <math>i \geq 1</math> gilt:

g(i + 1) = µf(n, i) =

  das kleinste <math>n \in N_{0}</math>, mit 1 - p(g(i) + 1, n) = 0, wenn

    (1) so ein n existiert und

    (2) 1 - p(g(i) + 1,m) für alle <math>m \leq n </math> definiert ist,

  undefiniert, sonst

Die zur Definition von g verwendete zahlentheoretische Funktion p ist

p(r, y) =

  1, wenn <math>y \geq r</math> und y ist Gödelnummer

  0, sonst

Illustrieren Sie die folgenden Aussagen durch den Einsatz selbst entwickelter Scheme-
Prozeduren. Wählen Sie exemplarisch <math> S = {a, b}</math> und die Verschlüsselung im 3er-System,
mit <math>a \rightarrow 1,  b \rightarrow 2</math> als Gödelisierung h mit <math>h(w) =
\Sigma ^{\|w\|-1}_{i=0} a_{i}*3^{i}</math> mit <math>a_{i} \in {1,2}</math>. Das Wort
aba erhält dann die Gödelnummer <math>h(aba) = 1*3^{2}+2*3^{1}+1*3^{0} = 16</math>. Nicht jede natürliche
Zahl ist Gödelnummer eines Wortes aus S*: Beispielsweise ist <math>10 = 1 * 3^{2} + 0 * 3^{1} + 1 * 3^{0}</math>
keine.

<math> p: N_{0} \times N_{0} \rightarrow {0,1}</math> 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
<math> \Sigma ^{n}_{i=0} a^{i}*3^{i}</math> mit <math>a_{i} \in {1,2}</math>
darstellbar sein.)

<math>g: N \rightarrow N_{0}</math> wächst streng monoton und ist total. (Hinweis: Verwenden Sie eine Scheme-
Prozedur zur Berechnung der ersten 10 Gödelnummern.)

Mit Hilfe der Funktion <math>k : N \rightarrow S^{*}, k(n) = h^{-1}(g(n))</math> 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 <math>k^{-1} : S^{*}  \rightarrow N</math> liefert somit auch wieder die Gödelisierung
mit <math>k^{-1}(w_{n}) = h(n)</math>.