The Genetic Beaver Project
 
 
 
Hi!  The Genetic Beaver is an ongoing research project, developed at CISUC's AI Lab, by Penousal Machado & Francisco B. Pereira .  
The project's goal is finding Busy Beaver Turing machines (TM) trough the use of Genetic Algorithms. We are currently interested in the 4-Tuple variant.   
We have already found a 7-state TM which produces 100 ones in 5093 transitions. This is, as far as we know, the most productive 7-state (4-tuple) TM. 
Go to:  

  

Problem Definition: 

The problem was proposed by T. Rado in 1962. It consists in finding Turing Machines (TM) which produce a maximum number of ones on their tape before halting. These TMs have N states, one of which is the initial state, a tape alphabet with two symbols (0,1), an initial blank tape, an anonymous halt state.  
In each step the machine prints a new symbols and moves its head either left or right. Sigma is a function defined to be the maximum number of ones that a TM with N states produces on the tape when halting. An N state TM that does produce Sigma(N) ones is called a Busy Beaver. The number of transitions this machine makes before halting defines the function S(K).   

(Marxen, H. & Buntrock, J., 90), Attacking the Busy Beaver 5

5-Tuple TMs Variant:    

For a  5-Tuple Turing machines the program instructions can be defined as follows:  
[state] [symbol] -> [new state] [write] [move]  

[state]= {1,2,...,N}
[symbol] = {0,1}  
[new state]= {1,2,...,N} U {H}  
[write] = {0,1}  
[move] = {left,right}  

The machine starts on state 1, and halts when it reaches state H.

The usual definition for the BB problem is the one stated above.

4-Tuple TMs Variant:   

In a  4-Tuple Turing machine the program instructions have the following form: 
[state] [symbol] -> [new state] [action]  

[state]= {1,2,...,N} 
[symbol] = {0,1}  
[new state]= {1,2,...,N} U {H}  
[action] = [write | move]  
[write]={0,1}  
[move] = {left,right}  

i.e. The difference between 5-tuple and 4-tuple turing machines is that 5-tuple turing machines write and move in the same transition, while 4-tuple TMs either write or move.

The rules described in (Boolos & Jeffrey) Computability and Logic, are usually followed.  

  • The machine halts scanning the leftmost 1 on a string of 1's, with the rest of the tape blank.

Considering this, we do not need a transition for the halting state. The stop for lack of a transition constitutes an acceptable halt. The number of consecutive ones defines the sigma function.

  
 5-Tuple Top Candidates:   
 
n
Sigma(n)
S(n)
  Authors
*1
1
1
  Lin & Rado
*2
4
6
  Lin & Rado
*3
6
21
  Lin & Rado
*4
13
107
  Brady
5
4098
47,176,870
  Marxen & Buntrock
6
 95,524,079
 8,690,333,381,690,951
  Marxen
 
Machines marked with * are Busy Beavers, i.e. There is no machine that produces an higher number of ones. 
 
 

4-Tuple Top Candidates:  
 
n
Sigma(n)
s(n)
 Authors
5
11
 52
   ?
6
21
125
  Nielson, C.
7
102
4955
  Machado, P. & Pereira, F. (4/8/98)
8
384
43368
  Machado, P. & Pereira, F. (13/8/98)
 

The previous records were:  

  • bb(7) -> s(7)=37, by Lally, A., Reineke, J. & Weader, J.
  • bb(8) -> s(8)=86, by Norman, T., Chik, J. & Marcella, D.

We haven't really started our atack to BB(8), it seems that S(8) is significantly larger than 384.  

If you noticed some error in the tables or if you know a more productive TM pleas let us know!

  
Our Best Candidates: 
 

 

We will add our 8 state and our new 7 state (102 ones) cadidate asap, meanwhile you can see the machine at CLSI. 

 
Links to other pages about Busy Beavers:  

machado@dei.uc.pt