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.



  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


To maximize the prospect of vertices that are "close" to each other in the graphic being numbered close to each other and, thus, to facilitate a visualization of the system's evolution, a tentative version of each of the graphs is embedded as a layered directed graph. The vertices are then renumbered by sorting their vertical coordinates.
An interesting experiment would be to see which snake updating rules tend to be most efficient in causing the snake to traverse the highest proportion of graph edges. Are there rules that robustly succeed in this regard for a large number of graphs?
Although this Demonstration presents a two-state snake traversing a two-color 3-regular network, much of the code can be deployed to study more general snakes.
The pun implicit in the title is intended.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.

Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-Step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2017 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+