Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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 Answer 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 ;-)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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