Simple example of a sequence without computable modulus of convergence

2011-01-11T23:28:07Z

Can anyone give a simple example of a sequence that converges, but there's no computable function that gives $N$ as a function of $\epsilon$, i.e., the modulus of convergence is not computable?

In the literature, all I could find were aesthetically unpleasant examples of Specker sequences.

I hope that relaxing the requirements of the sequence itself being computable and it's limit not is enough to get simpler examples. Unfortunately, the examples that I've been able to come up with myself are worse than the literature.

And what if we still require the sequence itself to be computable? Is there still so easy an example?

Answer by Andreas Blass for Simple example of a sequence without computable modulus of convergence

2011-01-11T23:43:23Z

Because of the relaxed requirements, the following seems to work. Let $f$ be an increasing function from natural numbers to natural numbers that grows faster than any computable function. (For example, define $f(n)$ to be $n$ plus the largest number obtainable by giving any input $\leq n$ to any Turing machine with Gödel number $\leq n$.) Then define $a_k$ to be $1/n$ if $f(n-1)<k\leq f(n)$ . The sequence converges to 0, but any modulus of convergence, applied to $\varepsilon=1/n$, would majorize $f$ and would therefore not be computable.

Answer by Jason for Simple example of a sequence without computable modulus of convergence

2011-01-13T05:09:51Z

The answer to your more restrictive question is still yes with a reasonable definition of computable sequence (and I'll use your Busy Beaver example in the proof). Specifically, I will provide you with a computable $f: \mathbb{N} \rightarrow \mathbb{N}$ such that $\vec{a} = \langle a_m| m \in \mathbb{N}\rangle$ defined by:

$a_m = \begin{cases} 1/f(m) & \text{if } f(m) \neq 0 \\ 0 & \text{otherwise.} \end{cases}$

converges to $0$, but its modulus of convergence is noncomputable.

Fix a computable Cantor pairing function $\langle \cdot, \cdot\rangle$ where $\langle e, n\rangle \geq n$ for all $n$ and some computable enumeration of Turing machines $\langle T_e| e \in \mathbb{N}\rangle$ with $T_0$ some trivial Turing machine halting in $0$ steps on every input. Then define $f$ as follows:

$f(\langle e, n\rangle) = \begin{cases} e & \text{if } T_e \text{ halts in exactly } n \text{ steps on input } 0 \\ 0 & \text{otherwise.} \end{cases}$

$f$ is clearly computable because we can use an appropriate Universal Turing machine to run program $e$ on input $0$ for $n$ steps to determine whether it halts in exactly $n$ steps or not. Furthermore, each positive Natural number $e$ is assumed at most once by $f$, mainly at $\langle e, n\rangle$ if $T_e$ halts in exactly $n$ steps on input $0$. Consequently, for any positive Natural number $e$, we'll have $|a_m - 0| < 1/e$ beyond the at most $e$ many places where $f$ assumes a value from {$1, 2, \ldots, e$}. Therefore, $\vec{a}$ converges to $0$.

But if the modulus of convergence $M$ for $\vec{a}$ were computable, where $M(k)$ is understood to satisfy $|a_m - 0| < 1/k$ for all $m > M(k)$, then the Busy Beaver problem would also be computable. To see this, first note that if the program with positive index $e$ halts on input $0$ in exactly $n$ steps and $e \leq k$, then we have $a_s = 1/f(s) = 1/e \geq 1/k$ where $s = \langle e, n\rangle \geq n$, so that $M(k) \geq n$. Consequently, $M(k)$ will give us an upper bound on the number of steps it takes for all programs halting on input $0$ with index at most $k$ to do so. Therefore, by taking the maximum code $e_s$ of all of the $s$-state Turing machines, $M(e_s)$ will in particular provide us with an upper bound on the number of steps that it takes for all $s$-state Turing Machines halting on input 0 to do so. Then we simply run all of the $s$-state programs for this many steps and take the maximum output to compute $BB(s)$.

If on the other hand, you wanted $\langle a_s| s < \mathbb{N}\rangle$ to be a convergent computable sequence of Natural numbers, then $a_s$ must be constant beyond some fixed Natural number $N$, and so we will always have a simple computable modulus of convergence given by the constant function assuming $N$ at every value.

Simple example of a sequence without computable modulus of convergence - MathOverflow

Simple example of a sequence without computable modulus of convergence

Answer by Andreas Blass for Simple example of a sequence without computable modulus of convergence

Answer by Jason for Simple example of a sequence without computable modulus of convergence