First page Back Continue Last page Overview Graphics

Bit rotation

Notes:

Here are two solutions from a more complicated four state deterministic TM that moves both right and left over a 5-cell tape. This machine rotates the input bits one to the right: the blue (W) and green (X) states remember the previous bit when marching to the right, and the red (Y) and yellow (Z) states remember the rightmost bit while marching to the left to deposit it in the first tape position. An alternative implementation would have been a non-deterministic machine that guessed what bit to write in the first cell, remembered its guess, and then validated it against the last cell of the tape.