# Thread: Help on a Turing Machine Question

1. ## Help on a Turing Machine Question

Hello,

Show that for each Turing Machine, M, there is a Turing Machine, M', which computes the same partial function as M, but which never moves left of the initially scanned square of any initial tape.

2. Originally Posted by Jessica.M
Hello,

Show that for each Turing Machine, M, there is a Turing Machine, M', which computes the same partial function as M, but which never moves left of the initially scanned square of any initial tape.
It does depend on how the TM is defined, I will assume that the initial tape
consists of a sequence of cells with a number of 1's and the rest of the tape

Suppose the reading head of TM M moves a maximum of X cells to the left of
the initial position. Then consider a TM M' that moves the block of 1's X+1
cells to the right (show this need never move to the left of the initial
position), then positions the reading head over the leftmost non blank cell
and then executes M.

RonL