**From:** J. Andrew Rogers (*andrew@ceruleansystems.com*)

**Date:** Mon Jun 23 2008 - 09:10:54 MDT

**Next message:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Previous message:**Vladimir Nesov: "Re: [sl4] Is there a model for RSI?"**In reply to:**Vladimir Nesov: "Re: [sl4] Is there a model for RSI?"**Next in thread:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Reply:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Reply:**Vladimir Nesov: "Re: [sl4] Is there a model for RSI?"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

On Jun 23, 2008, at 4:03 AM, Vladimir Nesov wrote:

*>
*

*> No, Peter is correct, and it is possible to construct even simpler
*

*> example. Say, our universal TM that runs the show only stops for two
*

*> programs of length less than 10: for P1 of length Len(P1)=3 and for P2
*

*> with Len(P2)=4. You can encode any other TM to run on this UTM, but
*

*> it'll be at least of length 10: for all P that stop, P<>P1, P<>P2,
*

*> Len(P)>=10. Let's say, the output of running P1 is Run(P1)=P3, and
*

*> output of P2 is Run(P2)=P4, but we make sure that also Run(P3)=P4.
*

*> Then, clearly Kolmogorov complexity of P3 is 3 (length of P1), and of
*

*> P4 it's 4 (length of P2), but P3 outputs P4, and P4 has greater
*

*> Kolmogorov complexity than P3.
*

Yes, the complexity of the state will vary -- a simple counter with no

other behavior is sufficient to see that this is true -- but that is

not the complexity of the machine. What does this have to do with

Peter's original assertion? It was very late when I responded, but he

did write something like:

"Suppose you have a machine that outputs a copy of itself, except that

somewhere in its memory it contains a model number, and each time it

makes a copy, it increments the model number on the copy.

This machine and all of its descendants comprise an infinite set of

distinct machines..."

It looked kind of like someone confusing machine complexity with state

complexity with some ambiguous handling of the complexity of the

control function, and it still does to me this morning. I could be

wrong, I was having trouble parsing his point.

The focus should have been on the very first line, since that had no

ambiguity: Exactly how does a machine output a copy of itself (with or

without the counter)?

J. Andrew Rogers

**Next message:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Previous message:**Vladimir Nesov: "Re: [sl4] Is there a model for RSI?"**In reply to:**Vladimir Nesov: "Re: [sl4] Is there a model for RSI?"**Next in thread:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Reply:**Peter de Blanc: "Re: [sl4] Is there a model for RSI?"**Reply:**Vladimir Nesov: "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
*