按年被提到
20162025 · 2 次2026
数学、逻辑与理论›数学猜想与重大证明·arXiv:1605.04343 · cs.FL

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

Adam Yedidia, Scott Aaronson · 2016
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2023-07-10 · 最近 2025-05-29
3不同的人
2活跃月份
2讨论串
32被引(OpenAlex)
arXiv 摘要(候选层不写导读)

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.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论sp332 · 2023-07

“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 https://scottaaronson.blog/?p=2725) I recommend starting there just to know wh…”

The Undecidability of BB(748): Understanding Godel’s Incompleteness Theorems [pdf]原评论 ↗
评论ttctciyf · 2025-05

“> 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 consistent", which is independent from ZFC, in terms of a Turing Machine which enumerat…”

What does “Undecidable” mean, anyway原评论 ↗
评论bubblyworld · 2025-05

“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 (most) problems can be arbitrarily large. Yes, if you ask the same question with…”

What does “Undecidable” mean, anyway原评论 ↗