The winners of the busy beaver contest are: 1. Ekaterina Lenchikov 274,877,907,373 2. Patrick Kwok 178,956,962 3. Mahmoud Alsaeed 31,498,014 4. Ziyin Zhong 15,932,364 5. Ashkan Moatamed 7,920,128 6. Professor Jeff Edmonds 3,983,884 7. Muhammad Khalid 3,981,188 8. Yash Kapadia 3,802,502 9. Samuel Lim 48,408 10. Jaskaran Garha 47,616 Grades were awarded as follows: 4 points for more than 1 million steps 3 points for 1000 to 999999 steps 2 points for 100 to 999 steps 1 point for 1 to 99 steps 0 points if the submission had too many errors, too many states or ran forever ----------------------------------------- Jeff Edmonds (who came in 6th, but only used 5 states instead of 6, and didn't even use the X character) gave me permission to post his solution. Here it is: Oops I misread the question when I went away to think about it, so I am going to only use 4 states. (Really only 3 states, because the accepting state is of no use.) My time will be 3,983,883. If you can give me 2 more states, i.e., a total of 6 then I can increase the time by another 2^(1984+12) *(1984+12). My idea is think of the contents of the tape in binary and to count down and to extend the length of the used tape by one each decrement. However, we flip the role of zeros and ones. And we flip the order of the bits from left to right. Our initial tape is to contain #11111100000. (Here # indicates the start of the tape) Changing zeros to ones and ones to zeros and flipping the order of the bits from left to right gives 11111000000#, which is 1984 in binary. Each meta step will decrement this number by one and add a leading zero. The loop invariant is that after the i^th meta step, the number in binary will be 1984-i with i leading zeros. For example, i=0: _________11111000000# = 1984 with 0 leading zeroes i=1: ________011110111111# = 1983 with 1 leading zeroes i=2: _______0011110111110# = 1982 with 2 leading zeroes i=3: ______00011110111101# = 1981 with 3 leading zeroes i=4: _____000011110111100# = 1980 with 4 leading zeroes i=5: ____0000011110111011# = 1979 with 5 leading zeroes Changing ones back to zeros and zeros back to ones and flipping the order of the bits back again from right to left then gives the actual tape content to be i=0: #11111100000_________ i=1: #000000100001________ i=2: #1000001000011_______ i=3: #10000010000111______ i=4: #110000100001111_____ i=5: #0010001000011111____ Let n = 1984 be our initial value. Let m = 11 be the initial number of bits. The i^th meta step (going from i-1 to i) will change the integer from n-i+1 to n-i and change the number of bits from m+i-1 to m+i. To do this, the algorithm must move the from left to the right and back to the left. This takes 2(m+i) time. The last pass of the TM will just go once till it finds the blank. Hence, the total time is [sum_{i = 1..n} 2(m+i)] + m+n = 2mn + [sum_{i = 1..n} 2i] + m+n = 2mn + n(n+1) + m+n = 2(11)(1984) + (1984)(1985) + 11 + 1984 = 3,983,883 To make it easier to understand, I am first going to write the code with zeros and ones switched and left and right flipped. Suppose the current state is i=4: _____000011110111100# = 1980 with 4 leading zeroes with the head on the right most bit, i.e., the low order bit (here a 0) in state s0 and we must change it to i=5: ____0000011110111011# = 1979 with 5 leading zeroes with the head on the right most bit, i.e., the low order bit (here a 1) in state s0 The algorithm must find the rightmost 1. Change it to zero. And change all earlier zeros to ones. Doing this from right to left, we first change the rightmost zeros. Code: delta(s0,0) = change to 1, go left, & stay in state s0 delta(s0,1) = change to 0, go left, & change to state s1 The algorithm then moves the head all the way to the left to the first blank and changes it to a 0. Code: delta(s1,0) = go left & stay in s1 delta(s1,1) = go left & stay in s1 delta(s1,blank) = change to 0, go right, & change to state s2 The algorithm then moves the head back all the way from left to right. delta(s2,0) = go right & stay in s2 delta(s2,1) = go right & stay in s2 delta(s2,#) = go left & change to state s0 This reestablishes the loop invariant. The code terminates when the integer on the tape is zero, i.e., is all zeros. The following code will then move the head all the way to the left until it gets a blank. delta(s0,0) = change to 1, go left & stay in state s0 Hence the exit condition is delta(s0,blank) = change to the halting state. Changing ones back to zeros and zeros back to ones and flipping the order of the bits back again from right to left then gives Code: Our initial tape is to contain #11111100000 with the head on the left most 1. delta(s0,1) = change to 0, go right, & stay in state s0 delta(s0,0) = change to 1, go right, & change to state s1 delta(s1,1) = go right & stay in s1 delta(s1,0) = go right & stay in s1 delta(s1,blank) = change to 1, go left, & change to state s2 delta(s2,1) = go left & stay in s2 delta(s2,0) = go left & stay in s2 delta(s2,#) = go right & change to state s0 delta(s0,blank) = change to the halting state. If you can give me 2 more states, then I can increase the time by another 2^(1984+12) *(1984+12) At the end of this algorithm the integer will be zero with m bits with n extra leading zeros for a total of m+n zeros. But really on the tape is m+n ones. As an integer, this is 2^(m+n)-1. Use the two extra states to decrement this number to zero.