1
$\begingroup$

Is it possible that part of sequence is more complex than all sequence because the best way to encode it is to use the complete sequence and starting and ending positions of the fragment.

Maybe, for example, string of hexadecimal digits of $\pi$. Or something else.

$\endgroup$
1
  • 1
    $\begingroup$ If both sequences are intended to be infinite, then any added 'starting point' complexity will be drowned out in the long run. If both are finite then I believe there can be a logarithmic gap. And if one is finite and one is infinite, how are you comparing them? $\endgroup$ – Steven Stadnicki Feb 18 '13 at 17:44
1
$\begingroup$

I am not sure, but I would say yes, however, only by $O(|n|)$ (the length of program/TM that would truncate such sequence including the desired length of output sequence). An example of such sequence might be some prefixes of output of Busy Beavers. Still, this is just my intuition.

I hope it helps ;-)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.