[math-fun] BusyBeaver(8000) is undecidable.
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, Im 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 theres a counterexample to Goldbachs Conjecture, and a 5,372-state machine that halts iff theres a counterexample to the Riemann hypothesis. In all three cases, this is the first time weve 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
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
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] --
In the comment thread of that blog post, Aaronson express skepticism that anybody could easily beat 4,888. I feel challenged. Here's my proposed tape layout. There's a pair of interleaved unary counters on the right, which are used for the current candidate sum; in general both are odd. On the left is a single unary counter holding the current candidate divisor, used in the prime checker. X = 5; Y = 0; bigloop: Y++; // From this point on, X and Y are usually odd. littleloop: X--; Y++; if (X==0) HALT; // Check for halting, halfway through a double-increment-decrement. X--; Y++; if (!Prime(X) || !Prime(Y)) go littleloop; restack: X++; Y--; if (Y>0) go restack; X++; go bigloop; About a dozen states to set up. At most five for incrementing and decrementing X and Y, each time, so that's about 40 more. The two ifs are one or two states each. So if there is something hard here, it is in the prime checker (which we either have to write twice, or store a little more state on the tape). Does a prime checker really need 4.800 states? I think not. On Wed, May 4, 2016 at 4:51 PM, Tom Rokicki <rokicki@gmail.com> wrote:
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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I revisited the comment thread on Aaronson's post last night. Recall that Aaronson expressed some pride that they had captured the Goldbach conjecture with a binary Turing machine that would halt if GC was false, in only 4,888 states. I immediately had the intuition that this was at least an order of magnitude too high. My intuition was right, and Yedidian's and Aaronson's wrong. In comment #108, commenter Jared S. announces that he has a 73-state solution; rather than announce it directly, he escrowed it somewhere and gave a SHA hash of the document for later authentication, in order to start a game of "code golf". At comment #151, "code golf addict" takes up the challenge, and announces a a 31-state solution (again providing a SHA-256 hash). At comment #195, "code golf addict" says that he's gotten it down to 27 states, and gives a link to his code at https://gist.github.com/anonymous/a64213f391339236c2fe31f8749a0df6 . I haven't really looked at either of "code golf addict"'s machines yet. But 27 states is in line with my intuition; I don't harbor any convictions that it can be compressed to 10 states. On Wed, May 4, 2016 at 5:42 PM, Allan Wechsler <acwacw@gmail.com> wrote:
In the comment thread of that blog post, Aaronson express skepticism that anybody could easily beat 4,888. I feel challenged.
Here's my proposed tape layout. There's a pair of interleaved unary counters on the right, which are used for the current candidate sum; in general both are odd. On the left is a single unary counter holding the current candidate divisor, used in the prime checker.
X = 5; Y = 0; bigloop: Y++; // From this point on, X and Y are usually odd. littleloop: X--; Y++; if (X==0) HALT; // Check for halting, halfway through a double-increment-decrement. X--; Y++; if (!Prime(X) || !Prime(Y)) go littleloop; restack: X++; Y--; if (Y>0) go restack; X++; go bigloop;
About a dozen states to set up. At most five for incrementing and decrementing X and Y, each time, so that's about 40 more. The two ifs are one or two states each. So if there is something hard here, it is in the prime checker (which we either have to write twice, or store a little more state on the tape). Does a prime checker really need 4.800 states? I think not.
On Wed, May 4, 2016 at 4:51 PM, Tom Rokicki <rokicki@gmail.com> wrote:
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] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (3)
-
Allan Wechsler -
rcs＠xmission.com -
Tom Rokicki