--- On Thu, 1/8/09, Vladimir Nesov <[email protected]> wrote: > > 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.
Well, it is true that you can find |P| < |Q| for some cases of P nontrivially simulating Q depending on the choice of language. However, it is not true on average. It is also not possible for P to nontrivially simulate itself because it is a contradiction to say that P does everything that Q does and at least one thing that Q doesn't do if P = Q. -- Matt Mahoney, [email protected] ------------------------------------------- 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
