Clausal Language (ver. 5.81.20, 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.

Remark. The abbreviation p.r. stands for primitive recursive.

Chapter. Primitive Recursive Functions.

Section. Primitive Recursive Functions.

Basic primitive recursive functions. See also the module Maux*.

Composition.

Primitive recursion.

Primitive recursive functions.

Example. Find a p.r. derivation of the ternary function

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

h (x, z, y) = ?

Addition is primitive recursive. (1 point) Find a p.r. derivation of the addition function $x + y$ .

Hint. Note that

0 + y = y

x + 1 + y = x + y + 1

x + y = ?

Subsection. Exercises.

Exercise. Find a p.r. derivation of the multiplication function $x \cdot y$ .

Hint. Note that

0 \cdot y = 0

(x + 1) \cdot y = x \cdot y + y

x \cdot y = ?

Exercise. (1 point) Find a p.r. derivation of the exponentiation function $x^{y}$ .

Hint. Recall that

x^{0} = 1

x^{y + 1} = x \cdot x^{y}

Rewrite the recurrences for the binary function

f (y, x) = x^{y}

f (y, x) = ?

x^{y} = ?

Subsection. Additional Problems.

Exercise. (1 bonus point) Find a 'short' p.r. derivation of the constant function

C_{256} (x) = 256

C_{256} (x) = ?

Exercise. Find a p.r. derivation of the summation function $\sum_{i = 0}^{n} i$ .

Hint. Recall that

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

\sum_{i = 0}^{n + 1} i = \sum_{i = 0}^{n} i + n + 1

Rewrite the recurrences for the binary function

f (n, m) = \sum_{i = 0}^{n} i

with the dummy second argument.

f (n, m) = ?

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

Exercise. Find a p.r. derivation of the factorial function $n!$ .

Hint. Recall that

0! = 1

(n + 1)! = (n + 1) \cdot n!

Rewrite the recurrences for the binary function

f (n, m) = n!

with the dummy second argument.

f (n, m) = ?

n! = ?

Exercise. Find a p.r. derivation of the predecessor function $x \dot{-} 1$ .

Hint. Note that

0 \dot{-} 1 = 0

x + 1 \dot{-} 1 = x

Rewrite the recurrences for the binary function

f (x, y) = x \dot{-} 1

with the dummy second argument.

f (x, y) = ?

x ∸ 1 = ?

Exercise. (1 bonus point) Find a p.r. derivation of the modified subtraction function $x \dot{-} y$ .

Hint. Note that

x \dot{-} 0 = x

x \dot{-} (y + 1) = x \dot{-} y \dot{-} 1

Rewrite the recurrences for the binary function

f (y, x) = x \dot{-} y

f (y, x) = ?

x ∸ y = ?