A relatively small turing machine whose behavior is independent of set theory

[摘要] Since the definition of the Busy Beaver function by Radó in 1962, an interesting open question has been what the smallest value of n for which BB(n) is independent of ZFC. Is this n approximately 10, or closer to 1,000,000, or is it unfathomably large? In this thesis, I show that it is at most 340,943 by presenting an explicit description of a 340,943-state Turing machine Z with 1 tape and a 2-symbol alphabet whose behavior cannot be proved in ZFC, assuming ZFC is consistent. The machine is based on work of Harvey Friedman on independent statements involving order-invariant graphs. Ill In doing so, I give the first known upper bound on the highest provable Busy Beaver number in ZFC. I also present an explicit description of a 7,902-state Turing machine G that halts if and only if there;;s a counterexample to Goldbach;;s conjecture, and an explicit description of a 36,146-state Turing machine R that halts if and only if the Riemann hypothesis is false. In the process of creating G, R, and Z, I define a higher-level language, TMD, which is much more convenient than direct state manipulation, and explain in great detail the process of compiling this language down to a Turing machine description. TMD is a well-documented language that is optimized for parsimony over efficiency. This makes TMD a uniquely useful tool for creating small Turing machines that encode mathematical statements.

[发布机构] Massachusetts Institute of Technology