Simple example of a sequence without computable modulus of convergence - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T07:16:52Z http://mathoverflow.net/feeds/question/51794 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51794/simple-example-of-a-sequence-without-computable-modulus-of-convergence Simple example of a sequence without computable modulus of convergence Mateus Araújo 2011-01-11T23:28:07Z 2011-01-13T05:09:51Z <p>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 <a href="http://en.wikipedia.org/wiki/Modulus_of_convergence" rel="nofollow">modulus of convergence</a> is not computable?</p> <p>In the literature, all I could find were aesthetically unpleasant examples of Specker sequences. </p> <p>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.</p> <hr> <p>And what if we still require the sequence itself to be computable? Is there still so easy an example?</p> http://mathoverflow.net/questions/51794/simple-example-of-a-sequence-without-computable-modulus-of-convergence/51796#51796 Answer by Andreas Blass for Simple example of a sequence without computable modulus of convergence Andreas Blass 2011-01-11T23:43:23Z 2011-01-11T23:43:23Z <p>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 <code>$f(n-1)&lt;k\leq f(n)$</code>. The sequence converges to 0, but any modulus of convergence, applied to $\varepsilon=1/n$, would majorize $f$ and would therefore not be computable. </p> http://mathoverflow.net/questions/51794/simple-example-of-a-sequence-without-computable-modulus-of-convergence/51914#51914 Answer by Jason for Simple example of a sequence without computable modulus of convergence Jason 2011-01-13T05:09:51Z 2011-01-13T05:09:51Z <p>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:</p> <p>$a_m = \begin{cases} 1/f(m) &amp; \text{if } f(m) \neq 0 \\ 0 &amp; \text{otherwise.} \end{cases}$</p> <p>converges to $0$, but its modulus of convergence is noncomputable.</p> <p>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:</p> <p>$f(\langle e, n\rangle) = \begin{cases} e &amp; \text{if } T_e \text{ halts in exactly } n \text{ steps on input } 0 \\ 0 &amp; \text{otherwise.} \end{cases}$</p> <p>$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 <em>most</em> 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| &lt; 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$.</p> <p>But if the modulus of convergence $M$ for $\vec{a}$ were computable, where $M(k)$ is understood to satisfy $|a_m - 0| &lt; 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)$.</p> <hr> <p>If on the other hand, you wanted $\langle a_s| s &lt; \mathbb{N}\rangle$ to be a convergent computable sequence of <em>Natural numbers</em>, 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. </p>