From: rollo@artvark.com (Rollo Silver)
Date: Tue, 2 Apr 1996 20:46:36 +0800
To: Carl Ellison <cme@acm.org>
Subject: Re: "Random Sequence"
Message-ID: <v02130502ad85efd99ac3@[204.134.0.172]>
MIME-Version: 1.0
Content-Type: text/plain


>At 07:25 AM 3/31/96 -0700, Rollo Silver wrote:
>>The paper "On the Effective Definition of 'Random Sequence'", by Michael
>>Levin, Marvin Minsky, and Roland Silver can be viewed (and downloaded, and
>>printed) from my website <http://www.artvark.com/artvark>.
>
>Rollo,
>
>        I read the paper and it's nice work -- but it departs from current
>definitions of random sequences in that it assumes you specify the countable
>set of machines trying to test for non-randomness first and then generate a
>sequence to fool that set of machines.  Current definitions of randomness
>assume an infinite set of testing machines, often limited to polynomial time
>and space, and a sequence generator that must defeat them all without
>knowing anything about them.  Such sequences are, in a sense, "more random"
>than the ones your paper dealt with -- I believe.  Did I miss something?

* It's a bit anachronistic to say in 1996 that a paper written 30 years
earlier "departs from current definitions of random sequences." The authors
may have been brilliant, but they weren't prescient. <g>

I can't imagine how a computer could be smart enough to defeat an infinite
set of guessing machines without knowing ANYTHING about them. In fact,
what's wrong with this argument: call the "fooling" machine Frank, and one
of the "guessing" machine Gert. You say that Frank doesn't need to know
anything about Gert. Let me suppose however that Gert DOES know about
Frank. In that case, Gert can simulate Frank and "guess" his output, thus
foiling Frank's attempts to fool Gert!

Maybe it's the "polynomial time & space". That restricts the guesser-domain
considerably, compared with our very weak requirement that the guessers can
be any Turing machines whatever -- as long as the set of them is
effectively calculable.

BTW, is the set of ALL finite automata effectively calculable? I suspect
maybe so. If so, by essentially the argument given in the paper, there is a
computer (Turing machine) that can fool them ALL.

I hope it's okay to cc this note to coderpunks. It's not about coding per
se, but it may shed some light on what "randomness" means, and on
"computable randomness", which sounds appropriate for coderpunks to me.

------------------------------------------------------------------------
Rollo Silver      | The CDA means  | Artvark / PO Box 219
505-586-0197      | lost jobs and  | San Cristobal, NM 87564 USA
rollo@artvark.com | dead teenagers | http://www.artvark.com/artvark/