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/