From: Peter de Blanc (peter@spaceandgames.com)
Date: Mon Jun 23 2008 - 02:32:27 MDT
J. Andrew Rogers wrote:
> Eh? I'm not following this.
Which step did you get lost at?
>>> All that aside, your assertion is contrary to some pretty rudimentary
>>> (for this list) theorems in mathematics.
>>
>> So show us these alleged theorems.
>
>
> While it has many expressions in literature (Chaitin has his own quaint
> pedestrian expressions of the concept), let us work from the fact that
> you are arguing against a trivial consequence of the Invariance Theorem,
> which opens Chapter 2 of my copy of Li & Vitanyi. It is prefaced with
> the following quote:
>
> "The following 'Invariance Theorem' is the cornerstone for the
> subsequent development of the [algorithmic information] theory. In fact,
> for many later applications it embodies the entire theoretical
> foundation."
Yup, it sure is a theorem. It doesn't contradict anything I've said.
I think I know what's confusing you. The claim I'm refuting is that a
machine can't output another machine which is more complex than itself
(you may suppose the input tape is blank; the program I gave doesn't
look at any input).
Now, if I had said "here's a program which outputs a *string* which is
more complex than itself", then that would sound pretty weird to you,
because you're automatically applying different definitions of
complexity to the program and the string. When I talk about the
complexity of a program, you might be thinking of the program's length,
but if I talk about the complexity of a string, you think of the length
of the shortest program which generates that string.
Of course, a program is nothing but a string. But you need to apply the
same definition of complexity to both strings; String 1 is a program and
String 2 is its output (in this case another program). If you assert
that S2 can't have greater Kolmogorov complexity than S1 then you're wrong:
Try running my lisp program. It'll output another program that you can
run. If you keep running them, you'll notice that each program outputs a
brand new program, distinct from all the previous ones. Since there
are infinitely many programs in this sequence, their complexity must
grow without bound. Thus one of them must output a program more complex
than itself.
- Peter de Blanc
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT