BB(3, 4) > Ack(14)

Original Article ↗ Hacker News Discussion ↗

Understanding the specific Busy Beaver machine

  • Several comments unpack the state table notation: rows are states (A, B, C, Z as halt), columns are tape symbols (0–3), and each entry encodes “write symbol; move Left/Right; go to next state.”
  • Initial configuration: state A, infinite tape of zeros. Halting happens when a transition goes to state Z, regardless of what it writes or where it moves.
  • Multiple code sketches (C, Rust, Python) show how to simulate the machine, emphasizing that states are like goto targets and symbols are runtime data.

Code structure and “spaghetti” vs structured style

  • One question asks if the goto-heavy C version can be made more “structured.”
  • Examples show conversions to nested loops and booleans (Rust) and to computed gotos (GNU C), trading clarity vs control-flow directness.
  • Some find the structured versions clever but also “horrifying,” illustrating the tension between theoretical faithfulness and conventional software style.
  • A higher-level remark notes this champion is relatively structured: A and C only hand control back to B, there are no “do-nothing” transitions, and it never writes blanks.

Information content and encoding

  • A rough count treats the 3-state, 4-symbol machine as containing about 60 bits of information; earlier miscalculation is corrected.
  • Commenters note this overcounts: symmetries (mirroring tape, relabeling states/symbols), enforcing exactly one halting transition, and normal forms like Brady’s algorithm reduce effective description length to under ~40 bits.
  • Parallel discussion: lambda-calculus Busy Beaver variants (BBλ) achieve vastly larger values in even fewer bits and can be argued to be information-theoretically “optimal.”

Behavior, halting, and big numbers

  • Some implement and observe the machine: informally, it builds and transforms long runs of symbols in a way that grows extremely fast (roughly via nested exponentiation-like behavior).
  • The difficult part is not seeing rapid growth, but understanding why it eventually halts; the article’s inductive proof is referenced as necessary.
  • The produced number of symbols can be expressed with Knuth up-arrow notation requiring many arrows, yet is still far below Graham’s number; other constructions (BBλ) exceed even that.

Meta: publication venues, Discord, and peer review

  • Significant debate centers on citing Discord logs for important results:
    • Pro: real collaboration happens there; links serve as attribution; traditional journals and peer review are criticized as slow, biased, and partly responsible for replication issues.
    • Con: Discord is proprietary, ephemeral, and hard to archive; important arguments should be preserved in durable forms (papers, PDFs, blogs).
  • Broader tensions appear around what counts as “foundational,” the role of journals, tenure and grant incentives, and how scientific credit and reliability should be managed in the internet era.