Is below statement true?

$\forall L \in r.e. \,\, \, \exists f:\{0,1\}^* \longrightarrow \{0,1\}^* \, , \exists x\in \{0,1\}^* \; s.t \, \, L = \{x,f(x),f(f(x)),..\} $ .

My guess is no and I tried to prove this with cantor diagonalization.If we suppose that $L_i$ has this property so ‎$‎L_i = ‎\{x_i,f_i(x_i),f_i(f_i(x_i)),...\}‎$,now I want to make $L$ that doesn't have above property $L = \{x_k \in \{0,1\}^* | \nexists i \; x_k \in L_i\}$,How can I prove that it is in $r.e$?

  • $\begingroup$ What does this property mean in English? (That will also help you come up with a better title.) If you're stuck disproving the claim, have you tried proving it instead? Observing where your attemps fail will help you make better attempts on the other side! $\endgroup$ – Raphael Jan 29 '17 at 13:29
  • 2
    $\begingroup$ Hint: Recall that for every L ∈ RE there is a computable function $g : \mathbb{N} \to \Sigma^*$ so that $L = \{ g(i) \mid i \in \mathbb{N} \}$. $\endgroup$ – Raphael Jan 29 '17 at 13:31
  • $\begingroup$ I know that every $L \in r.e$ is a range of a computable function,but my question is different! $\endgroup$ – haleh Jan 29 '17 at 13:54
  • $\begingroup$ Yes. I assume that this is a homework exercise, in which case you should always assume that the solution is not too much more than combining facts from class in a few steps. $\endgroup$ – Raphael Jan 29 '17 at 16:53
  • $\begingroup$ I'm guessing $f$ has to be computable. $\endgroup$ – Yuval Filmus Jan 29 '17 at 17:25

Since $L$ is r.e., there is a computable program $\varphi$ that enumerates it, say in the order $$ x_1,x_2,x_3,x_4,\ldots $$ Suppose I give you $x_n$, can you find $x_{n+1}$ using $\varphi$? Can you use this to solve your question?

| cite | improve this answer | |
  • $\begingroup$ yeah,you are right! Can we say that its inverse is true? $\endgroup$ – haleh Jan 29 '17 at 18:59
  • $\begingroup$ What do you think? Make a conjecture and try to prove it. $\endgroup$ – Yuval Filmus Jan 29 '17 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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