Re: Proper Turing cones are null?

From: Keith Ramsay (kramsay_at_aol.com)
Date: 02/23/05 

Date: 23 Feb 2005 06:13:35 -0800

Keith Ramsay wrote:
| Mike Oliver wrote:
| | I *think* the following is true -- if x is a noncomputable
| | real, then the set of y such that x is computable wrt y has
| | measure 0.
|
| The set of y such that the n-th bit of x is the same as the
| 2^n-th bit of y for n>=1 has positive measure.

I'm sorry, that was really stupid. Of course it doesn't.
I was thinking I got something like the fattened Cantor
set that has measure greater than zero, but that's wrong.

It's enough to prove that for each Turing machine M, the set
of y such that x is computable from y using M has measure
zero, or in other words that if the set of y from which x
is computable by M has measure >0, then x is computable.
Suppose that the set of y from which x is computable by M
has measure epsilon>1/N>0. There are not N distinct reals
having that property.

For each finite binary string s, consider the set Y(s) of
y such that M equipped with an oracle to y returns the k-th
bit of s on input k, for 1<=k<=length(s). If s is an initial
segment of s', then Y(s') is a subset of Y(s), and if
neither s nor s' is an initial segment of the other, then
Y(s) and Y(s') are disjoint.

If y is in Y(s), then the computations of bits of s with an
oracle to y query only finitely many bits in y. Let H be the
set of pairs (s,t) where t is the initial segment of y whose
last bit is the last bit of y queried during those
computations of bits of s. Then H is computably enumerable,
since each pair (s,t) can be verified by a finite number of
terminating computations, and Y(s) consists of the union of
{y' : t is an initial segment of y'} for (s,t) in H. The t
for which (s,t) is in H are independent, which makes these
subsets disjoint. Since H is computably enumerable, then for
each s, so are the t such that (s,t) are in H.

If Y(s) has measure >1/N, then for some t_1,...,t_p, the
(s,t_i) are in H and the total measure of {y' : t_i is an
initial segment of y' for some 1<=i<=p} is >=1/N. Hence
the set T of finite binary strings s such that Y(s) has
measure >1/N is also computably enumerable.

We know T is a binary tree since if s is an initial segment
of s', then Y(s) contains Y(s') and if Y(s') has measure
>1/N then so does Y(s). There are not N independent nodes
in T, because those would correspond to N disjoint sets
Y(s) of measure >1/N.

For each initial segment s of x, the set Y(s) contains the
set of oracles y such that if M is equipped with y, then
it computes not merely the bits in s, but all the bits of
x. By assumption, the set of those y has measure >1/N. So
each initial segment s of x is in the tree T, and x
corresponds to an infinite branch of T. (Infinite
branches of T correspond to reals having the same propery
as x has.)

If for each k, there existed a node of T above k which is
not an initial segment of x, then there would be infinitely
many independent nodes in T. So for sufficiently large k,
the initial segment of x of length k has only initial
segments of x above it. Then we can compute x by enumerating
the nodes of T above this initial segment of x.

Keith Ramsay

Relevant Pages

  • Re: Well Ordering the Reals
    ... >>>an initial segment indexed by the natural integers. ... If we let c be the cardinality of the reals, ... It will be some infinite ordinal ... > segments of the well-ordering, else there would be countably many. ...
    (sci.math)
  • Re: Well Ordering the Reals
    ... >>In a well-ordering of the reals, ... >>an initial segment indexed by the natural integers. ... For each countable initial segment is generated a unique convergent ...
    (sci.math)
  • Banach-Tarski: Staccato
    ... Through only translation, rotation and recomposition, the maximum ... When you divide the reals into two everywhere discontinuous subsets, ... One notion with that is where two real-component subsets of a segment ...
    (sci.math)
  • Re: Non-Standard Analysis & Other Infinities
    ... >>> It's basically consideration that if the line segment is comprised ... >>> The reals are a complete ordered field. ... First, about the nested intervals, they are non-degenerate closed ...
    (sci.math)