Berechenbarkeitstheorie

Aufgabe 1

1 (i) Beschreiben Sie die 1-stelligen Funktionen f(x_{1}), die die folgenden RM-Programmen berechnen.

a) ; I_{0} D(1, 2) ; I_{1} S(1) ; I_{2} D(1, 1) ; I_{3} S(2)  b) ; I_{0} D(1, 3) ; I_{1} S(2) ; I_{2} D(2, 1) ; I_{3} S(1)

(ii) Konstruieren Sie ein Programm, das zeigt, daß das Prädikat “x_{1} ≤ x_{2}” berechenbar ist.

2 Zu zeigen ist, daß die Funktionen E, H primitiv rekursiv (p.r.) sind, wobei:

a) E ist definiert durch

E(x) = \{ \begin{matrix}0 & wenn x gerade ist; \\ 1 & wenn x ungerade ist. \end{matrix}

b) H ist definiert durch

H(x) = \{ \begin{matrix}0 & wenn x/2 gerade ist; \\ 1 & wenn (x − 1)/2 ungerade ist. \end{matrix}

3 Sei g p.r. Definieren Sie durch Rekursion

\begin{aligned}f(0, x) & = & g(x) \\ f(n + 1, x) & = & f(n, f(n, x)) \end{aligned}

Ist f p.r.?