Help explain this Turing machine notation

Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
2 replies · 2K views
mishima
Messages
576
Reaction score
43
Below is an image from a website article discussing a Turing machine. It is supposed to represent a Turing machine, but I don't really follow the notation. I assume this is part of Wolfram's book, "New Kind of Science", which I do not have a copy of. I have only ever seen a Turing machine represented as a 5-tuple (partial function that maps (s, x) to (s', x', d).

turing_rule.gif


article: http://blog.stephenwolfram.com/2007...-simplest-universal-turing-machine-is-proved/
 
on Phys.org
The top row reads, machine state is "on" tape is red, yellow, white, machine state is "off", tape is red, yellow, white, and it represents the six possible conditions that this Turing machine might find oat any step.

The bottom row shows how this Turing machine will respond to the six conditions listed in the top row. The little black things indicate one of two machine states. Call them "on" and "off". The colors indicate what color will replace the color just read at the current position on the tape. The position of the new state marker indicates which direction the Turing machine will move the tape.

So, if the machine state is "on" and the spot on the tape is red, then the spot will be replaced with yellow, the machine state will remain "on", and the tape will be stepped to the left.

If the machine state is "on" and the spot on the tape is yellow, then the spot will be replaced with red, the machine state will remain "on", and the tape will be stepped to the left.

If the machine state is "on" and the spot on the tape is white, then the spot will be replaced with yellow, the machine state will switch to "off", and the tape will be stepped to the right.

and so on.
See http://en.wikipedia.org/wiki/Wolfram's_2-state_3-symbol_Turing_machine for more.

The "triangles graphic" at the top shows the state of the tape as it is changed by the Turing machine. On quick inspection, I would say that this machine tends to scan the tape back and forth until it hits white in continuously widening scans. The tapes starts out all white except for one red or yellow dot (at the top of the "triangles graphic") and then broadens with continued processing (in the down direction).
 
  • Like
Likes   Reactions: FactChecker and Medicol
Thanks for the help!