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.

Chapter. Primitive Recursive Functions. See [1].

Section. Pairing Function and Arithmetization.

Subsection. Cantor Pairing Function.

Exercise. Show that the modified Cantor pairing function $⟨ x, y ⟩$ is primitive recursive.

⟨ x, y ⟩ = ?

Basic properties of the pairing function. We have

⟨ x_{1}, x_{2} ⟩ = ⟨ y_{1}, y_{2} ⟩ \to x_{1} = y_{1} \land x_{2} = y_{2}

x < ⟨ x, y ⟩ \land y < ⟨ x, y ⟩

x = 0 \lor \exists y \exists z x = ⟨ y, z ⟩

Ordering properties of the pairing function. We have

⟨ x_{1}, x_{2} ⟩ ≦ ⟨ y_{1}, y_{2} ⟩ \leftrightarrow x_{1} + x_{2} < y_{1} + y_{2} \lor x_{1} + x_{2} = y_{1} + y_{2} \land x_{1} ≦ y_{1}

⟨ x_{1}, x_{2} ⟩ < ⟨ y_{1}, y_{2} ⟩ \leftrightarrow x_{1} + x_{2} < y_{1} + y_{2} \lor x_{1} + x_{2} = y_{1} + y_{2} \land x_{1} < y_{1}

Exercise. Show that the first projection $π_{1} (x)$ of the pairing function is primitive recursive.

π_{1} (x) = ?

Exercise. Show that the second projection $π_{2} (x)$ of the pairing function is primitive recursive.

π_{2} (x) = ?

Exercise. Show that the unary iteration of second projection is a p.r. function.

π_{2}^{n} (x) = ?

Exercise. (2 points) The Fibonacci function ${fib}_{n}$ has the following recursive definition:

{fib}_{0} = 0

{fib}_{1} = 1

{fib}_{n + 2} = {fib}_{n + 1} + {fib}_{n}

Derive Fibonacci sequence as a p.r. function by showing that the function

Twofib (n) = ⟨ {fib}_{n}, {fib}_{n + 1} ⟩

is primitive recursive.

Twofib (n) = ?

{fib}_{n} = ?

Subsection. Arithmetization of Tuples.

Exercise. (1 point) Consider the binary predicate $Tuple (n, x)$ which holds if the number $x$ is the code of an $n$ -tuple. Note that this includes the case when $n = 0$ or $n = 1$ . Show that the predicate is primitive recursive.

Tuple (n, x) \leftrightarrow ?

Exercise. (1 point) Consider the ternary function ${[x]}_{i}^{n}$ which generalizes the projection functions $π_{1} (x)$ and $π_{2} (x)$ to accept tuples, i.e. the application ${[x]}_{i}^{n}$ yields the $i$ -th element of the $n$ -tuple $x$ provided $1 ≦ i \land i ≦ n$ . Show that the function is primitive recursive.

{[x]}_{i}^{n} = ?

******************************************************************************
********************************* DEBUGGING **********************************
******************************************************************************

Test_fun (x) = ?

Itfa (0, a) = a

Itfa (n + 1, a) = Itfa (n, (n, Test_fun (n)), a)

Itf (n) = Itfa (n, 0)

Test_pred (x) \leftrightarrow ?

Itpa (0, a) = a

Itpa (n + 1, a) = Itpa (n, n, a) \leftarrow Test_pred (n)

Itpa (n + 1, a) = Itpa (n, a) \leftarrow \neg Test_pred (n)

Itp (n) = Itpa (n, 0)