random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b19393d.703539923 at news.okstate.edu...
    ...
> probably I should not have said what I did the
> way I did, because my impression is that there
> is really no such thing as complete information
> about a physical system.

Sorry for making such a production of it, but that
was exactly the crux of this part of the argument
(and the contradiction that kept grating on me).
I apologize if I wasn't effective in communicating
this aspect.

*Most* (not all) of this fracas seems to be about
such miscommunications in one or the other
direction, such as:

> >> >> can have complete information regarding the state
> >> >> of an _arithmetic_ _algorithm_.
> >> >
> >> >I assume that is your definition of "an algorithm"?
> >>
> >> It's not the _definition_, (and to the extent that
> >> it is part of a definition it's not _my_ definition).
    ...
> Good heavens, of course the state of an algorithm
> can be finitely described. I didn't say otherwise.
>
> When I said "not _my_ definition" I meant it was
> not a definition due to me, not that it was not
> a definition that I was using. When I said that
> it was not the definition I meant _exactly_ that:
> "one can have complete information regarding
> the state" is not the definition of "arithmetic
> algorithm".

Heh, OK, "PART of the definition" is correct, and I
totally misread what you meant by "not _my_
definition" when you correctly inserted that 'part of'.

Had I more carefully phrased my question as "is
part of the definition of 'algorithm' that you are
using" we might have been spared a fraction of
these exchanges, just as we might have, had your
phrasing re 'given complete information' up above
been as you now wish it had.

Different use of technical terms is also part of it,
it seems.  When I say "algorithm" (and this seems
to be widespread usage) I don't necessarily imply
an algorithm that is guaranteed to stop within a
finite amount of time nor one that is guaranteed to
have the exact answer when it does stop -- I say
'deterministic' algorithm when I need to imply that,
'probabilistic' algorithm when I need to imply the
contrary, and just 'algorithm' without adjectives
when talking about both sorts.  50 years ago usage
was surely different (presumably back then a phrase
like 'probabilistic algorithm' would either seem an
oxymoron or be taken as a strange way to name an
algorithm about some aspect of probability theory),
so I might have taken that into account.


Perhaps this subpart is about communication too:

> about.) People don't usually try to prove things
> by saying it's probably in a book somewhere...

Right, but you didn't ask for a PROOF, the way I read
your question, just:

> Could you give us a hint regarding exactly what work
> of Chaitin's shows we can get "truly random" numbers from

..."shows".  I understand "show" and "prove" can
be used as synonymous in some contexts, and maybe
that is how you were using 'show' here -- I had not
read it as such.  Anyway, you were only asking for
a _hint_ about exactly what work of Chaitin was the
relevant one, not the proof itself -- and why isn't it
correct to 'hint' that his recent book titled "Exploring
Randomness" looks like the right one?  I couldn't and
can't be positive, not having received and studied it
yet, but it seemed a potentially useful pointer to supply
in response to a request for just a "hint"!


> I hope I've clarified the contradiction you mention
> in this post - while I don't think it was actually a
> contradiction, I do agree that seeing it as
> contradictory is not all that unreasonable, I
> would have stated things much more carefully
> if I'd known there was going to be a quiz.

Same here.  I have used sloppy, approximate and
perhaps misleading wording.  There are enough real
disagreements without artificially constructing more.

Neither of us was 'all that unreasonable' in taking
some of the other's words in pretty bad ways
(including contradictory, ridiculous, offensive, &c),
and maybe, as we didn't know there was going to
be a quiz, it was also not totally unreasonable to
spend 'just' hours rather than entire days in crafting
our statements.  The overall result _was_ rather
unreasonable though:-).


> First, I don't think that it makes
> sense to talk about a perfectly
> random _sequence_, any more than
> it makes sense to talk about a random
> number. Someone wanted to know
> how random 6 was.

If you take away the sting of 'perfectly', it
seems to me that talking about 'how random
is a number [sequence of bits]' does make
sense.  6, aka 110, is not very random because
it can be output by a tiny program indeed in
any given UTM.  00000000000000000000 is
several bits, but not very random, as, again,
the program to output them can be made small.
000001010011100101110111's structure is
not quite as evident, but clearly there as soon
as you cut the string up 3 bits at a time -- again
a small program is possible.  It starts getting
harder with 0011101000100001011000100101
(a string I just input 'at random':-) -- the fact
I don't see its structure doesn't mean it have
one (and apparently I have no way in general
to prove a given long bitstring _doesn't_ have
"structure" -- to find a lower bound on the
amount of bits needed to encode it).

But this is close to the way a 'man in the street'
would use the word 'random' about a sequence
of bits -- including the possibility that one seems
random (I haven't noticed its structure == I
only so far have a program to emit it that is
large) but really isn't (it does have structure,
there _is_ a small program generating it).  If
we can give a useful technical meaning to a
word that well matches its common-or-garden
use, why not?

But I do agree that JVN was likely not thinking
of this meaning of 'random' as it was (AFAIK)
not used in his time.


> A perfect RNG is one with this property:
> If you use it to generate N bits then each
> sequence of N bits appears with probability
> 1/2^N. It has this property for _every_ N.

So the computation of Omega is a perfect RNG --
and isn't there an old proof about pi having
this property too?  (dim memories here...)

> (Hence an algorithm, as the word is usually
> defined, cannot be a perfect RNG. Because
> it has only finitely many states - it must repeat
> after a while, and hence for large enough
> values of N it is not true that all sequences
> of length N are equally likely.)

Sorry, but I must be missing something.  Can't
I write an algorithm to compute as many bits
of pi as I want?  Sure, the amount of state it
will have to save when it has computed K bits
of pi, in order to compute the next N (the next
'run'), will grow with K, having no upper bound.

But isn't that the reason we have Turing machines,
their infinite tape?-)  Isn't a Turing-machine
program (even one exploiting the fact that the
tape is unbounded) "an algorithm", at least when
it can be proved to run to completion in finite
time at each run?  Any given run will only use a
finite portion of the tape, but we don't have to
know how much in advance, do we?  At each
successive (finite) run, more and more of the
tape could be used -- we ain't gonna run out.

In other words, are you saying there cannot
exist an algorithm that is able to compute any
arbitrary amount of bits of pi on request, and (having
computed the first K of them and kept whatever
other auxiliary state it needs to on the Turing
machine tape) can at any time be asked for
"and now the next N please" for any N?  Why
would this Turing-machine program not be an
algorithm, by the definition you want to use?
It seems to me to meet any definition of
algorithm I have ever encountered, but maybe
I have not encountered enough?

If you concede such an algorithm is possible,
then how does it "have only finitely many
states", and why must it "repeat after a while"?
Surely it's proven that pi's bits (or digits in
any integer base of your choice) _don't_ repeat
after a while -- that's why pi is *irrational*, no?

Now if my dim memories are correct, wouldn't
this algorithm be a "perfect RNG" by your
definition as here given?  Or was this definition
meant to be incomplete, with clauses to be
added progressively as needed to eliminate
otherwise uncomfortable algorithms from the
"perfect RNG" class?-)


Alex