Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursion Theorem and c.e. sets

  1. Jan 26, 2012 #1


    User Avatar
    Gold Member

    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.

    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.
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?