I am trying to understand oblivious Turing machines. According to the book of Arora and Barak, a TM $M$ is oblivious if the location of each of its heads at the $i$-th step of execution on input $x$ is only a function of $|x|$ and $i$ for every input $x\in{\{0,1\}^*}$ and $i\in{\mathbb{N}}$.

Here is my understand, suppose at step $t$, the head of tape $k$ is at position $p$, and the transition to the step $t+1$ will move the head to the right, i.e., to position $p+1$. However, the position function of step $t+1$ yields position $p-1$ for tape $k$. Then the machine will need to move all the content of tape $k$ two cells to the left and mark the symbol at position $p-1$ as head symbol.

enter image description here

I don't know if my understanding is correct. But if it is correct, the oblivious TM needs to store some symbols when it scans from right to left and shift the content. Like in the example, the OTM also needs to remember 2 symbols to make a correct shift. If the function can generate any position at any step, say $p-k$, it seems that the TM needs to be able to store a variant number of symbols, which seems to be hard to implement if we want to use an oblivious TM to simulate a standard TM.

Also I'm not sure if this is what the book really means because the content of the work tape is right after the input content, it seems that we can't shift the work tape content to the left because it will override the input content (although we can shift all the content to the left...).

  • $\begingroup$ The position function tells whether the head moves one step to the left, one step to the right, or (depending on your version of the TM model) stay put. It cannot jump. So the situation you describe isn't possible. It also has nothing to do with obliviousness. Obliviousness is about the head movement not depending on the input. $\endgroup$ – Yuval Filmus Oct 4 '19 at 13:39
  • $\begingroup$ Also, it's not clear why the machine should shift the contents of its tape. The tape is immobile. Only the head moves. When the head moves left, the tape doesn't change at all. There is no need to move any content. $\endgroup$ – Yuval Filmus Oct 4 '19 at 13:41
  • $\begingroup$ @YuvalFilmus Thank you for your comment. My question is the OTM tries to simulate a standard TM. The standard TM will move the head to the right, but the OTM position function requires the head to move to the left. So I think if the OTM just moves its head to the left without changing the tape content, it will point to the wrong symbol. $\endgroup$ – Snjór Oct 4 '19 at 21:18
  • $\begingroup$ You are asking how to implement an oblivious universal Turing machine. This is not so clear from your post. The textbook you mention should contain a description of such a machine. Have you looked at it? What part of it is unclear? $\endgroup$ – Yuval Filmus Oct 5 '19 at 0:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.