**From:** Peter de Blanc (*peter@spaceandgames.com*)

**Date:** Mon Jun 23 2008 - 02:32:27 MDT

**Next message:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Previous message:**William Pearson: "Re: [sl4] Is there a model for RSI?"**In reply to:**J. Andrew Rogers: "Re: [sl4] Is there a model for RSI?"**Next in thread:**Charles Hixson: "Re: [sl4] Is there a model for RSI?"**Reply:**Charles Hixson: "Re: [sl4] Is there a model for RSI?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Previous message:**William Pearson: "Re: [sl4] Is there a model for RSI?"**In reply to:**J. Andrew Rogers: "Re: [sl4] Is there a model for RSI?"**Next in thread:**Charles Hixson: "Re: [sl4] Is there a model for RSI?"**Reply:**Charles Hixson: "Re: [sl4] Is there a model for RSI?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

*
This archive was generated by hypermail 2.1.5
: Wed Jul 17 2013 - 04:01:03 MDT
*