Zeigen Sie mit den Normalschemata, dass die folgende Funktion ite (C, T, E) primitiv rekursiv ist:

Question

Aufgabe:

Zeigen Sie mit den Normalschemata, dass die folgende Funktion ite \( (C, T, E) \) primitiv rekursiv ist:
\( \text { ite }(C, T, E)=\left\{\begin{array}{ll} T & , \text { falls } C \neq 0 \\ E & , \text { falls } C=0 \end{array}\right. \)

Frage:

Ich verstehe fast überhaupt nicht wie ich hier vorgehen soll. Ich habe das jetzt so verstanden, dass ich die beiden Fälle, also C = 0 und C ≠ 0, irgendwie mit 0 und n+1 darstellen soll. Würde das dann quasi so aussehen?:

ite(0, T, E) = E

ite(n+1, T, E) = T, ite(n, T, E)

Ist wahrscheinlich falsch, aber der einzige Ansatz den ich habe.

Answer 1

\(\begin{aligned}\operatorname{ite}(0,T,E) &= \operatorname{id}_2^2(T,E)\\\operatorname{ite}(n+1,T,E) &= \operatorname{id}_3^4(n, \operatorname{ite}(n,T,E), T,E)\end{aligned}\)

Laut Normalschema der primitiven Rekursion ist \(f:\mathbb{N}^m\to \mathbb{N}\) primitiv rekursiv, wenn es primitiv rekursive Funktionen \(g:\mathbb{N}^{m-1}\to\mathbb{N}\) und \(h:\mathbb{N}^{m+1}\to\mathbb{N}\) gibt, so dass

        \(\begin{aligned}\phantom{ =\,}&f(0,x_1,\dots,x_{m-1}) = g(x_1,\dots,x_{m-1})\end{aligned}\)

und

    \(\begin{aligned}&f(n+1,x_1,\dots,x_{m-1})\\ =\,& h(n, f(n,x_1,\dots,x_{m-1}),x_1,\dots,x_{m-1})\end{aligned}\)

für alle \(n,x_1,\dots,x_{m-1}\in \mathbb{N}\) ist.

Laut Definition sind die Projektionen

        \(\operatorname{id}_k^m:\ \mathbb{N}^m\to\mathbb{N},\ (x_1,\dots,x_m)\mapsto x_k\)

primitiv rekursiv.