HackerPapers

arXiv:1605.04343cs.FL

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

Adam Yedidia, Scott Aaronson

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.

arXiv comments
31 pages, 6 figures, with the last 10 pages devoted to bibliography and appendices. Submitted to Complex Systems
Journal reference
DOI
Subjects
cs.FLFormal Languages and Automata Theory cs.LOLogic in Computer Science

On Hacker News

Linked by 4 identifiable commenters in 4 comments across 3 threads, from Jul 2023 to Jun 2025.

Comments linking this paper, per year.

Discussed in comments3 threads

  1. BusyBeaver(6) Is Quite Large 1 comment
  2. What does “Undecidable” mean, anyway 2 comments

    • > Are these two meanings of "undecidable" related I can't claim to answer this, but you might like to look at A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory[0] which (amongst other interesting things) does discuss the proposition "ZFC is…

      ttctciyfView on HNParent context

    • I don't think this is an important distinction. The point of Turing machines is that you can ask questions like "can all instances of this problem be solved uniformly, and how relatively expensive is it?". This requires infinite memory in a formal sense, because instances of…

      bubblyworldView on HNParent context

  3. The Undecidability of BB(748): Understanding Godel’s Incompleteness Theorems [pdf] 1 comment

    • There's a lot of introduction here, but it starts getting to the point in section 3.4 "The previous paper". That paper is "A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory" https://arxiv.org/abs/1605.04343 (and an improvement in the blog comments on…

      sp332View on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.