1

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.)

zooby
  • 4,343
  • As you note in the second part of the question, this is a standard technique for showing that finite string rewrite systems are Turing complete. I don't recall seeing a particular name for it, though. – hmakholm left over Monica Jun 24 '19 at 00:27
  • (Also, actual computer architectures are -- and have always been -- so different from Turing's formal model that is is hard to see how minor details like this would have influenced any "view" of computers). – hmakholm left over Monica Jun 24 '19 at 00:29
  • @Henning Well, I would say that Turing machines are often taught and the state is compared to the memory. And if you reset a computer half way through a calculation it would cause an error. But it is kind of interesting you could take the tape out of one computer and put it in another stateless computer and it would still keep going. But I suppose this is just redefining where the memory is. – zooby Jun 24 '19 at 00:34
  • 1
    i know this is old question but take a look at this https://link.springer.com/chapter/10.1007/978-3-540-73554-0_7 , stateless turing machine (turing machine with only one state) in the paper uses 3 head instead of just 2 – LLL Jul 21 '22 at 01:25
  • 1
    @LLL Interesting. I think it is perfectly possible (although with a bit more work and more characters) to do the same thing with 2 heads. I guess it's all the same thing in the end. – zooby Jul 21 '22 at 20:53

0 Answers0