<p>It's true, all current busy beaver candidates have a quadratic relationship between output size and steps. As Ross points out, this has to do with how they act. They move back and forth across much of the output every time they increase the output size by some constant. That means that to get to size N they must run for approximately 1 + 1 + 2 + 2 + 3 + 3 + ... = N(N+1) steps.</p>

<p>However, there are many other types of Turing machines. For example, there are ones often called counters which move back and forth across a section of output, each time incrementing a binary (or other base) counter. These take exponential time to increase the size of the output. One interesting one is Brady's "Surprise in a Box" <a href="http://www.drb.insel.de/~heiner/BB/simAB3Y_SB.html">http://www.drb.insel.de/~heiner/BB/simAB3Y_SB.html</a> which expands quadratically for a little while and then moves completely within the "box" until it halts.</p>

<p>There are also machines which have a sort of recursive "back and forth" behavior so that it takes them N^2 steps to increase the size of the tape. They have a cubic relationship between output size and steps.</p>

<p>I suspect that for larger values busy beavers will not have this relation because they will get more complex in their behavior, but I don't know of any proofs.</p>

CC BY-SA 2.5
2011-03-16T23:35:16.863Z
2011-03-16T23:35:16.863Z
sligocki
<p>When glancing at the running times and output sizes of some Busy Beaver candidates on <a href="http://www.drb.insel.de/~heiner/BB/" rel="nofollow">this page</a>, I find that there seems to be a rough (up to some small power of 10) quadratic relation between output size and running time. Do you know a heuristic argument or even proof for this? Is it related to the computational model of Turing machines, or is it some more general principle?</p>

<p>Because (under the assumption of a computational model where the binary description of the algorithm and the algorithms' length can be read out and operated on by the program) no program can decide the halting problem for all programs a little bit longer than itself and access to the busy beaver program of some length entails ability to solve the Halting problem for that length by checking whether a given program runs longer than the busy beaver, it can't be that this is somehow a test (for said programs with efficient access to memory) that will vastly constrain the possible candidates for all sizes, as then a smaller number of supplied bits would suffice to generate the busy beaver and thee would be a program could solve the halting problem for somewhat bigger programs. If you sharpen the notion of "vastly", this reasoning will also apply to Turing machines.</p>

CC BY-SA 2.5
2011-03-16T17:57:21.273Z
If, in the Busy Beaver Turing machines, the heads follow a random walk on the tape, there would be a quadratic relation between output size and running time. I don't know any argument that the computation of a Busy Beaver machine should appear random, though. Maybe it's only true for small Busy Beaver machines.
Peter Shor 
CC BY-SA 2.5
2011-03-16T20:51:32.277Z
This is my no means a proof and would even count as poor in terms of intuition but: a Turing machine which writes as many '1's as it can to the tape would write a '1' every transition it makes (constantly moving in one direction or another). However, such a machine cannot halt. Machines which write a lot to the tape but also halt must somehow scan over the input they have already written. If a machine scrolls back and forth over whichever symbols are already on the tape (involving its past computation so that it can halt) and writing new symbols intermittently on either side or...
Ross Snider
CC BY-SA 2.5
2011-03-16T20:52:21.420Z
(cont'd)... in the middle then by the scanning back and forth behavior there is a quadratic relationship between transitions and symbol writing. My guess is that proving something very concrete about all busy beaver TM's which suggests a quadratic relationship will be very hard.
Ross Snider
CC BY-SA 2.5
2011-03-17T00:15:04.833Z
In this paper you can find some bounds http://www2.mta.ac.il/~amirben/downloadable/beavers.ps.gz ... they are not so tight :-). I think the best "heuristic" in this case is "examine the champions" and see how they works. Heiner Marxen's page has a complete list of resources (http://www.drb.insel.de/~heiner/BB/)
Marzio De Biasi
<cc.complexity-theory><turing-machines>
Busy Beavers: quadratic relation of output size and running time?
Joris
# Busy Beavers: quadratic relation of output size and running time?

(Asked by: username_0 on 2011-03-16)

When glancing at the running times and output sizes of some Busy Beaver candidates on [this page](http://www.drb.insel.de/~heiner/BB/), I find that there seems to be a rough (up to some small power of 10) quadratic relation between output size and running time. Do you know a heuristic argument or even proof for this? Is it related to the computational model of Turing machines, or is it some more general principle?

Because (under the assumption of a computational model where the binary description of the algorithm and the algorithms' length can be read out and operated on by the program) no program can decide the halting problem for all programs a little bit longer than itself and access to the busy beaver program of some length entails ability to solve the Halting problem for that length by checking whether a given program runs longer than the busy beaver, it can't be that this is somehow a test (for said programs with efficient access to memory) that will vastly constrain the possible candidates for all sizes, as then a smaller number of supplied bits would suffice to generate the busy beaver and thee would be a program could solve the halting problem for somewhat bigger programs. If you sharpen the notion of "vastly", this reasoning will also apply to Turing machines.

**Tags:** cc.complexity-theory, turing-machines
> **Comments:**
> **username_1**: If, in the Busy Beaver Turing machines, the heads follow a random walk on the tape, there would be a quadratic relation between output size and running time. I don't know any argument that the computation of a Busy Beaver machine should appear random, though. Maybe it's only true for small Busy Beaver machines.  
> **username_2**: This is my no means a proof and would even count as poor in terms of intuition but: a Turing machine which writes as many '1's as it can to the tape would write a '1' every transition it makes (constantly moving in one direction or another). However, such a machine cannot halt. Machines which write a lot to the tape but also halt must somehow scan over the input they have already written. If a machine scrolls back and forth over whichever symbols are already on the tape (involving its past computation so that it can halt) and writing new symbols intermittently on either side or...  
> **username_2**: (cont'd)... in the middle then by the scanning back and forth behavior there is a quadratic relationship between transitions and symbol writing. My guess is that proving something very concrete about all busy beaver TM's which suggests a quadratic relationship will be very hard.  
> **username_3**: In this paper you can find some bounds http://www2.mta.ac.il/~amirben/downloadable/beavers.ps.gz ... they are not so tight :-). I think the best "heuristic" in this case is "examine the champions" and see how they works. Heiner Marxen's page has a complete list of resources (http://www.drb.insel.de/~heiner/BB/)  

---

## 1 answers

### Answer by username_4 on 2011-03-16. Score: 9 | Accepted answer

It's true, all current busy beaver candidates have a quadratic relationship between output size and steps. As Ross points out, this has to do with how they act. They move back and forth across much of the output every time they increase the output size by some constant. That means that to get to size N they must run for approximately 1 + 1 + 2 + 2 + 3 + 3 + ... = N(N+1) steps.

However, there are many other types of Turing machines. For example, there are ones often called counters which move back and forth across a section of output, each time incrementing a binary (or other base) counter. These take exponential time to increase the size of the output. One interesting one is Brady's "Surprise in a Box" <http://www.drb.insel.de/~heiner/BB/simAB3Y_SB.html> which expands quadratically for a little while and then moves completely within the "box" until it halts.

There are also machines which have a sort of recursive "back and forth" behavior so that it takes them N^2 steps to increase the size of the tape. They have a cubic relationship between output size and steps.

I suspect that for larger values busy beavers will not have this relation because they will get more complex in their behavior, but I don't know of any proofs.


---

