# Can every r.e. set be obtained by repeated function application?

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$?

• 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! – Raphael Jan 29 '17 at 13:29
• 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} \}$. – Raphael Jan 29 '17 at 13:31
• I know that every $L \in r.e$ is a range of a computable function,but my question is different! – haleh Jan 29 '17 at 13:54
• 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. – Raphael Jan 29 '17 at 16:53
• I'm guessing $f$ has to be computable. – 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?