Specker sequence

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. 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 0 over RCA 0 . In fact, the proof of the forward implication, i.e.…

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. 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 0 over RCA 0 . In fact, the proof of the forward implication, i.e. that the least upper bound principle implies ACA 0 , is readily obtained from the textbook proof (see Simpson, 1999) of the non-computability of the supremum in the least upper bound principle. 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| 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 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

Text derived from https://en.wikipedia.org/w/index.php?oldid=1368885091 under CC BY-SA 4.0; modifications have been made.