0
$\begingroup$

The problem I'm trying to solve is to prove that there are infinite indices $e \in \mathbb N_0$ such that $\varphi_e = \varphi_{e+1}$.

The fact that there exists one such $e$ is trivial, as the fixed-point theorem or the recursion theorem immediately gives us such an $e$, but I'm having trouble justifying why there is an infinite amount of such indices. I also tried to work with functions such as $f(x) = x + k$, but this did not lead me anywhere. I would certainly appreciate a hint in the right direction!

Improve this question
$\endgroup$
2
  • $\begingroup$ induction, modifying the fixed-point function appropriately at each step? $\endgroup$
    – Neal Young
    Commented Sep 23 at 15:21
  • 2
    $\begingroup$ defining $\varphi_e$ in the question itself would make this question readable for a general audience. $\endgroup$
    – kodlu
    Commented Sep 24 at 14:50

1 Answer 1

Reset to default
1
$\begingroup$

The recursion theorem actually gives infinitely many fixed points. Recall the outline of the argument is that if we let $h$ be a computable function such that for all $e,$ $\varphi_{h(e)} = \varphi_{\varphi_e(e)}$ (where the right side diverges on all inputs if $\varphi_e(e)\uparrow$), and then fix an $e$ such that $\varphi_e = f\circ h,$ then $$\varphi_{h(e)} = \varphi_{\varphi_e(e)} = \varphi_{f(h(e))}$$ so $h(e)$ is a fixed point. But by the padding lemma, there are infinitely many $e$ such that $\varphi_e= f\circ h,$ and thus, since the natural choice of $h$ is injective, each gives a distinct fixed point $h(e).$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.