0
$\begingroup$

Note this question was originally asked on Theoretical CS Stack Exchange, but it is not a research level question so it is being closed, and I am asking here instead.

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?

$\endgroup$
4
  • $\begingroup$ What kind of TM, and where/how is $i$ given? $\endgroup$ Jun 8, 2022 at 4:36
  • $\begingroup$ Cross-posted: cstheory.stackexchange.com/q/51560/5038, cs.stackexchange.com/q/152155/755. Please do not post the same question on multiple sites. $\endgroup$
    – D.W.
    Jun 8, 2022 at 5:34
  • $\begingroup$ Your question has already received a proposed answer on TCS.SE. I'm surprised that you've re-posted it here. It would be appropriate to mention that and explain why you didn't find that answer satisfactory. Posting without revealing that you've received one answer could be considered impolite to answerers here, who might spend time to answer without realizing that you've already gotten an answer. $\endgroup$
    – D.W.
    Jun 8, 2022 at 5:37
  • $\begingroup$ In the future, if you realize that you've posted on the wrong site, and it hasn't been answered yet, it would be better to delete the copy on the wrong site before posting on a new site, so it doesn't risk wasting people's time. $\endgroup$
    – D.W.
    Jun 8, 2022 at 5:37

1 Answer 1

3
$\begingroup$

It depends.

1: If there are at least $\lceil \lg |s| \rceil$ unused cells after the end of $s$ and the head starts within $s$, then the answer is yes.

Here is how. Start from the beginning of $s$. Insert the binary representation of $i$ after the first symbol of $s$ (you can do this by copying the rest of $s$ $\lceil \lg |s| \rceil$ positions to the right). Call this the "counter". Now repeatedly do the following, until the counter reaches zero: decrement the counter by one, then copy the counter one position to the right and the next element of $s$ one position to the left. At any intermediate time step, the tape contains $s_1 s_2 \dots s_j$, then the binary representation of $i-j+1$, then $s_{j+1} s_{j+2} \cdots$, and each iteration increments $j$ by one and decrements the counter by one.

2: If the Turing machine's head starts outside of $s$, then the answer is no. The head might be arbitrarily far away from $s$ (say, a number of cells away that is exponential in $|s|$).

A Turing machine has no way to "jump" to a position. It doesn't have random access. Instead, it can only move the head one position per step. Also, it needs a way to keep track of how far to move the head.

$\endgroup$
5
  • $\begingroup$ How do you know when you've reached position $i$? $\endgroup$ Jun 8, 2022 at 5:41
  • $\begingroup$ @KellyBundy, good point. See updated answer. How does that look? Anything else I've missed? $\endgroup$
    – D.W.
    Jun 8, 2022 at 5:53
  • $\begingroup$ Looks ok, yes. Neat idea to move the counter through s. Not sure that's what they're asking, their question is rather unclear to me. $\endgroup$ Jun 8, 2022 at 6:11
  • $\begingroup$ Thank you for the answer and apologies for the mess up with cross posting. I do have one question about your answer: I am somewhat unclear as to how this algorithm does not run in linear time, as if I understand correctly you iterate over one position each step, so to reach index $i=10^{100}$ for example you need to perform $10^{100}$ of these steps? $\endgroup$
    – user918212
    Jun 8, 2022 at 14:15
  • $\begingroup$ @Generic, it does. That is polynomial in the length of the string. Linear time is polynomial time. $\endgroup$
    – D.W.
    Jun 8, 2022 at 17:37

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.