# Recursion Theorem and c.e. sets

1. Jan 26, 2012

### jgens

Let $\varphi_e$ denote the p.c. function computed by the Turing Machine with code number $e$. Given $M=\{x : \neg(y<x)[\varphi_y=\varphi_x]\}$ prove that $M$ is infinite and contains no infinite c.e. subset.

I have already proved that $M$ is infinite. A necessary and sufficient condition to prove that $M$ has no c.e. subset is that given any one-to-one computable function $f$ it follows that $f(\omega) \nsubseteq M$. One way to demonstrate that this holds is to use the Recursion Theorem to show that there is some index $x_0$ such that $\varphi_{x_0}=\varphi_{f(x_0)}$ but $x_0 < f(x_0)$. I am having trouble doing this however and was wondering is someone here could help.

I think that this is the right way to approach the problem since the text suggested we use the Recursion Theorem to tackle it.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted