From: Peter de Blanc (peter@spaceandgames.com)
Date: Sun Jun 22 2008 - 23:21:05 MDT
J. Andrew Rogers wrote:
> The length of a program's output is not its complexity.
Agreed.
> And where does this number exist?
If you'll look at the program I supplied, you'll notice a 0 at the end.
If you run the program, it'll output a near-copy of itself, different
only in that the 0 has been replaced with a 1. In general, program N
will output a near-copy of itself, except the N at the end will be
replaced with N+1.
My argument does not depend on how exactly you choose to measure the
complexity of a program; the only fact we use is that there are
finitely-many programs below any given complexity bound. Since we have
specified an infinite sequence of programs, one of those programs must
be the first in the sequence to exceed the complexity bound. Therefore
that program is more complex than the program preceding it in the sequence.
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT