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?


1 Answer 1


This isn't a research-level question, so it's probably better on the normal Computer Science Stack Exchange.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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