New answers tagged

3 votes
Accepted

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

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$. ...
user avatar
  • 141k

Top 50 recent answers are included