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. General Recursive Functions.

Section. Beyond Primitive Recursion: Universal Function for Primitive Recursive Functions.

Primitive recursive function symbols.

Arithmetization of primitive recursive function symbols. See also the module Mxpr.

Interpreter of primitive recursive function symbols. (2 bonus points) Define the interpreter of p.r. function symbols.

e • x = ?

Primitive recursive indices. See also the binary predicate $Prf (n, e)$ holding of well-formed p.r. indices defined in the module Mxpr.

Exercise. Find a well-formed p.r. index of the unary constant function $C_{1} (x) = 1$ , i.e. find the number $C_{1}$ such that

Prf (1, C_{1})

C_{1} • x = 1

C_{1} = ?

Exercise. Find a well-formed p.r. index of the unary constant function $C_{2} (x) = 2$ , i.e. find the number $C_{2}$ such that

Prf (1, C_{2})

C_{2} • x = 2

C_{2} = ?

Exercise. (1 point) Find a well-formed p.r. index of the addition function $x + y$ , i.e. find the number $Plus$ such that

Prf (2, Plus)

Plus • (x, y) = x + y

Plus = ?

Exercise. Find a well-formed p.r. index of the multiplication function $x \cdot y$ , i.e. find the number $Times$ such that

Prf (2, Times)

Times • (x, y) = x \cdot y

Times = ?

Exercise. (2 points) Find a well-formed p.r. index of the exponentiation function $x^{y}$ , i.e. find the number $Exp$ such that

Prf (2, Exp)

Exp • (x, y) = x^{y}

Exp = ?

Section. Exercises.

Exercise. Find a well-formed p.r. index of the summation function $\sum_{i = 0}^{n} i$ , i.e. find the number $Sum$ such that

Prf (1, Sum)

Sum • n = \sum_{i = 0}^{n} i

Sum = ?

Exercise. Find a well-formed p.r. index of the factorial function $n!$ , i.e. find the number $Fact$ such that

Prf (1, Fact)

Fact • n = n!

Fact = ?

Exercise. Find a well-formed p.r. index of the predecessor function $x ∸ 1$ , i.e. find the number $Pred$ such that

Prf (1, Pred)

Pred • x = x ∸ 1

Pred = ?

Exercise. (2 points) Find a well-formed p.r. index of the modified subtraction function $x ∸ y$ , i.e. find the number $Minus$ such that

Prf (2, Minus)

Minus • (x, y) = x ∸ y

Minus = ?