random

[David C. Ullrich]

On Sat, 2 Jun 2001 17:28:22 +0200, "Alex Martelli" <aleaxit at yahoo.com>
wrote:

>"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 don't recall you pointing out _this_ contradiction previously;
the "obvious contradictions" I recall you pointing out were
contradictions between things I'd said about algorithms and
things I'd said about physical systems (and the reason I
keep denying that _they_ are contradictory is that
an algorithm is _not_ a physical system - there's nothing
contradictory about saying every tomato is green and
this apple is red...)

I don't think there was anything contradictory about what
I meant to say, but I do agree those two statements look
a little contradictory. No, a person cannot have complete
information about the state of that physical RNG. And
even if one _could_ have complete information,
that would still not be enough to predict the next bit.

That's assuming that physics is not all wrong. And
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.

>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,

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

You're not actually suggesting that you or anyone
else thinks that "one can have complete
information" _is_ the _definition_ of the
word "algorithm"? By this definition the number
2 is an algorithm.

If I'd said that "red" is not the definition of
"tomato" would you conclude that I could
conceive of non-red tomatoes? Even if
I then said something about "to the extent
to which red is part of the definition"???

>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,

I'm a mathematician. Lucky me.
I can think of _various_ things that "arithmetic is 
powerful enough to model any formal system" might mean,
some of which are nonsense and some of which
are true, at least given certain constraints on the
_size_ of the formal system. Arithmetic certainly
cannot model _any_ formal system in any reasonable
sense, for example langauges with uncountably many 
constants are going to be tough to model in arithmetic.

But Godel numbering does show that you can
model formal systems in small languages in
arithmetic, in some sense. 

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

I have not said anything about non-finitistic
algorithms.

>> 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?

I can't decide whether this is intentional or accidental
drift. I did not say that it had any effect on mathematics.
I said it was impossible to have complete information
about a physical system. You replied asking me who
I was, some infallible priest or something, I forget
exactly how you put it. So I rephrased what I'd
said, including what one would think would be
the obvious disclaimers. Now you ask me
how that affects the math. I never said it did.

>  You think mathematics should be
>changed based on what physical theories happen to match
>or not-match the alleged 'real' world, maybe...?

Over and over and over you say things that you seem
to think have something to do with things I said, but
over and over I have no idea how you got <whatever>
from anything I actually did say.

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

And I reiterate my statement that when someone
says that recent work of Chaitin says that JVN
was wrong, I ask for a hint regarding exactly _how_
Chaitin shows that JVN was wrong, then saying
"it's probably in the book" is no answer.

Ask me to justify something I've said at any 
time in my life about mathematics. I will _tell_
you what the proof _is_ (or tell you _exactly_
where to find the proof, _or_ in rare cases
say no, I really didn't know what I was talking
about.) People don't usually try to prove things
by saying it's probably in a book somewhere...

>  (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?

Sigh. If we are talking about "random enough for
a given purpose" then JVN's _original_ comment
was just totally and utterly stupid. Of course there
is no problem coming up with an arithmetic RNG
which is good enough for a _given_ purpose.

_If_ we decide for some reason to assume that
JVN was not a total moron then it's extremely
clear that he was not talking about finding an
RNG that's good enough for a _given_ purpose -
the only non--moronic interpretation is the
problem of finding an arithmetic RNG that's
good enough for _any_ purpose (one RNG).

>> 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,

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,

I don't think that Godel numbers are a "problem". 

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

Here's the original question:

<original question with a bit of context>

>That's what I was always taught, however in the light of 
>Gregory Chaitin's work or randomness in arithmetic: 
>
>	<http://www.cs.auckland.ac.nz/CDMTCS/chaitin/>
>
>JVN may have been wrong. 

??? There's a _lot_ of stuff there. 

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

</original question with a bit of context>

Um, that's not the question at the top of the thread,
that's my original question that's led to this hoo-haw.

What do you imagine I meant by '"truly random"'?
Never mind. Do you really think that somehow
the phrases "truly random" and "perfectly random"
mean something different to me?

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

Of course. This is clear. This is awesomely clear,
whether we know anything about Chaitin's work
or not! So it also seems clear that it's not what
I was asking about...

>  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_ "construction"? Not sure whether or not you're
referring to "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"
If that's what you're referring to, I think it's a little
vague to be called a "construction". But yes,
a person _could_ do interesting things
along those lines.

But if the "algorithm" is not guaranteed to stop
then it's not an algorithm. An RNG that takes
infinitely much time to return sometimes is
not very useful. (And if we put some upper
limit on the number of steps we've lost our
pristine perfection...)

>> >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 tend to doubt that I said anything about "GIVEN
complete information." I did say something about
"given complete information". A _hypothesis_
is not an assertion. Here are two true theorems 
of mathematics:

Thm1 If x is a real number then x^2 >= 0.

Thm2 GIVEN a real number x such that x^2 < 0
  it follows that x^2 >= 0.

Those are both true. The hypothesis in one does
not contradict the assertion in the other - it
can't, being just a hypothesis.

So in fact there was nothing contradictory about
what I said, _quite_. But I agree I didn't say what
I meant very well - this is the first I recall your
mentioning this particular ""contradiction" - I
tried to clarify what I meant a few lines up.

> 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,

The seeming contradictions that you've mentioned
previously are no contradictions at all, any more
than saying every tomato is red and here is a green
apple is a contradiction. If I say that and if you happen
to think that apples are tomatoes then it's a contradiction.
But apples are not tomatoes, and algorithms are not
physical systems - that takes care of all the 
"contradictions" you've pointed out previously.

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.

The bit about "until you deign to give us
your definition" would be appropriate _if_
you had _asked_ for a definition previously.

Since you asked: Zero-th, note that the
word "random" is used in many different
ways, even in mathematics. For example
if I slip and use the phrase "random variable"
below, that use of the word "random" is not
what we're talking about at all. Curiously.
(It's certainly a related notion, but for
example it makes no sense whatever
to ask how random a random variable
is - it's not the same use of the word.)

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.

What it seems to me makes sense is the
notion of a perfect RNG. A perfect RNG is
_not_ going to generate "perfectly random"
sequences - the ouput _could_ be

0000000000000000000....

That's only going to happen 0% of the time,
but the same is true of any other specific
sequence - an RNG that is constrained
so as not to generate that sequence is
"imperfect".

So to finally answer your question:

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 for example there is no correlation
between the output on one run of N bits
and the next run of N bits, because a pair
of runs of N bits is the same as a run of
2N bits, and a correlation would mean that
all sequences of length 2N were not equally
likely.)

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

>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?

When you're talking math contradictions are the
one evil. But there's nothing bad about tautologies,
in fact tautologies are all we have.

(That's using the colloquial meaning of "tautology", 
not the meaning in formal logic, the difference being
that colloquially anything that's necessarily true
for purely logical reasons is a tautology, while
in official logic tautologies are part of propositional
logic. Ie a logical truth in first-order logic like
"if every tomato is red and george is a tomato
then george is red" is not formally a tautology,
just because it's not part of _propositional_ logic,
it involves predicates.)

>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,

I know a lot of places where I can read lots of
proofs that Cantor was wrong about everything and
Godel was wrong about everything, etc. The reals
are countable. Fermat's last theorem is false. One of
these guys' main tools is refusing to define terms
when asked. This is why I find your comment about
my not "deigning" to define terms _offensive_, in 
case you're curious. Exactly where... lemme 
rephrase that: Exactly WHERE in this thread did
you or anyone else ask me to define some term
I was using?

Please be specific.

> 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? 

"Infinite information" is not going to allow one
to predict _anything_ about the output of a perfect
RNG, as I defined it above.

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

David C. Ullrich
***********************
"Sometimes you can have access violations all the
time and the program still works." (Michael Caracena,
comp.lang.pascal.delphi.misc 5/1/01)