Clausal Language (ver. 5.81.21, by P.J. Voda, J. Komara, J. Kluka)

Literature.

[1] J. Komara. Recursive Functions. Downloadable lecture notes available through the web page of the course.
[2] J. Komara and P. J. Voda. Lecture Notes in Theory of Computability. 2001.
[3] J. Komara and P. J. Voda. Metamathematics of Computer Programming. 2001.
[4] I. Korec. Úvod do teórie algoritmov. Skriptá MFF UK, 1981.

[CL] CL-TeX.

Chapter. Primitive Recursive Functions.

Section. Recursion with Parameter Substitution.

Subsection. Recursion with Parameter Substitution: Case $k = 1$ and One Parameter.

Exercise. (3 bonus points) Show that if $g (y)$ , $h (x, z, y)$ and $s (x, y)$ are all primitive recursive then so is $f (x, y)$ defined by

f (0, y) = g (y)

f (x + 1, y) = h (x, f (x, s (x, y)), y)

Hint. Derive $f (x, y)$ as a p.r. function with the help of its course of values function $\overline{f} (x, y)$ :

\overline{f} (0, y) = f (0, y), 0

\overline{f} (x + 1, y) = f (x + 1, y), \overline{f} (x, s (x, y))

Proof.

Selector for recursive arguments. Show that the selector function $x_{i} (x)$ is primitive recursive.

x_{i} (x) = ?

Selector for parameters. Show that the selector function $y_{i} (x, y)$ is primitive recursive.

y_{i} (x, y) = ?

Partial course of values sequence. Show that the auxiliary ternary function $\overline{f} (x, y) [i ..)$ such that

i ≦ x \to \overline{f} (x, y) [i ..) = \overline{f} (x_{i} (x), y_{i} (x, y))

is primitive recursive.

\overline{f} (x, y) [i ..) = ?

Course of values function. Show that the function $\overline{f} (x, y)$ is primitive recursive.

\overline{f} (x, y) = ?

Final step. Show that the function $f (x, y)$ is primitive recursive.

f (x, y) = ?

[CL] Remark. You can test your solution by interpreting the theory. Choose non-local interpretation.

Subsubsection. Contraction of Parameters.

Exercise. Show that if $g (y_{1}, y_{2})$ , $h (x, z, y_{1}, y_{2})$ , $s_{1} (x, y_{1}, y_{2})$ and $s_{2} (x, y_{1}, y_{2})$ are all primitive recursive then so is $f (x, y_{1}, y_{2})$ defined by

f (0, y_{1}, y_{2}) = g (y_{1}, y_{2})

f (x + 1, y_{1}, y_{2}) = h (x, f (x, s_{1} (x, y_{1}, y_{2}), s_{2} (x, y_{1}, y_{2})), y_{1}, y_{2})

Hint. Derive the function as primitive recursive with the help of its parameter contraction function $⟨ f ⟩ (x, y)$ :

⟨ f ⟩ (x, ⟨ y_{1}, y_{2} ⟩) = f (x, y_{1}, y_{2})

Proof.

⟨ f ⟩ (x, y) = ?

f (x, y_{1}, y_{2}) = ?

[CL] Remark. You can test your solution by interpreting the theory. Choose non-local interpretation and set component identifier suffix to the string _cp

Subsubsection. Case Analysis.

R_{*} (x, y) = 1 \leftarrow R (x, y)

R_{*} (x, y) = 0 \leftarrow \neg R (x, y)

Exercise. Show that if $g (y)$ , $h_{1} (x, z, y)$ , $h_{2} (x, z, y)$ , $s_{1} (x, y)$ , $s_{2} (x, y)$ and $R (x, y)$ are all primitive recursive then so is $f (x, y)$ defined by

f (0, y) = g (y)

f (x + 1, y) = h_{1} (x, f (x, s_{1} (x, y)), y) \leftarrow R (x, y)

f (x + 1, y) = h_{2} (x, f (x, s_{2} (x, y)), y) \leftarrow \neg R (x, y)

Proof.

h (x, z, y) = ?

s (x, y) = ?

f (x, y) = ?

[CL] Remark. You can test your solution by interpreting the theory. Choose non-local interpretation and set component identifier suffix to the string _ca

Subsection. General Case.

Theorem. Primitive recursive functions are closed under recursion with parameter substitution.