From: Vladimir Nesov (robotact@gmail.com)
Date: Mon Jun 23 2008 - 05:03:55 MDT
On Mon, Jun 23, 2008 at 9:38 AM, J. Andrew Rogers
<andrew@ceruleansystems.com> 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 robotact@gmail.com http://causalityrelay.wordpress.com/
This archive was generated by hypermail 2.1.5 : Wed Jul 17 2013 - 04:01:03 MDT