In my reading of the blog post it appears they used an interpreter for their Laconic language that took about 4000 states. It does seem that a bit of engineering should be able to reduce the state count a lot by eliminating the interpreter. Four thousand states for Goldbach does seem high. A variant of Hashlife can run most Turing machines at pretty phenomenal speeds; I once played with this as an attempt to find new BB records, but was unsuccessful at beating the incredible results that have been found. On Wed, May 4, 2016 at 8:18 AM, Allan Wechsler <acwacw@gmail.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] --