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

Section. Arithmetization of Computation Model.

Subsection. Arithmetization of Reductions. See also the modules Mxgr and Mxrd.

Exercise. Show that there is a binary primitive recursive predicate $t{⊳}_1^{•}r$ which is arithmetization of the one-step reduction relation.

Exercise. Show that there is a primitive recursive predicate $\mathrm{Computation}\left(s\right)$ which holds for (the codes of) computation sequences.

Remark. Note that we require that the last element of a computation sequence is a numeral.

Subsection. Kleene Normal Form Theorem.

Exercise. (5 points) Show that there is a unary primitive recursive function $\mathrm{U}$ and a ternary primitive recursive predicate ${\mathrm{T}}_1$ such that for every unary partial recursive function $\mathrm{f}$ there exists a number $e$ such that the following holds for all numbers $x$:

Exercise. Show that there a $4$-ary primitive recursive predicate ${\mathrm{T}}_2$ such that for every binary partial recursive function $\mathrm{f}$ there exists a number $e$ such that the following holds for all numbers $x_1$ and $x_2$:

Exercise. (1 point) Show that there a $5$-ary primitive recursive predicate ${\mathrm{T}}_3$ such that for every ternary partial recursive function $\mathrm{f}$ there exists a number $e$ such that the following holds for all numbers $x_1$, $x_2$ and $x_3$:

Section. Recursive Indices.

Some recursive indices.

Notation.

Subsection. Effective Operations on Recursive Indices.

Exercise. Show that there is a primitive recursive function ${\mathbf{\varnothing }}^{\mathbf{(}n\mathbf{)}}$ such that for every $n\geqq 1$ the number ${\mathbf{\varnothing }}^{\mathbf{(}n\mathbf{)}}$ is a well-formed recursive index of the $n$-ary nowhere defined partial function ${\mathrm{\varnothing }}^{\mathrm{(}n\mathrm{)}}$, i.e.

for every $n\geqq 1$.

Exercise. Show that there is a binary primitive recursive function $e^{\mathbf{(}n\mathbf{)}}$ such that for every $n\geqq 1$ the number $e^{\mathbf{(}n\mathbf{)}}$ is a well-formed recursive index of the same partial recursive function as the number $e$, i.e.

for every $n\geqq 1$.

Hint. Define the function with the help of the binary primitive recursive predicate $\mathrm{Rf}(n,e)$ from the module $\mathrm{Mxgr}$.

Exercise. (1 point) Show that there is a binary primitive recursive parametric function $e\mathbf{/}x$ such that

Exercise. (1 point) Show that there is a ternary primitive recursive function ${\mathrm{s}}_3^2\mathrm{(}e\mathrm{,}{x}_1\mathrm{,}{x}_2\mathrm{)}$ such that

This is the Kleene's s-m-n theorem for the case $m=2$ and $n=3$.