<p>This isn't a research-level question, so it's probably better on the normal Computer Science Stack Exchange.</p>
<p>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 <span class="math-container">$\Omega(n^2)$</span> 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.</p>

CC BY-SA 4.0
2022-06-08T01:29:01.037Z
2022-06-08T01:29:01.037Z
Jake
<p>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 <span class="math-container">$s$</span>, where <span class="math-container">$|s| = 10^{100}$</span> for example.  Then if we wanted to learn the value of <span class="math-container">$s_i$</span>, the <span class="math-container">$i$</span>th value in the string, could we do this in say time polynomial in the length of the string?</p>
<p>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 <span class="math-container">$s_i$</span>, the ith value in the array, in time polynomial in <span class="math-container">$|s|$</span>, regardless of the chosen value of <span class="math-container">$i$</span>?  Or would the head have to &quot;slide over to <span class="math-container">$i$</span>&quot; with some cap on it's speed, so it could not do this task efficiently?</p>

CC BY-SA 4.0
2022-06-08T05:34:38.073Z
Cross-posted: https://cstheory.stackexchange.com/q/51560/5038, https://cs.stackexchange.com/q/152155/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).
D.W.
<turing-machines><search-problem>
Can a Turing machine quickly move to any position of a large string?
user918212
# Can a Turing machine quickly move to any position of a large string?

(Asked by: username_0 on 2022-06-08)

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?

**Tags:** turing-machines, search-problem

> **Comments:**
> **username_1**: Cross-posted: https://cstheory.stackexchange.com/q/51560/5038, https://cs.stackexchange.com/q/152155/755.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  

---

## 1 answers

### Answer by username_2 on 2022-06-08. Score: 0 | Accepted answer

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.


---

