I was puzzled by one part of this post, and some of Scott's readers had a similar reaction. Namely, I was surprised that it took *so many* states for a Turing machine that halts should it find a Goldbach counterexample. In any decent high-level language this program is about three lines long. One commenter guessed that Goldbach should only take a few hundred states to characterize, and I felt even this was too high. But Scott's a smart guy, and he says he and Yedidia were unable to express the concept in fewer than 4,888 states. My intuition is still that this is way too high -- I wonder if we funsters can't improve on Yedidia and Aaronson? On Wed, May 4, 2016 at 2:34 AM, <rcs@xmission.com> wrote:
from Scott Aaronson's blog: The 8000th Busy Beaver number eludes ZF set theory: new paper by Adam Yedidia and Scott A.
http://www.scottaaronson.com/blog/?p=2725
Today, I’m proud to announce that Adam Yedidia, a PhD student at MIT
(but an MEng student when he did most of this work), has explicitly constructed a one-tape, two-symbol Turing machine with 7,918 states, whose behavior (when run on a blank tape) can never be proven from the usual axioms of set theory, under reasonable consistency hypotheses. Adam has also constructed a 4,888-state Turing machine that halts iff there’s a counterexample to Goldbach’s Conjecture, and a 5,372-state machine that halts iff there’s a counterexample to the Riemann hypothesis. In all three cases, this is the first time we’ve had an explicit upper bound on how many states you need in a Turing machine before you can see the behavior in question.
Includes a very short summary of work on BB(5) & BB(6), with a pointer to Marxen's page. Uses Lagarias's equivalence for Riemann.
Rich
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun