Algorithmic Randomness is Universal (Was Re: Godel's Dualism ...)

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 05/17/04 

Date: 17 May 2004 09:08:07 -0700

Hi Stephen,

I wrote a long reply but it got lost in a google server error. Your
claim that algorithmic randomness is not universal seems to me
misguided. Please have a look at the comments below.

"Stephen Harris" <cyberguard1048-usenet@yahoo.com> wrote in message news:<VNVpc.107$BJ6.40@newssvr27.news.prodigy.com>...
> The algorithmic theory of randomness explicates this
> idea of regularity with the help of Turing machine
> programs. One considers a finite string as regular,
> or nonrandom, if it can be generated by a simple
> program, i.e., if its program-size complexity is
> considerably smaller than its length. Accordingly,
> a finite string is defined to be random if its
> program-size complexity is roughly equal to its
> length, i.e., if it cannot be compressed to a shorter
> program.

Yes, so far, correct.

> (Note that this notion is relative to a chosen programming
> language or coding system; a finite string may be random
> in one but nonrandom in another.)

This comment is useless as it stands because it is not generally true.

Please listen to what Cover and Thomas say in "Elements of Information
Theory", pp. 148-149

"Theorem 7.2.1 (Universality of Kolmogorov complexity): If U is a
computer, then for any other computer A,
 
             K_U(x) \leq K_A(x) + c_A (7.3)
 
 for all strings x E {0, l}*, where the constant c_A does not depend
on x.

Proof: Assume that we have a program p_A for computer A to print x.
Thus A(p_A) = x. We can precede this program by a simulation program
s_A, which tells computer U how to simulate computer A. The computer U
will then interpret the instructions in the program for A, perform the
corresponding calculations and print out x. The program for U is p =
s_Ap_A and its length is
    l(p) = l(s_A) + l( p_A ) = c_A + l( p_A) (7.4)

where c_A is the length of the simulation program. Hence,

 K_U(x) = min_{p:U(p)=x} l(p) \leq min_{p:A(p)=x} (l(p) + c_A) =
K_A(x) + c_A

(7.5)

for all strings x. QED.

The constant c_A in the theorem may be very large. For example, A may
be a large computer with a large number of functions built into the
system. The computer U be a simple microprocessor. The simulation
program will contain the details of the implementation of all these
functions, in fact, all the software available on the large computer.
The crucial point is that the length of this simulation program is
independent of the length of x, the string to be compressed. For
sufficiently long x, the length of this simulation program can be
neglected, and we can discuss Kolmogorov complexity without talking
about the constants.

  If A and U are both universal, then we have

   |K_U(x) - K_A(x)| < c (7.6)

for all x. Hence we will drop all mention of U in all further
definitions. We will assume that the unspecified computer U is a fixed
universal computer."

which corresponds to the "rather abstract programming language" of
Chaitin.

You are wrong in saying (just implying?) that algorithmic randomness
is not universal. Your claim that

"this notion is relative to a chosen programming language or coding
system; a finite string may be random in one but nonrandom in
another."

is indicative of the misguidence of Panu Raatikainen. I wholeheartedly
advise you to take the comments written in this book on information
theory to be much more authoritative than some article in some
philosophical journal.

Your argument can be valid for only contrived examples of trivially
short strings. For sufficiently long strings, your argument is wrong,
the Kolmogorov complexity is universal, and so is the definition of
algorithmic randomness which I suppose you already know well.

Take for instance, C versus LISP. The meaning of randomness would seem
to be ill-defined for short strings, but for long strings it does not
matter and that is precisely what we are interested in. It might not
be easy to implement LISP in C, but the size of the simulation program
does not matter the least bit asymptotically. Obviously, a slightly
inflated simulation program for human standards doesn't prevent us
from using C language as a universal computer in Kolmogorov
complexity. The fact is that one can simulate C in LISP and LISP in C
with a constant program, and that is all we should care about.

I challenge you to prove your claim for all binary strings. Pick two
universal computers of your liking, and try to show that the
definition of algorithmic randomness is not universal, i.e. it is
*relative* to the "coding system". You will see that it is valid only
for a small number of short strings. That is, I seek your elucidation,
please prove your claim to me mathematically, or retract it. It's a
mathematical question, not a merely philosophical one.
 
> Panu points out an obvious shortcoming in regarding a
> sorting system which allows admittance of nonmembers
> (some nonrandoms included into a random ensemble)
> as a continuum.

We shall see whether the received view or Panu's enlightened
alternative view is in error. I have not finished my analysis yet,
I'll gladly tell you when it's done, both here, and on FOM list. [!]

Please consider that my extreme skepticism of Panu's mathematical
prowess is not only out of respect for Chaitin, but also for
researchers in Kolmogorov complexity like Vitanyi, Schmidhuber and
others, as well as philosophers like Torkel Franzel and yourself.

Best Regards,

PS: In the rest of your comments you are telling me that a random real
has not the same complexity as a random integer, which I know well. In
digital physics, the universe is finite, so there is no need to think
about reals, random or not. We have only integers, and what I'm saying
is that I suspect the complexity of integers in nature is greater than
PRNGs of Wolfram. See however, the recent comments of Ed Frenkin on
sci.physics.discrete on the issue, which I found quite interesting.
http://groups.google.com/groups?dq=&hl=en&lr=&ie=UTF-8&group=sci.physics.discrete&selm=10afdki31getq79%40news.supernews.com 

--
Eray Ozkural
[!] I don't have much time for this task, I can spend about an hour
every few days on these high-flautin intellectual issues...

Relevant Pages

  • Algorithmic Randomness is Universal (Was Re: Godels Dualism ...)
    ... > program, i.e., if its program-size complexity is ... "Theorem 7.2.1 (Universality of Kolmogorov complexity): ... for all strings x. QED. ... You are wrong in saying that algorithmic randomness ...
    (comp.theory)
  • Algorithmic Randomness is Universal (Was Re: Godels Dualism ...)
    ... > program, i.e., if its program-size complexity is ... "Theorem 7.2.1 (Universality of Kolmogorov complexity): ... for all strings x. QED. ... You are wrong in saying that algorithmic randomness ...
    (comp.theory)
  • Re: Raatikainens critique of Chaitin
    ... > Since I don't understand what you mean by 'universality of algorithmic ... > complexity' I can't tell. ... We don't even need these 'indexing arguments' ... > of its strength in any reasonable sense: fix a theory T and vary the ...
    (comp.theory)
  • Re: Raatikainens critique of Chaitin
    ... > Since I don't understand what you mean by 'universality of algorithmic ... > complexity' I can't tell. ... We don't even need these 'indexing arguments' ... > of its strength in any reasonable sense: fix a theory T and vary the ...
    (sci.math)