Re: Can some non-computable sequences be "computed" by non-halting TMs?
From: Toby Ord (firstname.surname_at_philosophy.ox.ac.uk)
Date: 07/04/04
- Next message: Peter Olcott: "Re: Daryl, Dave, Barb and the Georges' source of Confusion"
- Previous message: |-|erc: "Re: limitation to induction on finite bounds"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Sun, 4 Jul 2004 14:27:26 +0000 (UTC)
In <cb6iu1$dke$1@ra.nrl.navy.mil> Ralph Hartley wrote:
> r.e.s. wrote:
>> "Ralph Hartley" <hartley@aic.nrl.navy.mil> wrote ...
>
>>>For example, the binary representation of Chaitin's Omega is such a
>>>bit sequence. The obvious algorithm to estimate this number
>>>eventually sets each bit to its correct value, and never changes it
>>>again. The sequence is nevertheless uncomputable, because no
>>>algorithm can determine whether or not a bit has reached its final
>>>value yet. Real numbers with this property are called "recursively
>>>enumerable". I will leave it as an exercise to figure out why.
Actually this is not quite correct. There must be a computable sequence
of rationals converging to the number from below. Convergence from above
means a co-r.e. real (like one minus Omega), from above and below means
a computable real and convergence (with no restriction) means a Delta_2
real which is a strictly weaker criterion. Incidentally I find the Delta_
2 reals to be a more natural class of 'almost computable' reals, but
they don't seem to come up as often as r.e. reals.
>> Thanks for the example -- it led me to read up on the r.e. reals --
>> but there's a lingering doubt ...
>>
>> Although a Chaitin Omega is an r.e. real (meaning that it's the
>> limit of a computable increasing sequence of rationals), apparently
>> *not* every r.e. real has an r.e. binary expansion (!). Is it known
>> that Chaitin Omegas *do* have r.e. binary expansions?
>
> That was my understanding, though I don't remember if the proof I saw
> applied to all Omegas or just one particular one.
No Omega numbers have r.e. binary expansions. While they are all 'r.e.
reals', the binary expansions of the Omega numbers are not r.e. (meaning
that the set of all integers n, such that n is included if and only if
the nth bit of omega is 1 is not an r.e. set).
One can see this from the incompressibility of the bits of Omega. For
any r.e. set, one can determine whether any n numbers are in it with log_
2(n) bits of advice. Just ask how many of the n numbers are in the set (
which is a number up to n using log_2(n) bits to represent it) then run
an enumeration of the set until that many of the specified n values have
been found to be in the set. The rest will not be in the set.
Since Omega numbers are incompressible, requiring n bits of advice to
get n bits of the number, they need more than log_2(n) bits and their
bits are thus not an r.e. sequence.
More can be found in an article I wrote a while ago:
http://arxiv.org/abs/math.NT/0302183
Toby Ord.
- Next message: Peter Olcott: "Re: Daryl, Dave, Barb and the Georges' source of Confusion"
- Previous message: |-|erc: "Re: limitation to induction on finite bounds"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
