## any given c.e.set has number M whose power bounds the corresponding elements of S?

For S ,any given c.e.set,does there exist a M (integer) and a partially computable function outputing every element of S the c.e.set ,such that $\forall x\in S,\exists n x=f(n)$ and $x=f(n)\leq M^n$?.

-
Since you do not require $f$ to be total, the restriction of the identity function to $S$ will do (with $M = 2$). – François G. Dorais Oct 27 2011 at 19:58
HMM,The question is so trivial,that I am embarrassed now to have asked it. – XL Oct 28 2011 at 2:19

## 1 Answer

Yes, even with $M=2$. Start with any partial recursive function that enumerates $S$ and "slow it down" so that it won't produce output $x$ until after $\log_2 x$ steps. With more delay, you can ensure, for example, that $f(n)\leq n$ for all $n$.

More formally, if $S=\{x:(\exists y)\ R(x,y)\}$, and if $\langle,\rangle$ is a reasonable pairing function, then define $f(n)$ to be $x$ if, for some $y$, $n=\langle x,y\rangle$ and $R(x,y)$ (and $f(n)$ is undefined otherwise).

-
 Yes,It seems the question is too trivial.But if we form the power series $\psi=\sigma_0^{\infty} a_n x^n$,the function $\psi$ converge on disc of complex plane,is it automorphic function ? – XL Oct 28 2011 at 2:25 The formula should be $\psi = \Sigma_0^{\infty}a_n x^n$ – XL Oct 28 2011 at 18:32