Re: does sqrt(2) exist in CM?
From: Jesse F. Hughes (jesse_at_phiwumbda.org)
Date: 02/11/05
- Next message: Serguey Zefirov: "F-rep volume computation."
- Previous message: W. Mueckenheim: "Re: abundance of irrationals!)"
- In reply to: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Next in thread: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Reply: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Messages sorted by: [ date ] [ thread ]
Date: Fri, 11 Feb 2005 10:33:57 +0100
examachine@gmail.com writes:
> Jesse F. Hughes wrote:
>> examachine@gmail.com writes:
>>
>> > Anyway, the problem is, if we swallow what I say above we have a
>> > paradox: it is not possible to define a "truly random" real by
> infinite
>> > application of a fair coin! Which seems a little counter-intuitive.
> How
>> > do we explain that?
>>
>> Why not explain it the obvious way? Chaitin randomness isn't the
> same
>> thing as random.
>
> If you think so, then you will have to conclude that Martin-Lof
> randomness and Solovay randomness aren't the same thing as random,
> either. What should that make us believe in? That Borel's paradox of
> the undefinability of randomness was correct?
>
> Please, let's make the discussion concrete. So, you don't think Solovay
> randomness, which is provably equivalent to strong Chaitin randomness
> defines randomness. In other words, Solovay randomness is just wrong,
> there are other random numbers than Solovay random numbers.
No, I think that Solovay/Chaitin randomness[1] does not mean the same
thing as when we say that flipping a coin is random. I didn't say
wrong, but it certainly can be misleading.
What do we mean when we say that a coin flip is a random source[2]?
We mean roughly that we cannot reliably predict the outcome prior to
the flip.
But that's apparently different than the meaning of random that
complexity theory yields. Moreover, the things that complexity theory
applies the term "random" to just don't seem to be sources of events.
They are numbers or strings, not sources of numbers or sources of
bits.
You can ask of a given string whether someone that doesn't know the
string can find a reliable algorithm for predicting the next bit, but
that's not the same as asking whether one can predict a coin flip (and
it's not obvious to me whether it's the same as Chaitin's sense of
random, but I bet someone here knows). In the former case, you're
asking about a deterministic source and placing limitations on the
agent's knowledge in order to test his capacity to predict and in the
latter, we're making a claim that a particular source is inherently
unpredictable (again, this is only loose talk when applied to coins
instead of to properly random sources like quantum whatsits).
Chaitin claims (in "Randomness and Mathematical Proof") that:
,----
| Almost everyone has an intuitive notion of what a random number
| is. For example, consider these two series of binary digits:
|
| 01010101010101010101
| 01101100110111100010
|
|
| [...]
|
| The second series of binary digits was generated by flipping a coin 20
| times and writing a 1 if the outcome was heads and a 0 if it was
| tails. Tossing a coin is a classical procedure for producing a random
| number, and one might think at first that the provenance of the series
| alone would certify that it is random. This is not so. Tossing a coin
| 20 times can produce any one of 220 (or a little more than a million)
| binary series, and each of them has exactly the same probability. Thus
| it should be no more surprising to obtain the series with an obvious
| pattern than to obtain the one that seems to be random; each
| represents an event with a probability of 220.
`----
Here, he's fairly explicit that the term "random" that applies to coin
tosses is different then the sense of "random" he's discussing: namely
random as in haphazard, without order[3].
They are two distinct meanings attached to the same word. If you
think that's sufficient for a paradox then you might have a gander at
/set/ theory next.
Footnotes:
[1] I know nothing about Martin-Lof's notion of randomness.
[2] Anyone that actually deals with probabilities and randomness may
feel free to correct my terminology and half-thoughts. And let's
assume that coin flips really *are* random.
[3] I have recently said that I disagreed with that opening sentence:
I didn't have any intuition about what a random number is. I take it
back now. "Random" meaning "haphazard" is fairly standard and I
suppose that I do have some vague intuition about what it means for a
number to be a sequence of digits without any apparent order. I was
only thinking of the term "random" as it applies to unpredictable
sources.
-- Jesse F. Hughes "[I]t's the damndest thing. There's something wrong with every last one of you, and I *never* thought that was a possibility. But now I feel it's the only reasonable conclusion." --JSH sees some sorta light
- Next message: Serguey Zefirov: "F-rep volume computation."
- Previous message: W. Mueckenheim: "Re: abundance of irrationals!)"
- In reply to: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Next in thread: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Reply: examachine_at_gmail.com: "Re: does sqrt(2) exist in CM?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
