Oblivious Turing Machine

[Praveen2710]

Hi,

I am trying to convert a turing machine to oblivious turing machine and I was going through an example but could not understand some part of it.

The situation is such . There exists a K-tape turing machine M, that has been converted in M' a single tape turing machine the example says we can convert this M' to M'' oblivious turing machine accordingly

 

We really only need to make a few changes to this to make M′ into an oblivious TM M′′:

 

-When M′ updates the encoding in its right-to-left sweep, it may need to move the ˆ marker to the right. However, M′′ cannot stop and move right when it finds the hat, because it is oblivious. Therefore, the head of M′′ must, on its right-to-left sweep, move LRL every time M′ would move L, so its movement pattern will look like LRLLRLLRL... That way, the head always has the opportunity to move the ˆ marker either left or right when it is encountered.

 

here ^ represents head of each tape in the initial problem.

I do not understand why M'' cannot move to the right as it is oblivious ?

[mooeypoo]

The point of oblivious turing machines is that the direction of their movement doesn't depend on the input, but is a function of time.

So, the head has some L/R movement, but it doesn't depend on the input.

 

M can't just move to the right on some decision based on what it gets as an input, it has some movement that is unrelated to the input. It will keep going wherever it is set up to go regardless of what it intercepts.

 

Does this explain it better?

 

This might help: http://cseweb.ucsd.edu/classes/sp11/cse201A-a/ln412.pdf (Especially page #2, it goes over the definition of oblivious turing machines)

[Praveen2710]

I understand that but my question is how will the head change if we do not consider the input.
I assume for every left the normal turing machine makes oblivious turing machine does a L-R-L .
I see that if head moves left then we edit the head in first left move.
I see if input is not head we just do a left-right-left and move to the next input (we are doing a sweep from right to left)
I do not get how to change head to right as doing a left-right-left will only move head from current position to left and then back to current we never visit right of current input to make it the head

[mooeypoo]

I understand that but my question is how will the head change if we do not consider the input.

I assume for every left the normal turing machine makes oblivious turing machine does a L-R-L .

I see that if head moves left then we edit the head in first left move.

I see if input is not head we just do a left-right-left and move to the next input (we are doing a sweep from right to left)

I do not get how to change head to right as doing a left-right-left will only move head from current position to left and then back to current we never visit right of current input to make it the head

That's the entire point of oblivious turing machines -- you need to find the way to move the head so that you can still respond to reads.

 

So, in this case, moving the head LRLLRLLRL... would still move it in general to the left, but would also give it the option to repeat a place for input it already intercepted -- hence, you will have a chance to 'rewrite'.

 

Does this make it clearer?

[Praveen2710]

yes thank you