Help explain this Turing machine notation

Click For Summary
The discussion centers on the representation of a Turing machine as depicted in an article related to Stephen Wolfram's "A New Kind of Science." The representation diverges from the traditional 5-tuple notation commonly used to describe Turing machines. The article illustrates a Turing machine with two states, "on" and "off," and a tape that can display three colors: red, yellow, and white. The top row of the graphic outlines the possible conditions of the machine, while the bottom row details the machine's responses based on its current state and the color read from the tape. For instance, if the machine is "on" and reads red, it replaces it with yellow, remains "on," and moves left. The discussion notes that the machine appears to scan the tape back and forth, gradually expanding its search area, starting from a single colored dot on an otherwise white tape. The conversation emphasizes the unique notation and behavior of this specific Turing machine model.
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/
 
Technology news 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 FactChecker and Medicol
Thanks for the help!
 
Learn If you want to write code for Python Machine learning, AI Statistics/data analysis Scientific research Web application servers Some microcontrollers JavaScript/Node JS/TypeScript Web sites Web application servers C# Games (Unity) Consumer applications (Windows) Business applications C++ Games (Unreal Engine) Operating systems, device drivers Microcontrollers/embedded systems Consumer applications (Linux) Some more tips: Do not learn C++ (or any other dialect of C) as a...

Similar threads

Replies
29
Views
5K
  • · Replies 9 ·
Replies
9
Views
2K
  • · Replies 15 ·
Replies
15
Views
2K
  • · Replies 5 ·
Replies
5
Views
1K
  • · Replies 2 ·
Replies
2
Views
500
  • · Replies 3 ·
Replies
3
Views
1K
Replies
4
Views
2K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 13 ·
Replies
13
Views
1K
  • · Replies 0 ·
Replies
0
Views
2K