Help explain this Turing machine notation

1. Oct 6, 2014

mishima

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

article: http://blog.stephenwolfram.com/2007...-simplest-universal-turing-machine-is-proved/

2. Oct 9, 2014

.Scott

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

3. Oct 9, 2014

mishima

Thanks for the help!