Equivalence result for Recursion Theorem

43 Views Asked by At

A corollary for the Recursion Theorem (Kleene) stands that for every recursive function $f$ there exists $n$ such that $W_{n} = W_{f(n)}$. That result is equivalent to the following one: for every r.e. set $A$ $(\exists n)[ W_{n} = \{x:<x,n> \in A\} ]$.

The author suggest as a hint for the proof to define $A_{n} = \{ x:<x,n> \in A \}$ and compare $\{A_{n}\}_{n \in \omega}$ with $\{W_{n}\}_{n \in \omega}$.

For the $\Rightarrow$ implication, I think we can define a function $$\psi (x,n) = \begin{cases} x & if <x,n> \in A \\ \uparrow & otherwise \end{cases}$$ so by the s-m-n Theorem, there is a 1:1 recursive function $f$ such that $\psi (x,n) = \varphi_{f(n)}(x)$. Now, as $f$ is recursive, there exists $n$ such that $W_{n} = W_{f(n)}$ which is equivalent to say that $W_{n} = dom(\varphi_{n}) = dom(\varphi_{f(n)})=\{ x | <x,n> \in A \}$. I am not quite sure if that argument is correct.

For the other implication I need some help.

1

There are 1 best solutions below

0
On BEST ANSWER

I don't see any problems with your implication. For the reciprocal, suppose $f$ is recursive. Let's define a recursively enumerable set $A$ by enumerating the domains of the computable functions $\varphi_{f(n)}$ simultaneously.

Every time we find out that a value $x$ is in the domain of some $\varphi_{f(n)}$, add $\langle x, n \rangle$ to $A$. This provides a recursive enumeration of $A$.

By construction, $A_n = W_{f(n)}$. By hypothesis there is $n$ with $W_n = A_n$.

Hope this makes sense.