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

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?

share|improve this question
1  
Not really an answer, so only a comment (DISCLAIMER: I know almost nothing about logic and computability theory), but how about the following: $a_n = 0$ if all even integers $k$ with $4 \leq k \leq n+4$ can be written as the sum of two primes, and $a_n = 1$ otherwise. Then $(a_n)$ is increasing, and converges to either $0$ or $1$ (classically, anyway). Unfortunately, we'll never know which until someone solves the Goldbach Conjecture; and moreover, even knowing which one it is might not be enough to calculate $N(\epsilon)$ explicitly...(to be continued...) –  Zen Harper Jan 12 '11 at 0:34
    
...(continued) Most mathematicians believe that the limit and $N$ are a computable number and function, but we just don't know which; constructivists would argue that the limit doesn't even exist. So, in both cases (although maybe constructivists wouldn't allow excluded middle here?!!!!), this isn't really an answer to your precise question, sorry. But I thought it might be interesting. –  Zen Harper Jan 12 '11 at 0:35
    
That's an interesting construction, in that many open problems in mathematics can be mapped to the convergence of a sequence, in a way that does not help at all in solving the original problem. –  Mateus Araújo Jan 12 '11 at 1:00
    
Yes, not my construction of course; E. Bishop, Brouwer and the constructivists have been doing that kind of stuff for a long time. As they pointed out, if anyone ever does solve the Goldbach Conjecture, you can just immediately switch to any other similar open problem; so these things will always be around. –  Zen Harper Jan 12 '11 at 1:08
add comment

2 Answers 2

up vote 9 down vote accepted

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.

share|improve this answer
1  
Nice trick. To further simplify your example, just extend the domain of $f$ to the reals and make it continuous (by whatever method that leaves it monotonic). Then $a_k := \frac{1}{f^{-1}(k)}$, and the same argument applies. Also, a simpler example for $f(n)$ could be the busy beaver function, i.e., the maximum number of steps that a halting $n$-state Turing machine can perform before halting. –  Mateus Araújo Jan 12 '11 at 0:44
    
@Mateus: As a clarification, you probably mean before halting on input $0$. –  Jason Jan 13 '11 at 5:13
add comment

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.

share|improve this answer
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.