Re: [math-fun] BusyBeaver(8000) is undecidable.
And RH? -----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable. 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it? On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov> wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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
_______________________________________________ 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
The Riemann Hypothesis is equivalent to the assertion that for all positive integers n, the following inequality holds: [DMR 1974] [H(delta(n)) - n^2/2]^2 < 36 n^3 where: H(k) = 1 + 1/2 + 1/3 + ... + 1/k delta(n) = eta(1)^(n-1) * eta(2)^(n-2) * ... * eta(n-2)^2 * eta(n-1) eta(q) = gcd{a > 1 : a | q} Clearly, this can be expressed as a calculation involving only integers. Best wishes, Adam P. Goucher
Sent: Monday, May 09, 2016 at 6:02 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] BusyBeaver(8000) is undecidable.
I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it?
On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov> wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Jeff Lagarias was the one who figured this out. Jim On Monday, May 9, 2016, Adam P. Goucher <apgoucher@gmx.com> wrote:
The Riemann Hypothesis is equivalent to the assertion that for all positive integers n, the following inequality holds: [DMR 1974]
[H(delta(n)) - n^2/2]^2 < 36 n^3
where:
H(k) = 1 + 1/2 + 1/3 + ... + 1/k
delta(n) = eta(1)^(n-1) * eta(2)^(n-2) * ... * eta(n-2)^2 * eta(n-1)
eta(q) = gcd{a > 1 : a | q}
Clearly, this can be expressed as a calculation involving only integers.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 6:02 PM From: "Allan Wechsler" <acwacw@gmail.com <javascript:;>> To: math-fun <math-fun@mailman.xmission.com <javascript:;>> Subject: Re: [math-fun] BusyBeaver(8000) is undecidable.
I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it?
On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov <javascript:;>> wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com <javascript:;>] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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 <javascript:;>> 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 <javascript:;>> 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 <javascript:;>> 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 <javascript:;>> 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 <javascript:;> > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun > _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> 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 <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com <javascript:;> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Adam, Sequence A057641 is another version of expressing the RH as the positivity of a sequence of integers. (Also based on the work of Robin and Lagarias) But the version you mention may be missing. Could you create the corresponding sequence? That is a(n) = 36 n^3 - [H(delta(n)) - n^2/2]^2 with a comment that this is pos iff the RH holds? Thanks! Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Mon, May 9, 2016 at 4:04 PM, Adam P. Goucher <apgoucher@gmx.com> wrote:
The Riemann Hypothesis is equivalent to the assertion that for all positive integers n, the following inequality holds: [DMR 1974]
[H(delta(n)) - n^2/2]^2 < 36 n^3
where:
H(k) = 1 + 1/2 + 1/3 + ... + 1/k
delta(n) = eta(1)^(n-1) * eta(2)^(n-2) * ... * eta(n-2)^2 * eta(n-1)
eta(q) = gcd{a > 1 : a | q}
Clearly, this can be expressed as a calculation involving only integers.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 6:02 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] BusyBeaver(8000) is undecidable.
I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it?
On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov
wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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
_______________________________________________ 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
_______________________________________________ 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
LCM? -----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Adam P. Goucher Sent: Monday, May 09, 2016 2:04 PM To: math-fun@mailman.xmission.com Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable. The Riemann Hypothesis is equivalent to the assertion that for all positive integers n, the following inequality holds: [DMR 1974] [H(delta(n)) - n^2/2]^2 < 36 n^3 where: H(k) = 1 + 1/2 + 1/3 + ... + 1/k delta(n) = eta(1)^(n-1) * eta(2)^(n-2) * ... * eta(n-2)^2 * eta(n-1) eta(q) = gcd{a > 1 : a | q} Clearly, this can be expressed as a calculation involving only integers. Best wishes, Adam P. Goucher
Sent: Monday, May 09, 2016 at 6:02 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] BusyBeaver(8000) is undecidable.
I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it?
On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov> wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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-fu n
_______________________________________________ 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
_______________________________________________ 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
_______________________________________________ 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
No, GCD. eta(p^k) = p, where p^k is a prime power, and eta(q) = 1 otherwise. Best wishes, Adam P. Goucher
Sent: Monday, May 09, 2016 at 9:33 PM From: "Schroeppel, Richard" <rschroe@sandia.gov> To: math-fun <math-fun@mailman.xmission.com> Cc: "rcs@xmission.com" <rcs@xmission.com>, "Schroeppel, Richard" <rschroe@sandia.gov> Subject: Re: [math-fun] [EXTERNAL] Re: BusyBeaver(8000) is undecidable.
LCM?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Adam P. Goucher Sent: Monday, May 09, 2016 2:04 PM To: math-fun@mailman.xmission.com Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
The Riemann Hypothesis is equivalent to the assertion that for all positive integers n, the following inequality holds: [DMR 1974]
[H(delta(n)) - n^2/2]^2 < 36 n^3
where:
H(k) = 1 + 1/2 + 1/3 + ... + 1/k
delta(n) = eta(1)^(n-1) * eta(2)^(n-2) * ... * eta(n-2)^2 * eta(n-1)
eta(q) = gcd{a > 1 : a | q}
Clearly, this can be expressed as a calculation involving only integers.
Best wishes,
Adam P. Goucher
Sent: Monday, May 09, 2016 at 6:02 PM From: "Allan Wechsler" <acwacw@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] BusyBeaver(8000) is undecidable.
I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it?
On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov> wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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-fu > n > _______________________________________________ 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
_______________________________________________ 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
_______________________________________________ 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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
You can avoid floating point by using rational approximations. For the purpose at hand, we don't care if the denominators are bigna. Lagarias's paper, "An Elementary Problem Equivalent to the Riemann Hypothesis" http://www.math.lsa.umich.edu/~lagarias/doc/elementaryrh.pdf mentions several elementary equivalences, by various authors. L's Problem E is to show For all n>1, sigma(n) < H(n) + e^H(n) * log(H(n)). Any exception will disprove RH. If RH is true, the checking-all-n program will run forever. Sigma(n) is the sum of the divisors of n; H(n) is the nth harmonic number, 1 + 1/2 + 1/3 + ... + 1/n. At the end of the paper, he mentions a result of Kaneko that Sigma(n) < e^H(n) log(H(n)) with n>60 also works. We might skirt around the transcendental functions by replacing e^H(n) with n * e^gamma, and log(H(n)) with the sum of 1/(n H(n)). If this works, we can change the problem inequality into comparing a rational number with e^gamma. Some factorial identities include an e^gamma; these might be reworked into a rational-number problem. Or we could ask RWG to give us a suitable series. The spread between Lagarias & Kaneko gives some wiggle room to select a suitable accuracy for e^H(n) and log(H(n)). This probably will take more than 27 states. But less than 5372. Anyone for the Masters Tournament of code golf? Rich -----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 11:02 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable. I don't actually know enough about RH to have a good intuition about how hard it is to "check". Don't you need to implement floating-point arithmetic first? Or is there a more discrete way of looking at it? On Mon, May 9, 2016 at 12:57 PM, Schroeppel, Richard <rschroe@sandia.gov> wrote:
And RH?
-----Original Message----- From: math-fun [mailto:math-fun-bounces@mailman.xmission.com] On Behalf Of Allan Wechsler Sent: Monday, May 09, 2016 9:46 AM To: math-fun Subject: [EXTERNAL] Re: [math-fun] BusyBeaver(8000) is undecidable.
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
_______________________________________________ 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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Adam P. Goucher -
Allan Wechsler -
James Propp -
Neil Sloane -
Schroeppel, Richard