Are Turing machines that move before assigning Turing complete?

222 Views Asked by At

A state in a Turing machine is an assignment and a move direction both depending on the current input.

But if we define Turing machines to be a move first and then an assignment both depending on the current input,

would this also be Turing complete?

e.g. instead of:

State X:
if 1 then change to 0 and move Left and goto state Y
if 0 then change to 0 and move right and goto state Z

We had rules such as:

State X:
if 1 then move left and change to 0 and goto state Y
if 0 then move right and change to 1 and goto state Z

Would this also represent a Turing complete system?

Also what about if we had a system like the following where each state always moved in one direction?:

State X:
    move Left
    if 1 then change to 0 and goto state Y
    if 0 then change to 1 and goto state Z
1

There are 1 best solutions below

0
On BEST ANSWER

The first example is, according to the comments, a finite state machine, and thus not Turing complete. Its only inputs are the head programming and the first tape symbol, and it cannot read anything it has written itself.

The second example, however, is Turing complete. One simple way to encode a standard Turing machine is to use only every second cell on the tape for actual information, and use the remaining ones to "turn around", if needed. So instead of the standard

X: If 0, write 1, move left, change to Y
   If 1, write 0, move right, change to Z

you would have something like

XR: If 0, write 1, move right, change to YLLLL
    If 1, write 0, move right, change to ZRR

and a corresponding code for XL. The state *LLLL says, regardless of writing, move left, change to *LLL, and corresponding for states *LLL and *LL, and for states *RRRR, *RRR and *RR.