Questions: Busy Beaver Function and Non-Computability

Question 1

A programmer claims to have written a program that computes BB(n) for all n — it just takes an extremely long time for large values. Why is this claim impossible?

• A. Because BB(n) grows faster than any computer's available memory, making the computation physically impossible
• B. Because a program that computed BB(n) for all n could be used to solve the halting problem, which is undecidable
• C. Because BB(n) is not uniquely defined — different Turing machine conventions give different answers
• D. Because programs can only solve problems in polynomial time, and computing BB requires exponential time

Answer: (B)

If such a program C existed, you could decide the halting problem: given any n-state machine M, compute BB(n) via C, then simulate M for BB(n) steps. If M has not halted after BB(n) steps, by definition of BB(n) it never will. This would decide halting for all n-state machines — impossible. The obstacle is not runtime or memory: it is logical impossibility via reduction. Time and memory constraints are engineering limits; undecidability is a fundamental limit.

Question 2

Which statement correctly characterizes BB(n) relative to all computable functions?

• A. BB(n) is eventually dominated by fast-growing computable functions like the Ackermann function or 2^(2^n)
• B. For any computable function f, BB(n) eventually exceeds f(n) — BB grows faster than every computable function
• C. BB(n) and computable functions cannot be compared, since BB is not a well-defined mathematical function
• D. BB(n) grows at the same asymptotic rate as the Ackermann function, which represents the maximum computable growth

Answer: (B)

BB dominates every computable function. If any computable f eventually exceeded BB(n), you could use f(n) as an upper bound on halting-time and decide the halting problem — impossible. Therefore no computable function can dominate BB. The Ackermann function is total and computable; BB eventually surpasses it. This hierarchy result means BB is not just 'hard to compute' — it is fundamentally beyond the reach of all algorithms, no matter how powerful.

Question 3

The busy beaver function BB(n) is non-computable because it is not uniquely defined — different formulations of Turing machines or counting conventions yield different values for each n.

• T. True
• F. False

Answer: False

BB(n) is completely well-defined: it is the maximum number of steps taken by any halting n-state, 2-symbol Turing machine starting on a blank tape. BB(1)=1, BB(2)=6, BB(3)=21, BB(4)=107 are specific integers established by exhaustive analysis. The non-computability is entirely unrelated to definitional ambiguity — it arises because computing BB for all n requires solving the halting problem. A function can be perfectly well-defined and still be non-computable.

Question 4

If you could compute BB(n) for all n, you could also solve the halting problem for all Turing machines.

• T. True
• F. False

Answer: True

This equivalence is the direct proof of BB's non-computability. Given BB(n) and any n-state machine M, simulate M for BB(n) steps. If M has not halted, it never will — by definition of BB(n) as the maximum halting time among all n-state machines. This reduction shows that BB-computability implies halting-problem decidability. Since halting is undecidable, BB must be uncomputable. The two problems are equivalent in computational power.

Question 5

Explain why BB(n) being 'a perfectly well-defined integer sequence' does not prevent it from being non-computable. What does non-computability actually mean here?

Model answer: Non-computability means no Turing machine (no algorithm) can produce BB(n) as output for every input n — not that individual values lack definite answers. For any specific n, BB(n) is a unique finite integer; researchers have bounded BB(5) and BB(6) through exhaustive case analysis. But computing BB in general requires deciding, for each n-state machine, whether it halts — equivalent to the halting problem. Non-computability is a property of the input-output mapping (can any uniform procedure generate all outputs?), not of individual output values. Well-definedness and computability are independent properties.

This distinction is the conceptual core of the busy beaver. It shatters the intuition that 'well-defined means computable.' Many students conflate the two: if we can in principle determine BB(5) by checking all 5-state machines, surely we can compute BB(n) for all n? The answer is no — checking finite cases is not the same as possessing a uniform algorithm, and the halting problem guarantees no such algorithm exists.