# Busy Beavers: quadratic relation of output size and running time?

When glancing at the running times and output sizes of some Busy Beaver candidates on this page, 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.

• 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 Mar 16 '11 at 17:57
• 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 Mar 16 '11 at 20:51
• (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 Mar 16 '11 at 20:52
• In this paper you can find some bounds 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 (drb.insel.de/~heiner/BB) – Marzio De Biasi Mar 17 '11 at 0:15