A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory

DOI10.25088/COMPLEXSYSTEMS.25.4.297zbMATH Open1445.03046arXiv1605.04343MaRDI QIDQ5126830FDOQ5126830

Adam B. Yedidia, Scott Aaronson

Publication date: 20 October 2020

Published in: Complex Systems (Search for Journal in Brave)

Abstract: Since the definition of the Busy Beaver function by Rado in 1962, an interesting open question has been the smallest value of n for which BB(n) is independent of ZFC set theory. Is this n approximately 10, or closer to 1,000,000, or is it even larger? In this paper, we show that it is at most 7,910 by presenting an explicit description of a 7,910-state Turing machine Z with 1 tape and a 2-symbol alphabet that cannot be proved to run forever in ZFC (even though it presumably does), assuming ZFC is consistent. The machine is based on the work of Harvey Friedman on independent statements involving order-invariant graphs. In doing so, we give the first known upper bound on the highest provable Busy Beaver number in ZFC. To create Z, we develop and use a higher-level language, Laconic, which is much more convenient than direct state manipulation. We also use Laconic to design two Turing machines, G and R, that halt if and only if there are counterexamples to Goldbach's Conjecture and the Riemann Hypothesis, respectively.

Full work available at URL: https://arxiv.org/abs/1605.04343

Mathematics Subject Classification ID

Consistency and independence results (03E35) Turing machines and related notions (03D10) Classical models of computation (Turing machines, etc.) (68Q04)

Cited In (8)

• Average-Case Completeness in Tag Systems
• Undecidability of the Spectral Gap
• Embedding of provably unsolvable problems into stream ciphers;Встраивание доказуемо неразрешимых задач в шифры гаммирования
• The Riemann hypothesis as the parity of special binomial coefficients
• Undecidable problems in quantum field theory
• Improved bounds for functions related to busy beavers
• The Riemann hypothesis in computer science
• On some algebraic ways to calculate zeros of the Riemann zeta function

   Recommendations

• Small deterministic Turing machines 👍 👎
• Some small self-describing Turing machines 👍 👎
• Small universal Turing machines 👍 👎
• Small Weakly Universal Turing Machines 👍 👎
• Small Semi-Weakly Universal Turing Machines 👍 👎
• Small Semi-weakly Universal Turing Machines 👍 👎
• A small minimal aperiodic reversible Turing machine 👍 👎
• MINSKY'S SMALL UNIVERSAL TURING MACHINE 👍 👎
• Turing machines with few accepting computations and low sets for PP 👍 👎
• The Complexity of Small Universal Turing Machines 👍 👎

This page was built for publication: A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5126830)