1

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.

zaa
  • 708
  • 1
    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? – Steven Stadnicki Feb 18 '13 at 17:44

1 Answers1

1

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 ;-)

dtldarek
  • 37,381