random

[Alex Martelli]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b18ea18.332276 at nntp.sprynet.com...
    ...
> I said you cannot have complete information about
> a physical system. You can't. An algorithm is not

Let's take your original sentence again, snipless:

"""
A physical RNG can have the property that one cannot make
any prediction about the value of the next bit even given
_complete_ information about how the numbers are being
generated.
"""

This says "GIVEN _complete_ information".  Now you say
you CANNOT "have complete information".  The two
statements are in contradiction.  If you cannot have it,
how can it be given?  I don't see why you keep denying
this obvious contradiction.

I claim: if you cannot make a prediction it is because you
are NOT given complete information.  Whether that is
because it cannot be given 'in principle' (physically) or
because it just is not given, is mathematically rather
irrelevant, it seems to me.

So what does the "GIVEN _complete_ information" above
is, if not a statement that you CAN be given complete
information about


> >So, to recap: the post I was replying to states that given
> >[what you now state is] an impossibility,
>
> No. I never stated that it was impossible to have
> complete information about the state of an algorithm.

You didn't, but you did state and re-state that it's
impossible to have complete information about the
state of a physical system, and yet the key characteristic
you stated for 'a physical RNG' begins with "GIVEN
_complete_ information".


> >> 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).

It's a popular definition, though not universal of
course -- Darren New seems to be debating on this
same thread on the basis of the finitistic definition
of 'algorithm'.  Very well then, if you can conceive
of algorithms whose state cannot be finitely described,
then, there you are: prediction will be impossible with
those algorithms because you can never possess all
the relevant information.  There, happy now?

(I _think_ -- but am not a philosopher or mathematician
so cannot feel sure -- that part of what Goedel shows is
that arithmetic is powerful enough to model any other
formal system, including the inconsistent-if-complete
conumdrum, so I don't imagine it's the "arithmetic"
part of 'arithmetic algorithm' that you imagine limits
a non-finitistic algorithm predictability?)


> Take it up with Heisenberg. If it's possible to have
> complete information about a physical system then
> physics is simply _wrong_.

It may be right, it may be wrong, how does that affect
mathematics anyway?  You think mathematics should be
changed based on what physical theories happen to match
or not-match the alleged 'real' world, maybe...?


> >> > From what I know of Chaitin's life work,
> >> >it started with just the idea of defining randomness in
> >> >terms of minimal amount of information (in bits) you need
> >> >for prediction.  If YOUR definition of 'randomness' is
    ...
> I really don't have any idea what you're getting at here.
> I never said anything about what's fruitful or interesting
> or useful. JVN said anyone using arithmetic methods to
> get random numbers is in a state of sin. It was stated
> that Chaitin has shown that this is wrong. I didn't see
> how, but I'm not familiar with his work, so I asked
> how Chaitin's work showed that JVN was wrong. So far
> I haven't heard the esplanation.

I reiterate my suggestion that said explanation is most
likely to be found in the less-than-200-pages of Chaitin's
new book, given its title "Exploring Randomness", and
that, not having yet read it, I could not presume to do
it full justice.  (But I have now ordered it, so that may
change soon!-).  Still, it doesn't seem mind-bending as
a possibility: if randomness can be defined based on the
number of bits needed for prediction (no need to require
an INFINITE number of bits before the word can be used),
why shouldn't arithmetic be quite usable to build a system
whose output requires sufficiently many bits of info to
predict, that its randomness is sufficiently high for a
given purpose?  What's "sinful" about it?


> Probably "is in a state of sin" is not well-defined.

Presumably was meant as a humorous quip?

> I take the comment to mean that there is no "percect"
> arithmetical RNG. It seems extremely clear to me that
> there isn't, and I haven't heard anything that explains
> how Chaitin's work _does_ show that there exists
> a perfect arithemtical RNG.

I'm not sure what you mean by "perfect" (or "percect" --
not sure if that was a typo, and if so, whether it was for
'percept' or 'perfect').  If you mean one requiring an
infinite amount of information for prediction, I guess it
would start with a halting-problem, Goedel numbers, or
other equivalently-hard problems as modeled in
arithmetic, and the random bit would be some low
bit in a count of the number of operations needed to
get a solution -- as the 'algorithm' would not be
guaranteed to stop (which makes it non-finitistic, and
thus, for those who DO require finiteness as part of an
algorithm's definition, not an algorithm), there could be
no bounds placed on the effort (information) required
to predict (no bounds = boundless = infinite -- as hotly
debated on a separate recent thread:-).  I doubt very much
that Chaitin wastes his precious time with these specific
silly mind-games (thus showing once more he's a far
wiser man than me:-), because that "perfect" (which was
not in the original question) requirement for infiniteness
is of little interest in this context.  If we model random
number generation as an adversarial cryptographic scenario,
which does seem a productive way to look at it, then we
are not required to come up with schemes which make
our adversary require infinite work (information) to predict
(and thus decrypt): it's enough that, for any ratio of our
work encrypting (generating) for his decrypting (predicting)
that is requested, we can come up with a setting that makes
the ratio higher.  And I believe (not being really up to date
on the latest cryptography results, I 'surmise' might be
closer:-) that so-called one-way-functions allow us to make
the work-ratio predict/generate (decrypt/encrypt) higher
than any pre-requested threshold.  I do suspect that 1-w-f
are part of Chaitin's work, btw.

And quips apart, what's "sinful" about dealing with
randomness this way?  If the underlying maths are sound
(and that, I surmise, IS what Chaitin has to do with it:
showing the soundness of this finite-maths approach
to randomness), why shouldn't RNG's be feasible and
sin-less that are based on these techniques?


> In fact I didn't claim _anything_ except that I didn't
> see how there can be a _perfect_ arithmetic RNG,
> Chaitin or no Chaitin. That's a _true_ statement
> about what I don't see.

Depending on your definition of 'perfect', I hope the
construction above may satisfy your quest for vision?


> >what makes you SO certain that NO other physical
> >systems can also be predictable in the same sense?-)
>
> Well, if I'd claimed that a physical computer was
> predictable you'd have a point.
>
> But claiming that no physical system is predicatable
> _except_ for computers is (i) not something I said,
> (ii) so obviouslt ridiculous that I don't see why you
> would think that that's what I was claiming from
> anything I _have_ said.

It seems to me that enough things you're saying have
just-as-ridiculous obvious consequences, such as your
joint assertions 'GIVEN _complete_ information' [about
a physical system] and 'comlete information cannot be
had' [about a physical system].  How am I to know which
ones of these contradictions and 'ridicolousnesses' you
ARE in fact claiming (perhaps in error) and which ones
you are not?  I still haven't heard your definition of
'perfect' randomness, for example.  I have my doubts
I'll be able to find it non-ridiculous, but I've been wrong
before.  So until you deign to give us your definition,
and clear up all the seeming contradictions in what you
have said before, what can I do except operate on the
basis of working hypotheses based on the most
reasonable interpretations of your words, and showing
where I think there are contradictions, tautologies, and
so forth?

Meanwhile I still see nothing 'sinful' in dealing with
randomness finitely, and nothing I've seen on this
thread has taken me even a iota closer to seeing it.
Or to seeing why arithmetic (which is quite capable
of non-finiteness if you push it:-) should be singled
out in this context.


> >it seems to become tautological ("I define X as being
> >something that requires infinities: no finite system can
> >reach X, it can only approach it")
>
> Another thing that's been puzzling me is where I've
> said anything about these infinities that you continue
> to quote me about.

As you do not deign to define your terms (not even to
USE them, actually -- that 'perfect' was NOT in the
original quote from JVN) unless pushed very hard about
it, why are you puzzled that people take the terms you
use in the normal and obvious meaning they could be
taken to have in your usage context?  What _IS_ a
'perfect randomness', as you use the term, if not one
taking infinite information to predict?  Until and unless
you clarify your terms you'll have to resign yourself
to people reading them in reasonable-looking ways that
might not have been the ones you intended them in.


Alex