I have a question regarding Turing machines.

Are these two tapes the same thing?

First one = _ _ _ _ * A A A B B B

Second one = * A A A B B B

_ denotes a blank tape cell.

  • $\begingroup$ What does $*$ denote? $\endgroup$ – Hans Hüttel Dec 2 '17 at 8:33

Well, kind of, but not really. A defining characteristic of a Turing machine is its current head position, where the head is reading and writing from the tape. These two tapes appear to be identical, but the tape head isn't in the same place. It depends on how you define "the same thing": the tapes themselves are the same, but the Turing machines' states are not.


Not the answer you're looking for? Browse other questions tagged or ask your own question.