Researchers Formalize Behavior for 11 Turing Machines
The findings define the logic of elusive six-state machines as part of an ongoing effort to solve the Busy Beaver problem.
Updated on Oct. 22, 2026 in Mathematics
Live Poll
Do you trust that artificial intelligence will help solve complex scientific problems more effectively than humans?
Researchers from Google DeepMind and the University of Cambridge have formalized the behavior rules for 11 six-state Turing machines, known as BB(6) machines. The team used the Gemini 3.1 Pro AI system to develop proofs, which were subsequently verified using the Lean 4 theorem prover.
Why it matters
This research narrows the search space for the Busy Beaver problem, a foundational challenge in computational complexity that seeks to determine the maximum number of steps a halting Turing machine can take. By formalizing these complex behaviors, the team advances efforts to map the boundaries of computable functions.
The researchers identified 11 'Cryptid' machines after analyzing 52 candidates generated from a search of 1,094 BB(6) holdouts, 65 BB(2,5) machines, and four BB(3,3) machines. Behavior proofs for the 11 machines were verified using the Lean 4 theorem prover.
The players
Google DeepMind
A leading AI research laboratory focused on deep learning and its applications in scientific discovery.
University of Cambridge
A historic research institution contributing to the development of theoretical computer science.
The details
The team utilized Gemini 3.1 Pro to perform simulations and detect patterns, generating conjectures about how these machines operate on a blank tape. These conjectures were translated into formal proofs and rigorously checked by Lean 4, an open-source software tool designed for mathematical verification. This process effectively documents the state-to-state logic of the machines, even while their ultimate halting status remains a subject of ongoing inquiry.
Timeline
October 22, 2026: The research results were published.
The Tech Race
This work follows the long-standing attempt to solve the Busy Beaver problem, a foundational challenge first introduced in the 1960s to identify the limits of algorithmic complexity. By utilizing AI to formalize these behaviors, the study represents a shift in how researchers approach difficult problems in computability theory.
These findings currently serve as a theoretical advancement for computer scientists and mathematicians studying algorithmic limits. No practical applications for consumer software are available, as the research is focused on the fundamental properties of computation.
The takeaway
This research establishes a new classification of machines, dubbed Cryptids, to help organize the most elusive cases in Turing machine theory. Observers should track whether the Busy Beaver community formally adopts the Cryptid label and succeeds in resolving the halting status of these 11 machines.
Further reading
For more on the search for computational limits, visit Mathematics.
Source note: This article includes information reported by TokenPost.
Live Poll
Do you trust that artificial intelligence will help solve complex scientific problems more effectively than humans?
