Praveen2710

yes thank you

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

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 ?

Hi I have an assignment question which I have no clue on how to start.I am posting the question. I would really appreciate if someone could guide me on how to solve it. Question: Show that for every time-constructible T: N → N, if L ∈ DTIME(T(n)), then there is an oblivious TM that decides L in time O(T (n) log T (n)). Any material that will help solve it or any similar examples would be highly appreciated.