A TurNing Machine Question
(Simple but challenging)
A "TurNing Machine" operates in a two-dimensional space made up of cells which are equilateral triangles. It scans one cell at a time, and, on the basis of its current state and the symbol present in the cell, the machine will print a symbol, and turn right or turn left to penetrate the side of the adjacent cell opposite the base of the current triangle. As it moves into the new cell the machine takes on a designated new (or possibly the same) state. The penetrated side of the cell into which the machine moves becomes the new base of reference, and the process of printing, moving, and changing states continues in a precisely defined manner. The interest for the question proposed is in the behavior of such machines which begin their operation somewhere in an all blank (0) unbounded cellular space. As an example, consider the machine with two states, {q1,q2}, and a two-symbol alphabet, {0,1}, which has its behavior described by the following table:
| TurNing Machine |
|---|
| | 0
| 1 |
| q1 | 1 R q1 | 0 L q2 |
| q2 | 0 L q1 | (halt) |
When started on an all blank (0) cellular space in state q1, the machine above will go through 23 steps before finally halting, having traversed a region comprised of 18 triangular cells that in the end looks approximately like this:
/1\1/1\
|
\1/0\1/0\1/1\
|
/1\1/0\1/1\1/
|
\1/1\1/
|
|
The following TurNing Machine operating on symbols 0 and 1 has only one state, q1:
| TurNing Machine |
|---|
| | 0
| 1 |
| q1 | 1 R q1 | 0 L q1 |
This machine has no "halt". Therefore, it will operate forever in its two-dimensional space of triangular cells. It is fascinating to watch its operation. It has so far been observed continuously for 10,000 steps leading to the following question about the machine. Will the machine's traversed region continue to grow forever, or will the machine eventually settle into a (static) fixed loop with the region of traversal finally ending its growth?
Another way of viewing the question is to consider it to be a problem involving cells of three colors (as in Wolfram's NKS): white, gray, and black. The unbounded cells are all initially white (untraversed). The machine navigates exactly as before, but it has the following rules involving a cell's color instead of a symbol 0 or 1, and no numbered state is involved:
If the cell is white or gray it turns black, and the machine then turns and enters the (adjacent) cell on the right,
or
if the cell is black, it turns gray, and the machines turns and enters the cell on the left.
With these restated rules the original question becomes, "Will the black and gray region continue to grow forever, or at some point will the machine settle into a fixed (static) loop?
--Allen Brady ( www.cse.unr.edu/~al)
24 July 2010