Busy Beaver Simulations


Contents:
1.   Introduction
2.   Recent Changes
3.   Simulation Styles
4.   Simulation Table
5.   How these Simulations were created
6.   Change Log

1. Introduction

Here I present (partial) simulation results of some TMs. Such a simulation result contains a table of the transitions for the TM, and a listing of tape contents, one line for one configuration, for a few hundred initial steps. This can be of great help in getting a grasp of "what the TM does".

2. Recent Changes

3. Simulation Styles

Currently I offer the following versions of simulation:

  1. Plain: this is the simple naive way, and what you would expect a TM to do.
  2. With reduced repetitions: Long repetitions of the same state reading the same tape symbol and hence doing the same action can become boring. This version omits the intermediate tapes of such a repetition.
  3. With exponents: This is the equivalent 1-macro machine with the same tape symbols, and explicit tape symbol repetition counts, shown as exponents.
  4. As a real macro machine: This is an equivalent macro machine, with a hand selected macro cell size, and sometimes with a hand selected amount of the original tape behind the macro head pulled into the macro state. Like all macro machines it has explicit symbol repetition counts, shown as exponents.
  5. With "pure additive configuration transitions" (PA-CTRs): This machine basically operates like the macro machine above. But it remembers the configurations and recognizes when a complete configuration is repeated, except for some of the exponent values. Then it proves that step with non-negative symbolic variables in the exponents, remembers the complete "configuration transition", and later can apply it.
    The "pure additive" restricts the exponent changes to the addition of a constant value (positive or negative).
    Since the configuration does not change except for the variable exponents, the same PA-CTR can be applied again and again, until some exponent value becomes too small for the application.

With PA-CTRs the complete 5-state record list and part of the 6-state record list can be simulated and shown until the TM halts.

4. Simulation Table

An exclamation mark (!) is added to the link, where the simulation is complete (until the TM halts). An at-sign (@) is appended to the link, where the TM is shown to not halt (to loop).

Source Plain With repetitions reduced With exponents As macro machine With PA-CTRs
From the example list in our paper  #1  #2  #3  #4  #5  #6  #7  #8  #1  #2  #3  #4  #5  #6  #7  #8  #1  #2  #3  #4  #5  #6  #7  #8  #1  #2  #3  #4  #5  #6  #7  #8  #1!  #2!  #3@  #4  #5  #6  #7!  #8@
From our 5-state record list  #1  #2  #3  #4  #5  #6  #7  #1  #2  #3  #4  #5  #6  #7  #1  #2  #3  #4  #5  #6  #7  #1  #2  #3  #4  #5  #6  #7  #1!  #2!  #3!  #4!  #5!  #6!  #7!
From our old 6-state record list  #1  #2  #3  #1  #2  #3  #1  #2  #3  #1  #2  #3  #1!  #2!  #3!
New 4-tupel 6-state record machines from Machado/Pereira  #1!  #1!  #1!  #1!  #1!
New 4-tupel 7-state record machines from Machado/Pereira  #1!  #2!  #3!  #1!  #2!  #3!  #1!  #2!  #3!  #1!  #2!  #3!  #1!  #2!  #3!
From our new 6-state record list  #a  #b  #c  #d  #e  #g  #i  #j  #k  #l  #m  #n  #o  #p  #q  #r  #a  #b  #c  #d  #e  #g  #i  #j  #k  #l  #m  #n  #o  #p  #q  #r  #a  #b  #c  #d  #e  #g  #i  #j  #k  #l  #m  #n  #o  #p  #q  #r  #a  #b  #c  #d  #e  #g  #i  #j  #k  #l  #m  #n  #o  #p  #q  #r  #a!  #b!  #c!  #d!  #e!  #g!  #i!  #j!  #k!  #l  #m  #n  #o  #p  #q  #r
3-state 3-symbol machines from Allen Brady  #SB  #b  #c  #d  #SB  #b  #c  #d  #SB  #b  #c  #d  #SB!  #b  #c  #d  #SB!  #b!  #c!  #d!
3-state 3-symbol machines from Myron Souris (email)  #a  #b  #a  #b  #a  #b  #a  #b  #a!  #b!
3-state 3-symbol machines from G. Lafitte and C. Papazian (email)  #a  #b  #c  #d  #e  #a  #b  #c  #d  #e  #a  #b  #c  #d  #e  #a  #b  #c  #d  #e  #a!  #b!  #c!  #d!  #e!
2-state 5-symbol machines from G. Lafitte and C. Papazian (email)  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #a!  #b!  #c!  #d!  #e!  #f!  #g!  #h!  #i!  #j
BB: 2 states (2 symbols) (cited from P. Michel)  #bb22!  #bb22!  #bb22!  #bb22!  #bb22!
BB: 3 states (2 symbols) (cited from P. Michel)  #bb32O!  #bb32S!  #bb32O!  #bb32S!  #bb32O!  #bb32S!  #bb32O!  #bb32S!  #bb32O!  #bb32S!
BB: 4 states (2 symbols) (cited from P. Michel)  #bb42!  #bb42!  #bb42!  #bb42!  #bb42!
2 states and 3 symbols (cited from P. Michel)  #a!  #b!  #cb!  #a!  #b!  #cb!  #a!  #b!  #cb!  #a!  #b!  #cb!  #a!  #b!  #cb!
2 states and 4 symbols (cited from P. Michel)  #a  #b  #c  #a  #b  #c  #a  #b  #c  #a  #b  #c  #a!  #b!  #c!
2 states and 4 symbols from T.J. & S. Ligocki  #a  #a  #a  #a  #a!
2 states and 5 symbols from T.J. & S. Ligocki  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #k  #l  #m  #n  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #k  #l  #m  #n  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #k  #l  #m  #n  #a  #b  #c  #d  #e  #f  #g  #h  #i  #j  #k  #l  #m  #n  #a!  #b!  #c!  #d!  #e!  #f!  #g!  #h!  #i!  #j!  #k!  #l!  #m!  #n
2 states and 6 symbols from T.J. & S. Ligocki  #a  #b  #c  #d  #e  #f  #g  #a  #b  #c  #d  #e  #f  #g  #a  #b  #c  #d  #e  #f  #g  #a  #b  #c  #d  #e  #f  #g  #a!  #b!  #c!  #d!  #e  #f  #g
3 states and 3 symbols from T.J. & S. Ligocki  #a  #b  #a  #b  #a  #b  #a  #b  #a!  #b!
3 states and 4 symbols from T.J. & S. Ligocki  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b!  #c!  #d  #e  #f  #g  #h  #i
4 states and 3 symbols from T.J. & S. Ligocki  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a  #b  #c  #d  #e  #f  #g  #h  #i  #a!  #b  #c  #d  #e  #f  #g  #h  #i
6 states and 2 symbols from T.J. & S. Ligocki  #a  #b  #a  #b  #a  #b  #a  #b  #a  #b
6 states and 2 symbols from Pavel Kropitz (full numbers)  #a  #b  #a  #b  #a  #b  #a  #b  #a  #b
Unusual symbol sizes by Marxen & Buntrock  #u9  #u13  #u80  #u154  #u9  #u13  #u80  #u154  #u9  #u13  #u80  #u154  #u9  #u13  #u80  #u154  #u9@  #u13@  #u80@  #u154@(1MB)

diagram #r In Wikipedia I found an image of the state diagram for the #r from our new 6-state record list, the former 6-state 2-symbol champion (unseated 10-Nov-2007).

5. How these Simulations were created

All these simulations are, of course, not hand-crafted. They are generated from TM descriptions (transition table) by an "awk" program, which I wrote for this special purpose.

You may use these awk programs as you like. They are given as source in order to practically demonstrate a way to implement a good TM simulator, which is capable to simulate non-trivial machines with acceptable speed, even when the underlying language is interpreted (and therefore slow). Execution times for the above simulations range from less than a second to a few minutes on a modern PC (in 2004). Altogether they need less than 10 minutes on a modern PC (in Nov-2005).

In fact, I have used the second awk program (with PA-CTRs) to run all the above machines from the 6-state record lists until they halt. The running time for #q (the former champion) was the largest: several days, due to the then really naive and therefore slow bignum implementation. With the current (Dez-2004) tuned version I did run #r in 1 hour to its halt.

I have used these awk programs with GNU "gawk", IRIX "nawk", and Solaris "nawk" (although the latter has bugs I had to work around). These awk programs should work with any (new) awk that has functions. Of course, if you find any bugs in them, please let me know.

These awk programs are not a frozen release. I will continue to develop them.

6. Change Log


To the busy beaver page of Heiner Marxen.
To the home page of Heiner Marxen.
$Date: 2010/07/06 21:05:28 $