Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help explain this Turing machine notation

  1. Oct 6, 2014 #1
    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/
     
  2. jcsd
  3. Oct 9, 2014 #2
    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).
     
  4. Oct 9, 2014 #3
    Thanks for the help!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Help explain this Turing machine notation
Loading...