Re: [sl4] Is there a model for RSI?

From: Vladimir Nesov (
Date: Mon Jun 23 2008 - 05:03:55 MDT

On Mon, Jun 23, 2008 at 9:38 AM, J. Andrew Rogers
<> wrote:
> If your "counter" does not occupy memory then the complexity is constant.
> If it does occupy memory, it is eating bits as N grows on a finite machine.
> Either way, you have a problem.
> All that aside, your assertion is contrary to some pretty rudimentary (for
> this list) theorems in mathematics. Without inspecting your argument, that
> alone should have suggested something was amiss.

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.

Vladimir Nesov

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