Turing Snakes

A Turing snake is a computational device similar to a Turing machine in which a "snake" with a head and tail tours a colored regular graph. As the head of the snake passes over a vertex, it measures its own internal state and the color of the vertex under its head. It uses these measurements to determine its new state, to recolor the vertex under its head, and to select which edge of the graph over which to slither. (The snake cannot coil back immediately over its own tail.)

In this Demonstration, you select which of six sample regular graphs you wish to examine, the update rule used by the Turing snake from the set of all two-state, two-color rules, the initial state of the head, the initial coloring of the graph, the vertex over which the snake's head is initially positioned, and the number of moves to be made by the snake.

The system outputs three graphics. The leftmost graphic shows the movements of the snake over the selected graph induced by the selected parameters. Edges traversed by the snake are shown in green; untraversed edges are in red. The middle graphic shows the evolution of the system on a flattened version of the graph. As with many diagrams used in A New Kind of Science, "time" goes forward as you move down the rows. A red site indicates that the head is at that site and is in state 1; a purple site indicates that the head is at that site and is in state 2. The rightmost graphic shows the causal network created by the system.