7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 6
    $\begingroup$ 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. $\endgroup$ – Peter Shor Mar 16 '11 at 17:57
  • 2
    $\begingroup$ 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... $\endgroup$ – Ross Snider Mar 16 '11 at 20:51
  • $\begingroup$ (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. $\endgroup$ – Ross Snider Mar 16 '11 at 20:52
  • 1
    $\begingroup$ 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) $\endgroup$ – Marzio De Biasi Mar 17 '11 at 0:15
9
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.