Chapter. Partial Recursive Functions.

Section. Arithmetization of Computation Model.

Subsection. Kleene's Normal Form Theorem.

Kleene's T-predicate for unary partial recursive functions. 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$:

Section. Recursively Decidable, Semidecidable and Undecidable Problems.

Subsection. Semidecidable Problems.

Definition. A unary predicate $\mathrm{R}$ is said to be

• recursively semidecidable, or simply semirecursive, if it is the domain of a partial recursive function,

• existential projection of recursive predicate, if there is a binary recursive predicate $\mathrm{Q}$ such that

  $$\mathrm{R}\left(x\right)\leftrightarrow \exists y\mathrm{Q}(y,x)$$

• recursively enumerable if it is empty or the range of a recursive function.

Subsubsection. Post's Theorem.

Exercise. (2 points) Prove Post's theorem for semirecursive predicates:

• a predicate $\mathrm{R}$ is recursive iff both $\mathrm{R}$ and $\neg \mathrm{R}$ are semirecursive predicates.

Remark. Prove the claim for the special cases in the next two theories.

Exercise. Suppose that $\mathrm{R}\left(x\right)$ is a recursive predicate. Define a partial recursive function $\mathrm{f}\left(x\right)$ such that

Exercise. Suppose that ${\mathrm{f}}_1\left(x\right)$ and ${\mathrm{f}}_2\left(x\right)$ are partial recursive functions such that

Let $\lceil {\mathit{f}}_1\rceil$ and $\lceil {\mathit{f}}_2\rceil$ be indices of ${\mathrm{f}}_1\left(x\right)$ and ${\mathrm{f}}_2\left(x\right)$, respectively. Define $\mathrm{R}\left(x\right)$ as a recursive predicate.

Exercise. (2 points) Prove Post's theorem for existential projections of recursive predicates:

• a predicate $\mathrm{R}$ is recursive iff both $\mathrm{R}$ and $\neg \mathrm{R}$ are existential projections of recursive predicates.

Remark. Prove the claim for the special cases in the next two theories.

Exercise. Suppose that $\mathrm{R}\left(x\right)$ is a recursive predicate. Define a recursive predicate $\mathrm{Q}(y,x)$ such that

Exercise. Suppose that ${\mathrm{Q}}_1(y,x)$ and ${\mathrm{Q}}_2(y,x)$ are recursive predicates such that

Define $\mathrm{R}\left(x\right)$ as a recursive predicate.

Exercise. (2 points) Prove Post's theorem for recursively enumerable predicates:

• a predicate $\mathrm{R}$ is recursive iff both $\mathrm{R}$ and $\neg \mathrm{R}$ are recursively enumerable predicates.

Remark. Prove the claim for the special cases in the next two theories.

Exercise. Suppose that $\mathrm{R}\left(x\right)$ is a recursive predicate. Assume further that $\mathrm{R}$ holds for the number ${\mathit{x}}_0$. Define a recursive function $\mathrm{f}\left(y\right)$ such that

Exercise. Suppose that ${\mathrm{f}}_1\left(x\right)$ and ${\mathrm{f}}_2\left(x\right)$ are recursive functions such that

Define $\mathrm{R}\left(x\right)$ as a recursive predicate.

Subsubsection. Alternative Characterization of Semidecidability.

Exercise. (2 points) Prove the following theorem:

• a predicate $\mathrm{R}$ is semirecursive iff it is an existential projection of a recursive predicate.

Remark. Prove the claim for the special cases in the next two theories.

Exercise. Suppose that $\mathrm{f}\left(x\right)$ is a partial recursive function such that

Let $\lceil \mathit{f}\rceil$ be an index of $\mathrm{f}\left(x\right)$. Define a recursive predicate $\mathrm{Q}(y,x)$ such that

Exercise. Suppose that $\mathrm{Q}(y,x)$ is a recursive predicate such that

Define a partial recursive function $\mathrm{f}\left(x\right)$ such that

Exercise. (2 points) Prove the following theorem:

• a predicate $\mathrm{R}$ is semirecursive iff it is a recursively enumerable predicate.

Reamrk. Prove the claim for the special cases in the next two theories.

Exercise. Suppose that $\mathrm{f}\left(x\right)$ is a partial recursive function such that

Let $\lceil \mathit{f}\rceil$ be an index of $\mathrm{f}\left(x\right)$. Suppose further that $\mathrm{R}$ holds for the number ${\mathit{x}}_0$. Define a recursive function $\mathrm{g}\left(z\right)$ such that

Exercise. Suppose that $\mathrm{f}\left(y\right)$ is a recursive function such that

Define a partial recursive function $\mathrm{g}\left(x\right)$ such that

Exercise. (2 points) Prove the following theorem:

• a predicate $\mathrm{R}$ is an existential projection of a recursive predicate iff it is a recursively enumerable predicate.

Remark. Prove the claim for the special cases in the next two theories.

Exercise. Suppose that $\mathrm{Q}(y,x)$ is a recursive predicate such that

Suppose further that $\mathrm{R}$ holds for the number ${\mathit{x}}_0$. Define a recursive function $\mathrm{f}\left(z\right)$ such that

Exercise. Suppose that $\mathrm{f}\left(y\right)$ is a recursive function such that

Define a recursive predicate $\mathrm{Q}(y,x)$ such that