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.

Section. General Recursive Functions.

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

Subsection. Arithmetization..

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

Interpreter of primitive recursive function symbols.

Subsection. Primitive Recursive Indices.

Subsubsection. Effective Operations on Primitive Recursive Indices.

Exercise. Define the p.r. function ${\mathbf{C}}_m$ such that

Exercise. (1 point) Define the binary p.r. function ${\mathbf{C}}_m^n$ such that for every $n\geqq 1$:

Exercise. Define a p.r. function $\mathbf{Iter}\left(e\right)$ such that

This means that if $e$ is a p.r. index of a unary function then $\mathbf{Iter}\left(e\right)$ is a p.r. index of its unary iteration.

Exercise. (1 point) Find a well-formed p.r. index of $x+y$ which corresponds to the p.r. derivation of addition as an iteration of the successor function. Define the index with the help of $\mathbf{Iter}\left(e\right)$.

Exercise. Define a p.r. function $\mathbf{Rec0}\mathrm{(}m\mathrm{,}e\mathrm{)}$ such that

This means that if $\mathrm{m}$ is a constant and $e$ is a p.r. index of a binary function $\mathrm{h}(x,a)$ then $\mathbf{Rec0}\mathrm{(}m\mathrm{,}e\mathrm{)}$ is a p.r. index of the unary function $\mathrm{f}\left(x\right)$ defined by following parameterless primitive recursion:

Exercise. (1 point) Find a well-formed p.r. index of $\sum _{\mathrm{i}=0}^n\mathrm{i}$ which corresponds to the derivation of the summation function by parameterless recursion. Define the index with the help of $\mathbf{Rec0}\mathrm{(}m\mathrm{,}e\mathrm{)}$.

Exercise. Find a well-formed p.r. index of $x\dot{-}1$ which corresponds to the derivation of the predecessor function by parameterless recursion. Define the index with the help of $\mathbf{Rec0}\mathrm{(}m\mathrm{,}e\mathrm{)}$.

Exercise. (2 points) Find a well-formed p.r. index of $x\dot{-}y$ which corresponds to the p.r. derivation of modified subtraction as an iteration of the predecessor function. Define the index with the help of $\mathbf{Iter}\left(e\right)$.

Exercise. Define the binary parametric function $e\mathbf{/}x$ such that

as a p.r. function.

Exercise. (bonus 2 points) Prove the Kleene's s-m-n theorem for the case $m=2$ and $n=3$ by providing a ternary p.r. function ${\mathrm{s}}_3^2\mathrm{(}e\mathrm{,}{x}_1\mathrm{,}{x}_2\mathrm{)}$ such that