Re: does sqrt(2) exist in CM?

examachine_at_gmail.com
Date: 02/16/05 

Date: 16 Feb 2005 03:44:12 -0800

Here's what Chaitin says on a hierarchy of randomness definitions (from
Turing degrees):

http://www.umcs.maine.edu/~chaitin/ait12.html

I think I'd read that before, but I've forgotten. This was exactly what
I meant by a hierarchy of randomness definitions.

Cheers,

Mike Oliver wrote:
> examachine@gmail.com wrote:
>
> > r.e.s. wrote:
> >
> >>A reasonable definition of "randomness" as a property of individual
> >>reals must -- as a necessary but not sufficient condition -- be
such
> >>that the reals not having this property comprise a set of Lebesgue
> >>measure 0, and this is the case for the Solovay definition.
> >
> > Nice, what would a sufficient condition entail?
>
> I think there can never be a final answer to this. Given
> any candidate definition and any real r satisfying it, you have
> the problem that the *true* definition of randomness, whatever
> it is, ought to guarantee that a random real is not equal to r.
>

> What you *can* have is a hierarchy of stronger and stronger
> conditions that are sufficient for more and more delicate
> purposes.
>
> So for example a real is "strongly n-random" if it avoids
> all Pi^0_n null sets. Solovay random is the same as
> strongly 1-random. A real is 1-random (no "strongly")
> if the prefix-free complexity of its initial segments
> is as large (up to an additive constant) as the length
> of the segment; it's n-random if it's 1-random after
> allowing an oracle for the (n-1)st jump of 0. Strongly
> n-random ==> n-random ==> strongly (n-1)-random. No
> warranty on these definitions or results; my memory
> could be a little off.
>
> Strong n-randomness is an approximation to randomness
> in the sense of random real forcing.