DeepMind's Gemini agent discovers and Lean-verifies new acceleration rules for 11 BB(6) Turing machines
omarsar0 · x · 2026-10-20
Google DeepMind's paper At the Limits of Computability introduces an autonomous, Gemini-based agentic pipeline for open-ended math discovery on the Busy Beaver frontier.
- The agent autonomously discovered and formally verified (in Lean) novel Collatz-like acceleration rules for eleven unresolved machines in BB(6).
- Pipeline: pick machines, spot patterns in execution traces, propose compact rules summarizing many steps, then run informal reasoning plus Lean proofs—only proved rules are kept, so results don't rely on trusting the model.
- Busy Beaver is uncomputable, so there is no fixed problem list; the agent must uncover and formulate new questions itself, unlike prior AI math work on human-defined problems.
- The machines are provisionally dubbed Cryptids: exact compact descriptions of their blank-tape runs exist, but halting remains open.
- Authors frame this as a demonstration of AI's potential for autonomous, open-ended mathematical discovery in fundamental CS.
More from AGI Musings
- Garrison Lovely's 'Obsolete' hailed as the best primer on the AI replacement race — zetalyrae · 2026-10-20
- For agents SaaS is just code — exec argues vertical SaaS moats are collapsing — matt_slotnick · 2026-10-20
- Anthropic and Musk equity-for-children moves are strategic investments, not charity — krishnan · 2026-10-20
- "It's still OK to enjoy programming": dev pushes back on AI-era coding doom — facontidavide · 2026-10-20
- 26,811-pupil study: AI lifts homework scores in China but hurts exam performance — Dr_Alex_Crimi · 2026-10-20
- Philosopher Negarestani answers 'The Superdark Factory': operational agency is outpacing rational integration — tylerjdunn · 2026-10-20