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.