# Can a Turing machine quickly move to any position of a large string?

I hope this question is not too basic and I am not missing something dumb. But suppose we simulated a Turing machine on a long string $$s$$, where $$|s| = 10^{100}$$ for example. Then if we wanted to learn the value of $$s_i$$, the $$i$$th value in the string, could we do this in say time polynomial in the length of the string?

The issue I am having is differentiating between the theoretical construction of the Turing machine vs. real computers which can for example index arrays in constant time due to their structure in memory. Could a TM obtain $$s_i$$, the ith value in the array, in time polynomial in $$|s|$$, regardless of the chosen value of $$i$$? Or would the head have to "slide over to $$i$$" with some cap on it's speed, so it could not do this task efficiently?

• – D.W.
Jun 8 at 5:34

But, to answer the thrust of your question: no, they cannot jump to the middle, and it can be viewed as a limitation of the model. You can use this fact to prove $$\Omega(n^2)$$ lower bounds on the language of palindromes for a single-tape TM, for example. To avoid this, there are various random access Turing machine models used in the literature.