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

2011-10-27T19:10:05Z

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

Answer by Andreas Blass for any given c.e.set has number M whose power bounds the corresponding elements of S?

2011-10-27T20:02:42Z

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

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

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

Answer by Andreas Blass for any given c.e.set has number M whose power bounds the corresponding elements of S?