{"id": "card_cs_busy_beaver", "kind": "reference", "title": "The Busy Beaver function — BB(5) proved, BB(6) open", "body": "BB(n), the Busy Beaver function (Rado 1962), is the most steps an n-state 2-symbol Turing machine can run before halting. It is UNCOMPUTABLE in general - a value of BB would decide the halting problem (undecidable, Turing 1936). In 2024 the bbchallenge Collaboration PROVED BB(5) = 47,176,870 in the Coq proof assistant (Coq-BB5; arXiv:2509.12337), ending a 60-year problem: every decider (Loops, n-gram Closed Position Set, Finite Automata Reduction, Weighted FAR, Closed Tape Language) is itself proved correct in Coq, and each machine carries a machine-checkable certificate. This is CITED, not recomputed here; the engine seals only the search-space count (21^10 candidate 5-state machines). BB(6) stays OPEN (astronomically large) - the open frontier of computability. Ties the halting problem and card_floor_p_vs_np.", "source": {"label": "Narrow Highway — computer science", "url": "", "authority_tier": "engine_derived", "ref": "stick_computer_science_bits_logic_and_what_can_be_computed"}, "shelf": "codex", "box": "computer_science", "bands": ["busy beaver", "busy beaver function", "BB(5)", "BB(6)", "Rado", "Turing machine", "halting problem", "undecidable", "uncomputable", "Coq-BB5", "bbchallenge", "computability", "computer science", "one map"], "subject": "The Busy Beaver function — BB(5) proved, BB(6) open", "connections": [{"to_card_id": "card_floor_computer_science", "relationship": "part_of", "evidence": "the Busy Beaver function - the concrete uncomputable frontier of computability"}, {"to_card_id": "card_cs_computability", "relationship": "connects_at", "evidence": "BB(n) is uncomputable - the halting problem made a concrete function; BB(5) proved in Coq, BB(6) open"}], "author": "engine", "created_at": 0.0, "updated_at": 0.0, "visibility": "public", "lifecycle_stage": "public", "volatility": "permanent", "surface": "secular", "generated": false, "call": "codex.computer.science", "facets": {"subject": ["BB(5)", "BB(6)", "Coq-BB5", "Rado", "Turing machine", "bbchallenge", "busy beaver", "busy beaver function", "computability", "computer science", "halting problem", "one map", "uncomputable", "undecidable"]}, "presentation": {"glyph": "•", "kind_label": "computer science", "by": "Narrow Highway — computer science", "authority": "engine_derived", "posted": "", "standing": ""}, "neighbors": [{"id": "card_floor_computer_science", "title": "Computer science — bits, logic, and what can be computed", "relationship": "part of", "why": "the Busy Beaver function - the concrete uncomputable frontier of computability", "href": "/card/card_floor_computer_science", "resolved": true}, {"id": "card_cs_computability", "title": "Computability and complexity — Turing to P vs NP", "relationship": "connects at", "why": "BB(n) is uncomputable - the halting problem made a concrete function; BB(5) proved in Coq, BB(6) open", "href": "/card/card_cs_computability", "resolved": true}], "house": {"door": "FIND", "kind": "card", "trail": "connections", "seal": "/card/card_cs_busy_beaver", "next_step": {"do": "follow a connection: what this card rests on, and what rests on it", "door": "FIND", "tool": "card_connections", "params": {"id": "card_cs_busy_beaver"}}, "ends": "a verdict or a card · the trail · a seal · one next step"}}