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

I have already proved that [itex]M[/itex] is infinite. A necessary and sufficient condition to prove that [itex]M[/itex] has no c.e. subset is that given any one-to-one computable function [itex]f[/itex] it follows that [itex]f(\omega) \nsubseteq M[/itex]. One way to demonstrate that this holds is to use the Recursion Theorem to show that there is some index [itex]x_0[/itex] such that [itex]\varphi_{x_0}=\varphi_{f(x_0)}[/itex] but [itex]x_0 < f(x_0)[/itex]. 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.

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Recursion Theorem and c.e. sets

Can you offer guidance or do you also need help?

**Physics Forums | Science Articles, Homework Help, Discussion**