Recursion Theory

To be updated.

• A set $A \subseteq \mathbb{N}$ is recursive if its characteristic function is computable, noted as $A \in \mathcal{R}$
• A set $A \subseteq \mathbb{N}$ is recursively enumerable if its semi-characteristic function is computable, noted as $A \in \mathcal{RE}$

Example. Justify the following sets whether they belong to $\mathcal{R}$

• $A = \{ \mathsf{pair}(max(1000,k),n) | \varphi_n(n) \textit{ halts in } k \textit{ steps} \}$
• $B = \{ \mathsf{pair}(min(1000,k),n) | \varphi_n(n) \textit{ halts in } k \textit{ steps} \}$

$A \in \mathcal{R}$. Given an input $y$, $n=\mathsf{proj2}(y)$, then $\varphi_n(n)$ halts either within 1000 steps, or $\mathsf{proj1}(y)$ steps, which can be computed.

$B \notin \mathcal{R}$. By contradiction, assume $V_B$ is a verifier. Then We can write a verifier also for $\mathsf{K}$ $$V_{\mathsf{K}} = \begin{cases} 1 & \textit{if } V_B(\mathsf{pair}(y,n))=1 \textit{ for some } 0 \leqslant y \leqslant 1000 \\ 0 & o.w. \end{cases}$$ And $\mathsf{K} \notin \mathcal{R}$ due to diagonalization argument. The trick lies in $A$ and $B$ is that $A$ records the halting step of functions taking over 1000 steps, but $B$ is not.

Appendix

• $\pair (n,m) = m + \frac{(n+m)(n+m+1)}{2}$
• $\projl(\pair(n,m)) = n$