Re: WELL WHICH IS IT... ?

From: Ralph Hartley (hartley_at_aic.nrl.navy.mil)
Date: 01/25/05 

Date: Tue, 25 Jan 2005 10:15:25 -0500

The Ghost In The Machine wrote:
> <stephen@nomail.com> wrote:
>>Of course, even though all of the prefixes of Chaitin's Omega
>>will appear on a list of computables we cannot actually determine
>>that they are prefixes of Chaitin's Omega.
>
> Actually we can -- once we have Chaitin's Omega. I'll admit I'm
> not sure, but I suspect we can get a good chunk of Omega's digits,
> just not *all* of it

Depends on what you mean by "a good chunk". As usual the quantifier order
matters.

For any n there is a TM that computes the first n digits (if that's what
you mean, it's trivial since it's true for all real numbers), but for any
TM there is an n such that the TM cannot output *any* digits beyond n.

Interestingly there *is* a TM that computes a sequence of numbers that
*converges* monotonicly to Omega (It is easy to construct from the
definition of Omega). You can't use that to compute the digits, because how
*fast* it converges is not computable.

I think I've seen real numbers like that referred to as "r.e. numbers." The
name fits.

If you mean something else by "a good chunk" ...

How many digits can *we* get? I'm not sure, but I suspect that we can't get
*that* number. If we could, we could get more digits than we can get.

(Fine print: By "get", I mean effectively compute. Some people might claim
that we can "get" or "know" something that we cannot effectively compute.
Some of those people may have good points (actually, I know some do). I
disagree, but am not prepared to argue about that now. I would have to
think hard, and for *way* too long.)

Ralph Hartley

Relevant Pages

  • Re: WELL WHICH IS IT... ?
    ... apparently Ghost and I interpretted the above differently. ... :> interpretted it as "Given the list of computables, and a real number X, ... is clear that all of pi's finite prefixes are within TX_10, ... even though all of the prefixes of Chaitin's Omega ...
    (comp.theory)
  • Re: WELL WHICH IS IT... ?
    ... apparently Ghost and I interpretted the above differently. ... :> interpretted it as "Given the list of computables, and a real number X, ... is clear that all of pi's finite prefixes are within TX_10, ... even though all of the prefixes of Chaitin's Omega ...
    (sci.math)
  • Re: WELL WHICH IS IT... ?
    ... apparently Ghost and I interpretted the above differently. ... :> interpretted it as "Given the list of computables, and a real number X, ... is clear that all of pi's finite prefixes are within TX_10, ... even though all of the prefixes of Chaitin's Omega ...
    (sci.logic)
  • Re: "Algorithmic Randomness, Quantum Physics, and Incompleteness"
    ... This may make it sound like you can calculate Omega with arbitrarily great ... The digits of pi can be computed one ... It follows that an algorithm that puts out a random string of bits must ... "DECIDABILITY AND UNDECIDABILITY IN THE ENUMERABLE TURING DEGREES" ...
    (sci.logic)
  • Re: Cantors diagonal proof wrong?
    ... > methods compute the digits of Pi by doubling the number of digits ... It is not a matter of time. ... But in a line enumerated by omega, ... > the size of the set of naturals ?), but I cannot imagine it as ...
    (sci.math)