# Turing Snakes

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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

[more]
Contributed by: Seth J. Chandler (March 2011)

Suggested by: Ed Pegg Jr

Open content licensed under CC BY-NC-SA

## Snapshots

## Details

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.

## Permanent Citation