From: J. Andrew Rogers (andrew@ceruleansystems.com)
Date: Mon Jun 23 2008 - 09:10:54 MDT
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
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT