Is there a name for a single state turing machine with two heads?

173 Views Asked by At

I noticed that if we had a Turing machine that looks not only at one position on a tape but two positions next to each other it is possible to make a single-state Turing machine.

For example the tape might be:

10010101010G01011010
          ^^

The state could be encoded into the tape, so the machine wouldn't have to remember it. If the heads are moving right it would encode the state into the second head and if the heads are moving left it would encode the state into the first head. That way, one of the heads could always "read" the state.

I also noticed that we could also encode the head position into the tape and then this could as well be encoded into a set of replacement rules. e.g. the rule "0G-->B1 move L" would be the replacement rules:

  1[0G] --> [1B]1
  0[0G] --> [0B]1

Where now we also extra symbols [ and ] to represent the head position.

Is there a name for such a Turing machine? I find it interesting in that such a machine would be completely dumb. As in it would have no memory or state. It's memory would be entirely in the environment on the tape. I wonder if Turing had used this model instead of the one with states, would we view computers differently? (I guess he used the state model because he was thinking about states of the brain.)