From: kevin@axon.cs.byu.edu (Kevin Vanhorn)
Date: Tue, 25 Jan 94 08:05:06 PST
To: doug@netcom.com
Subject: Randomness of a bit string
In-Reply-To: <199401250634.WAA08809@mail.netcom.com>
Message-ID: <9401251554.AA00533@axon.cs.byu.edu>
MIME-Version: 1.0
Content-Type: text/plain


Doug Merritt writes:

>A trivial example of this: pick some constant bitstring of length 32 or less.
>Call it K. Now look at the class of algorithms specifiable by the
>C code fragment printf("%x", K) [...]
>Next consider a program that computes an output by multiplying some
>input by two. [...]

Both of these examples are flawed, because the functions used are not
universal.

>Proceeding in this fashion, it becomes increasingly clear that the
>randomness of the output of an algorithm can only be measured relative
>to the properties of the class of algorithms being considered.

Not quite right.  The class of algorithms usually considered is the class of
ALL algorithms.  It is the ENCODING of algorithms that counts.  The
correct statement is

  "...the randomness of a string can only be measured relative to the
  particular encoding of algorithms being considered."

-----------------------------------------------------------------------------
Kevin S. Van Horn     | It is the means that determine the ends.
kevin@bert.cs.byu.edu |