MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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 '11 at 19:58
HMM,The question is so trivial,that I am embarrassed now to have asked it. – XL _at_China Oct 28 '11 at 2:19
up vote 1 down vote accepted

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).

share|cite|improve this answer
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 _at_China Oct 28 '11 at 2:25
The formula should be $\psi = \Sigma_0^{\infty}a_n x^n$ – XL _at_China Oct 28 '11 at 18:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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