Specker sequence

A Specker sequence. The n^th digit of x_k is 4 if n ≤ k and the nth Turing machine in a computable Gödel numbering halts on input n after k steps; otherwise it is 3.

In computability theory, a Specker sequence is a computable, monotonically increasing, bounded sequence of rational numbers whose supremum is not a computable real number. The first example of such a sequence was constructed by Ernst Specker (1949).

The existence of Specker sequences has consequences for computable analysis. The fact that such sequences exist means that the collection of all computable real numbers does not satisfy the least upper bound principle of real analysis, even when considering only computable sequences. A common way to resolve this difficulty is to consider only sequences that are accompanied by a modulus of convergence; no Specker sequence has a computable modulus of convergence. More generally, a Specker sequence is called a recursive counterexample to the least upper bound principle, i.e. a construction that shows that this theorem is false when restricted to computable reals.

The least upper bound principle has also been analyzed in the program of reverse mathematics, where the exact strength of this principle has been determined. In the terminology of that program, the least upper bound principle is equivalent to ACA₀ over RCA₀. In fact, the proof of the forward implication, i.e. that the least upper bound principle implies ACA₀, is readily obtained from the textbook proof (see Simpson, 1999) of the non-computability of the supremum in the least upper bound principle.

Construction 1

The following construction is described by Kushner (1984). Let A be any recursively enumerable set of natural numbers that is not decidable, and let (a_i) be a computable enumeration of A without repetition. Define a sequence (q_n) of rational numbers with the rule

$q_{n}=\sum _{i=0}^{n}2^{-a_{i}-1}.$

It is clear that each q_n is nonnegative and rational, and that the sequence q_n is strictly increasing. Moreover, because a_i has no repetition, it is possible to estimate each q_n against the series

$\sum _{i=0}^{\infty }2^{-i-1}=1.$

Thus the sequence (q_n) is bounded above by 1. Classically, this means that q_n has a supremum x.

It can be shown that $x$ is not a computable real number. Suppose, to the contrary, that $x$ were computable. Then the sequence $(q_{i})$ would have a computable modulus of convergence: there would be a computable function $r(n)$ such that

$|q_{j}-q_{i}|<{\frac {1}{n}}$

for all $i,j>r(n)$. Such a function can be obtained by approximating $x$ and comparing it with successive terms of $(q_{i})$. Since each new term in the enumeration changes a single digit in the binary expansion, a sufficiently accurate approximation to $x$ determines a stage after which the relevant initial segment can no longer change.

If such a function $r$ were computable, it would provide a decision procedure for $A$. Given $k$, compute $r(2^{k+1})$. If $k$ were later enumerated into $A$, the corresponding term would increase the sequence by $2^{-k-1}$. This cannot occur after all terms with indices greater than $r(2^{k+1})$ are within $2^{-k-1}$ of one another. Therefore, if $k$ belongs to $A$, it must appear among the first $r(2^{k+1})$ terms of the enumeration. These finitely many terms can be checked effectively, yielding a decision procedure for $A$. This contradicts the assumption that $A$ is not decidable, so $x$ is not computable.

Construction 2

Another construction of a Specker sequence (x_m) can be given using an enumeration of Turing machines. Let {n}(n) denote the action of the n-th Turing machine on the number n. Then let the n-th decimal digit of x_m be 4 if m > n and the computation {n}(n) halts within m − n steps. If the computation has not finished after m − n steps (or if m < n), the digit is 3. (See the figure above.)

• Each x_m is a rational number, since it has a periodic decimal expansion: after the first m decimal places, all digits are 3.
• The sequence is computable, since to produce x_m+1 after having calculated x_m, one only has to simulate m + 1 Turing machines running for one step each.
• The sequence is increasing, because when passing from x_m to x_m+1, digits can only change from 3 to 4.
• The sequence is bounded, because it never exceeds 0.4444444... = 4/9.

The limit of this sequence is not a computable real number, since its decimal expansion contains a 4 in its n-th decimal place if the computation {n}(n) halts, and a 3 otherwise. Determining the digits of the limit would therefore solve the Halting problem, which is impossible.

See also

• Computation in the limit

References

• Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.
• B.A. Kushner (1984), Lectures on constructive mathematical analysis, American Mathematical Society, Translations of Mathematical Monographs v. 60.
• Jakob G. Simonsen (2005), "Specker sequences revisited", Mathematical Logic Quarterly, v. 51, pp. 532–540. doi:10.1002/malq.200410048
• S. Simpson (1999), Subsystems of second-order arithmetic, Springer.
• E. Specker (1949), "Nicht konstruktiv beweisbare Sätze der Analysis" Journal of Symbolic Logic, v. 14, pp. 145–158.