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. Primitive Recursive Definitions.

Subsection. Primitive Recursive Definitions.

Exercise. Show that primitive recursive functions are closed under iteration of unary functions.

Remark. Prove the claim for the special case in the following theory.

Show that if $f$ is a unary p.r. function then so is its iteration $f^{n} (x)$ defined by

f^{0} (x) = x

f^{n + 1} (x) = f f^{n} (x)

Proof.

f^{n} (x) = ?

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

Exercise. Show that primitive recursive functions are closed under monadic discrimination.

Remark. Prove the claim for the special case in the following theory.

Show that if $g$ and $h$ are p.r. functions then so is the function $f$ defined by

f (0, y) = g (y)

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

Proof.

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 _m.

Exercise. (1 point) Show that primitive recursive functions are closed under primitive recursive definitions with parameters.

Remark. Prove the claim for the special case in the following theory.

Show that if $g$ and $h$ are p.r. functions then so is the function $f$ defined by

f (y, 0, z) = g (y, z)

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

Proof.

f (y, x, z) = ?

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

Lemma. Primitive recursive functions are closed under primitive recursive definitions with parameters.

Exercise. (1 point) Show that primitive recursive functions are closed under parameterless primitive recursive definitions.

Remark. Prove the claim for the special case in the following theory.

Show that if $h$ is a p.r. function then so is the function $f$ defined by

f (0) = m

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

Proof.

f (x) = ?

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

Lemma. Primitive recursive functions are closed under parameterless primitive recursive definitions.

Theorem. Primitive recursive functions are closed under primitive recursive definitions.

Subsection. Examples of Primitive Recursive Functions.

Exercise. Show that the multiplication function $x \cdot y$ is primitive recursive.

x \cdot y = ?

[CL] Remark. From now on you can use the builtin function $x \cdot y$ .

Exercise. Show that the exponentiation function $x^{y}$ is primitive recursive.

x^{y} = ?

Exercise. Show that the summation function $\sum_{i = 0}^{n} i$ is primitive recursive.

\sum_{i = 0}^{n} i = ?

Exercise. Show that the predecessor function $x ∸ 1$ is primitive recursive.

x ∸ 1 = ?

Exercise. Show that the modified subtraction function $x ∸ y$ is primitive recursive.

x ∸ y = ?

[CL] Remark. From now on you can use the builtin function $x ∸ y$ .