On Fri, Jan 9, 2009 at 6:04 AM, Matt Mahoney <matmaho...@yahoo.com> wrote:
>
> Your earlier counterexample was a trivial simulation. It simulated itself but
> did
> nothing else. If P did something that Q didn't, then Q would not be
> simulating P.
My counterexample also bragged, outside the input format that
requested simulation. ;-)
>
> This applies regardless of your choice of universal TM.
>
> I suppose I need to be more precise. I say "P simulates Q" if for all x,
> P("what is Q(x)?") = "Q(x)=y" iff Q(x)=y (where x and y are arbitrary
> strings).
> When I say that P does something else, I mean that it accepts at least one
> input not of the form "what is Q(x)?".
This is a step in the right direction.
What does it mean for P to NOT accept some input? Must it hang? What
it P outputs "I understand you perfectly" for each input not in the
form "what is Q(x)?"? (Which was my counterexample IIRC.)
> I claim that K(P) > K(Q) because any description of P must include
> a description of Q plus a description of what P does for at least one other
> input.
>
Even if you somehow must represent P as concatenation of Q and
something else (you don't need to), it's not true that always
K(P)>K(Q). It's only true that length(P)>length(Q), and longer strings
can easily have smaller programs that output them. If P is
10^(10^100000) symbols X, and Q is some random number of X smaller
than 10^(10^100000), it's probably K(P)<K(Q), even though Q is a
substring of P.
--
Vladimir Nesov
robot...@gmail.com
http://causalityrelay.wordpress.com/
-------------------------------------------
agi
Archives: https://www.listbox.com/member/archive/303/=now
RSS Feed: https://www.listbox.com/member/archive/rss/303/
Modify Your Subscription:
https://www.listbox.com/member/?member_id=8660244&id_secret=123753653-47f84b
Powered by Listbox: http://www.listbox.com
