In 1992 I (Heiner Marxen) received this (slightly shortened) email,
containing a proof for the "chaotic" TM #4 by Newcomb Greenleaf.
Date: Tue, 28 Jul 92 11:43:30 EDT
From: (Newcomb Greenleaf)
Subject: Chaos never halts - a fairly simple proof
---------------------------------------------------
The CHAOS MACHINE NEVER HALTS: a Proof
In their 1990 study [MB90] of the 5-state busy beaver problem
Marxen and Buntrock introduced several interesting Turing machines
which their survey program had discovered. Most fascinating is the
"Chaos Machine" (CM), number 4 in their table, whose transitions
are given in our Table 1. They had run CM for over two billion
steps. But its chaotic behavior, exhibiting both a very rich
detailed structure and a great deal of unpredictability, did not
seem to allow an easy proof that it would run forever, and thus be
ruled out of the busy beaver sweepstakes. This note provides such
a proof.
The proof arose from our experience in running CM in a simulator
built in Scheme (which accounts for the fact that our notation is
rather LISPy). As described in [MB90] we developed the simulator
in "exponential" form in order to accelerate the simulation and
reduce the storage demands for the tape. Blocks are represented by
pairs. A block of n 1's is represented by (1 n) while a block of n
0's is represented by (0 n), and we refer to n as the exponent or
block-length.
The left side of a transition is given by a 4-tuple or "situation"
(old-state entry-direction old-symbol block-length)
Here entry-direction L means that we are starting at the leftmost
cell of the block, so that the tape head has just moved to the
right and the block has been taken from the right. Even when the
exponent is 1 it is crucial to keep track of the entry direction,
as will become apparent below. If the block-length (i.e. the
exponent) is suppressed, then there are twenty possible "reduced
situations"
(old-state entry-direction old-symbol)
Fortunately only ten of these reduced situations turn out to be
accessible, as given in Table 2.
The right hand sides of the transitions, as shown in Table 2, are
4-tuples
(new-state exit-direction transformed-block new-symbol)
The new-state, exit-direction, and transformed-block were
determined experimentally in a finite-tape simulator and they were
all verified by simple inductions, the case (b R 1) being the most
complex. The number of steps is also included to allow keeping a
running count of the number of steps of the original machine. The
possible values for new-symbol were determined first by running CM
in exponential form and will be verified in the proof of the
theorem.
The major factor in determining the new-symbol is the relationship
between the entry-direction and the exit-direction. Does the head
exit the block at the same or the opposite end from its entry?
Before proceeding to the theorem proper, we give the Opposite
Departure Rule and the Same Departure Rules to summarize.
Opposite Departure Rule. If entry and exit occur at opposite ends
of the block, then the new-symbol is different from the old-symbol.
Proof. The new-symbol is different from the old-symbol because the
two blocks are taken from the same half of the tape where they are
adjacent. The only possible exception would be a block of 0's at
the end of the tape, but by taking such blocks large enough it can
be insured that the exit occurs at the same end as the entry.
When entry and exit occur at the same end of the block it is
necessary to look at the transformed block of the previous
transition to determine the new-symbol.
Same Departure Rules. If entry and exit occur at the left (resp.
right) then the new-symbol is found at the right (resp. left) of
the previous transformed block.
Proof. Suppose that entry and exit both occur at the left. Then
the block has been taken from the right half of the tape and the
previous transformed block is to be found at the right of the left
half of the tape. When we exit from the block at the left, the new
block will be taken from the left half of the tape, and the symbol
will be at the right of the previous transformed block. Note that
the new block may be a proper subset or a proper superset of the
previous transformed block.
Now we can state our main theorem whose corollary will be that CM
runs forever. To follow the proof it may help to convert Table 2
into a transition graph with ten nodes and seventeen edges (one of
which has never been observed and one of which has only been seen
once).
Theorem. I. The situations shown in Table 2 are all that arise
when CM runs.
II. A block consisting of a single 1 is never found on
the left half of the tape.
Proof. The proof is, of course, by induction. Suppose that I and
II have held up to a certain point. We show that they remain true
for the next step in the execution of the (exponential) machine.
To prove Part I we need to examine each of the ten situations from
Table 2 and use the Opposite Departure Rule and the Same Departure
Rules to determine the new-symbol. From Table 2 we assume by
induction that all transitions between reduced situations are found
in the following list of 17:
(a R 0) --> (b R 1)
(a R 0) --> (c L 0)
(a R 0) --> (c L 1)
(a R 1) --> (b L 0)
(b L 0) --> (c L 1)
(b L 0) --> (d L 1)
(b L 0) --> (e R 1)
(b R 1) --> (a R 0)
(b R 1) --> (c R 0)
(c L 0) --> (d L 1) [never observed]
(c L 0) --> (b R 1)
(c R 0) --> (d L 0)
(c L 1) --> (a R 1)
(d L 0) --> (a R 0)
(d L 1) --> (d L 0)
(e R 1) --> (a R 0) [observed once]
(e R 1) --> (d L 0)
Two reduced situations, which simply illustrate the possible types
of reasoning, will be given in detail, followed by one more complex
case, and then we turn to the crucial point mentioned in Note B of
Table 2.
First we consider the reduced situation (d L 1). Exit is always to
the right so by the Opposite Departure Rule the new-symbol is 0,
and since the new state is d and the new bloc is entered from the
left, we always go from (d L 1) to (d L 0).
Now we consider (c R 0). Exit is to the right so by the Same
Departure Rule the new-symbol is the leftmost of the previous
transformed block. But the previous reduced situation was
necessarily (b R 1) and the leftmost symbol of its transformed
block is always 0, so, since the new-state is d, we go from (c R 0)
to (d L 0).
The last case we look at is (a R 0). When the exponent is 1 the
exit is to the left, so the Opposite Departure Rule implies that
the new symbol is 1, and we go to (b R 1). For exponent greater
than 1 the new state is c and exit is to the right, so the Same
Departure Rules say that the new-symbol is at the left of the
previous transformed bloc. By induction the previous situation was
one of (b R 1 n : n = 2j+3), (e R 1 2), or (d L 0 n). The left
symbol of the transformed bloc from these situations can be either
0 or 1, so from (a R 0) with exponent >1 we can go either to
(c L 0) or (c L 1).
The other seven reduced situations are covered by similar
arguments. So now we turn to the crucial point. Why does the
situation (b R 1 1), which would lead to an immediate halt, never
occur? The reason is simply that Part II of the induction
hypothesis rules out blocks of 1's of length 1 in the left half of
the tape, so we can never enter such a block from the right. The
same reasoning says that we never get to (e R 1 1) or (a R 1 1)
either.
Now to prove Part II. From Table 2 we see that a bloc of 1's of
length 1 could be put in the left half of the tape only from one of
the situations (a R 1 1) [which we have just seen does not occur],
(b L 0 1), or (b L 0 2). The latter two situations generate the
transformed blocs (1 1) and (1 1)(0 1). But the reduced situation
preceding (b L 0) is necessarily (a R 0), which has always just put
a block of 1's at the beginning of the left half of the tape. So
the isolated 1 generated by (b L 0 1) or (b L 0 2) is immediately
amalgamated into a larger block and no block of 1's of unit length
is ever created put on the left.
This completes the proof of the Theorem.
Corollary. The Chaos Machine never halts.
Table 1. The Chaos Machine.
______________________________________
Input | _______Transition_on_State__|
Bit | A | B | C | D | E |
_______|_____|_____|_____|_____|_____|
__0___|_B1L_|_C1R_|_D0R_|_A1L_|_H1L_|
1 | B1R | E0L | A0L | D0R | C0L |
_______|_____|_____|_____|_____|_____|
Table 2. Transition table for the Chaos Machine in exponential form. A bloc
of n symbols is represented as (1 n) and a block of n blanks as (0 n).
==========================================================================
old |entry|old |block ||new |exit|transformed |new |steps|notes
state|dir. |symbol|length||state|dir.|block |symbol| |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
a | R | 0 | 1 || b | L |(1 1) | 1 | 1 |
| | +------++-----+----+-----------------+------+-----+-----
| | | n>1 || c | R |(0 n-2)(1 2) | 0,1 | 5 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
a | R | 1 | n || b | R |(1 n) | 0 | 1 | A.
-----+-----+------+------++-----+----+-----------------+------+-----+-----
b | L | 0 | 1 || c | R |(1 1) | 1 | 1 |
| | +------++-----+----+-----------------+------+-----+-----
| | | 2 || d | R |(1 1)(0 1) | 1 | 2 |
| | +------++-----+----+-----------------+------+-----+-----
| | | n>2 || e | L |(0 1)(1 2)(0 n-3)| 1 | 5 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
b | R | 1 | 1 || e | L |(0 1) | 0 | 1 |A, B.
| | +------++-----+----+-----------------+------+-----+-----
| | | 2j+2 || c | L |(0 2)(1 2j) | 0 |8j+2 |
| | +------++-----+----+-----------------+------+-----+-----
| | | 2j+3 || a | L |(0 3)(1 2j) | 0 |8j+3 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
c | L | 0 | 1 || d | R |(0 1) | 1 | 1 | C.
| | +------++-----+----+-----------------+------+-----+-----
| | | n>1 || b | L |(1 2)(0 n-2) | 1 | 3 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
c | R | 0 | n || d | R |(0 n) | 0 | 1 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
c | L | 1 | n || a | L |(0 1)(1 n-1) | 1 | 1 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
d | L | 0 | n || a | L |(1 1)(0 n-1) | 0 | 1 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
d | L | 1 | n || d | R |(0 n) | 0 | n |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
e | R | 1 | 1 || c | L |(0 1) | 0 | 1 | A.
| | +------++-----+----+-----------------+------+-----+-----
| | | 2 || a | L |(0 2) | 0 | 2 | D.
| | +------++-----+----+-----------------+------+-----+-----
| | | n>2 || d | R |(1 n-1)(0 1) | 0 | 5 |
-----+-----+------+------++-----+----+-----------------+------+-----+-----
Notes:
A. The case n=1 can not occur, by Part II of the induction hypothesis.
B. If this case ever occurred, the machine would immediately halt.
C. Never observed, but included in Part I of the induction hypothesis
D. Observed only once, at step 15.
==========================================================================
While our theorem shows CM is of no interest for the pursuit of the
busiest 5-state beaver, it remains a fascinating machine. It would
be most interesting to know more precisely how it is "chaotic" and
to better understand the many regularities that can be observed.
Our favorite vantage point for looking at these regularities is to
sample the tape when the head is at the extreme right, looking at a
block of 0's. You will see then a very regular "spectrum" of
exponents which begins
3 1 5 3 7 1 9 3 3 1 13 3 15 1 17 11 3 1 21 3 7 1 25 3 3 1 29 3 31 1 33
representing a tape that starts
111011111000111111101111111110001110 ...
Powers of 2 play a crucial role in the many periodicities which can
be observed, and the blocs of 0's have a much simpler pattern than
the blocs of 1's.