Can every computable number be written as a limit of a termwise-definable sequence?

86 Views Asked by At

I should define some terms. We'll start with some base set of functions/operations $\mathcal{F}\subset \mathbb{R}^\mathbb{R}\cup\mathbb{R}^{\mathbb{R}\times\mathbb{R}}$. A sequence $s_n$ is termwise definable if it can be written in terms of operations from $\mathcal{F}$ (applied termwise), constant integer-valued sequences, and the identity sequence $n\to n$. So for example, if we take $\mathcal{F} = \{+,\cdot\}$, then the set of termwise-definable sequences is simply the polynomials with integer coefficients. If $\mathcal{F} =\{+,\cdot,\div\}$, then the termwise-definable sequences are the rational sequences over $\mathbb{Q}$.

My question is, can one find a finite set of computable functions $\mathcal{F}$ such that any computable number $x$ can be written as $\lim_{n\rightarrow\infty} s_n$ for some termwise-definable $s_n$. As an example, if $\mathcal{F} = \{+,\cdot,\div,(x,y\to x^y)\}$, we can write $$ e = \lim_{n\rightarrow \infty} \left(1+\frac1n\right)^n $$ I suspect some more operations would be necessary to get to $\pi$. If you include factorials, it is enough, as we can do $$ \pi = \lim_{n\rightarrow\infty} \left(\frac{n! \left(1+\frac1{n^n}\right)^{n/n^n}}{n^n \sqrt{2 n}}\right)^2 $$ which follows from Stirling's approximation.

Is there a finite set $\mathcal{F}$ that's big enough so that we can get any computable number as a limit of some termwise-definable sequence?

1

There are 1 best solutions below

2
On BEST ANSWER

Yes, but you're not going to like it. Here's a sketch: we can choose a single function in $F$ to be a universal Turing machine $T(t, n)$ where $t$ denotes an encoding of a Turing machine which takes integer inputs and prints out real numbers with finitely many digits, and $T(t, n)$ denotes the output of $t$ given input $n$ (and let's say $T$ just returns zero on any inputs that aren't nonnegative integers). Then for any computable number we can (by definition) write down a Turing machine that prints out its digits, and feed to $F$ a constant integer sequence encoding this Turing machine, together with the identity sequence.

Probably you had in mind functions that are restrictions of analytic functions or something like that, though. I bet even with a restriction of that kind there are some weird tricks that can be pulled using something like zeta function universality.

You may be interested in reading Timothy Chow's What is a Closed-Form Number?.