4

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
zooby
  • 4,343
  • What would be the next iteration for your machine? Reading the symbol it just wrote? Or will it move, read, write, then change state, like a standard TM, except the last two steps are done depending on the previous read? – Arthur Jul 28 '20 at 13:30
  • Yes you are right! – zooby Jul 28 '20 at 13:34
  • Yes you are correct. It wouldn't work. How about the last example? – zooby Jul 28 '20 at 13:35
  • So basically, everything it does is decided by the first symbol and the programming of the head? That sounds like a finite state machine to me. – Arthur Jul 28 '20 at 13:36

1 Answers1

3

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.

Arthur
  • 199,419