Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

1 Answer

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|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
add comment

Your Answer

 
discard

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.