May 2016 - mathfun@mailman.xmission.com

Re: [math-fun] BusyBeaver(8000) is undecidable.
by Schroeppel, Richard 09 May '16

09 May '16

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(a)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(a)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(a)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(a)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(a)mailman.xmission.com >> > > https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > > >> > _______________________________________________ >> > math-fun mailing list >> > math-fun(a)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(a)mailman.xmission.com >> https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun >> > > _______________________________________________ math-fun mailing list math-fun(a)mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

5 7

Re: [math-fun] Russian Postal Problem
by Henry Baker 09 May '16

09 May '16

Does it help to send qubits (whether locked or unlocked) through the Russian mail system? Can qubits eliminate the need for telephone calls? At 11:59 AM 5/9/2016, Fred Lunnon wrote: >But the penny has just dropped about Diffie-Hellman and "man-in-the-middle" >--- Alice and Bob must acknowledge receipt by telephone, otherwise the post >office might impersonate each to the other and nab the goodies after all!

1 0

Re: [math-fun] Russian Postal Problem
by Hilarie Orman 09 May '16

09 May '16

Combination lock. Puzzle box that looks solid but has sliding panels. Embed the ring in opaque epoxy. Use a passenger pigeon. Use a drone. A catapult. Hilarie

1 0

Re: [math-fun] Russian Postal Problem
by Henry Baker 09 May '16

09 May '16

Ding! Ding! Ding! Yes, Victor, that is the standard/canonical solution. But I'd be interested if there are any solutions involving sending keys inside of locked boxes. (I don't know if there are any, but it would be interesting if there were.) At 11:30 AM 5/9/2016, Victor Miller wrote: >Is the following within the rules? > >1) Man sends box containing ring, padlocked to the lady. >2) Lady adds her own padlock to the box and sends it to the man. >3) Man removes his padlock with his key and sends the locked box back to >the lady. >4) Lady uses her own key to remove the her padlock. >No keys are exchanged. > >On Mon, May 9, 2016 at 2:18 PM, Dave Dyer <ddyer(a)real-me.net> wrote: > >> At 10:49 AM 5/9/2016, Brent Meeker wrote: >> >Send the key first. Only send the box after the key arrives. >> >> No, send the box first. If an anonymous locked box won't get >> through, the whole exercise is pointless. Any attempt to send >> the key first might alert the authorities to watch for the box. >> Once the box is safely transferred, as many attempts as necessary >> can be made to send a key for the box, which is already secure.

1 0

Re: [math-fun] Russian Postal Problem
by Henry Baker 09 May '16

09 May '16

These locks are traditional symmetrical key locks with a single private key (physical keys can be duplicated, but it isn't necessary in this case). Hint: Perhaps my thinking is perverse, but I think this problem is weirdly analogous to the missionaries & cannibals problem. At 07:38 AM 5/9/2016, Adam P. Goucher wrote: >Diffie-Hellman key exchange. > >Best wishes, > >Adam P. Goucher > >> Sent: Monday, May 09, 2016 at 2:49 PM >> From: "Henry Baker" <hbaker1(a)pipeline.com> >> >> I don't recall if this problem was ever discussed on math-fun: >> --- >> The Russian Postal Service Problem >> >> A man in the west of Russia wants to send a small but expensive gift (a ring) to his lady love who lives in the east. Unfortunately, the Russian postal service is corrupt: they will open every letter they get and remove any valuables from them before sending them on. >> >> The man could send the ring in a locked box (the postal service is underfunded and cannot afford tools to break into locked boxes), but his partner would have no way of opening the box. If the postal service believe he will send a key separately, they will hold onto the box until the key arrives. >> >> He could use a combination lock and telephone the combination to her, but the KGB monitor all phone lines and will tell their mates in the postal service everything he says. He can still talk to her; he just can't rely on secrecy. >> >> So, the postal service will deliver the parcel intact only if it is locked and if they know that no key will ever come their way. Delivering the ring in person is not an option. >> >> How does he safely send the ring to his partner?

1 0

[math-fun] Plane delayed by mathematics
by Guy Haworth 09 May '16

09 May '16

http://www.theguardian.com/us-news/2016/may/07/professor-flight-delay-terro… Guy Haworth

1 0

[math-fun] BusyBeaver(8000) is undecidable.
by rcs＠xmission.com 09 May '16

09 May '16

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

3 4

[math-fun] Differential equations. See something, say something.
by Warren D Smith 08 May '16

08 May '16

Professor's airplane math leads to flight delay AP 6:01 p.m. EDT May 7, 2016 An Ivy League professor said his flight was delayed because a fellow passenger thought the math equations he was writing might be a sign he was a terrorist. American Airlines confirms that the woman expressed suspicions about University of Pennsylvania economics professor Guido Menzio. She said she was too ill to take the Air Wisconsin-operated flight. Menzio said he was flying from Philadelphia to Syracuse on Thursday night and was solving a differential equation related to a speech he was set to give at Queen's University in Ontario, Canada. He said the woman sitting next to him passed a note to a flight attendant and the plane headed back to the gate. Menzio, who is Italian and has curly, dark hair, said the pilot then asked for a word and he was questioned by an official. "I thought they were trying to get clues about her illness," he told The Associated Press in an email. "Instead, they tell me that the woman was concerned that I was a terrorist because I was writing strange things on a pad of paper." Menzio said he explained what he had been doing and the flight took off soon afterward. He was treated respectfully throughout, he added. But, he said, he was concerned about a delay that a brief conversation or an Internet search could have resolved. "Not seeking additional information after reports of 'suspicious activity' ... is going to create a lot of problems, especially as xenophobic attitudes may be emerging," he said. American spokesman Casey Norton said the Air Wisconsin crew followed protocol to take care of an ill passenger and then to investigate her allegations. Norton wouldn't specify the details of the allegations, but said officials determined them to be non-credible. The woman was rebooked on a later flight.

4 3

[math-fun] Bitcoin creator revealed
by Eric Angelini 08 May '16

08 May '16

http://www.drcraigwright.net/jean-paul-sartre-signing-significance/ Best, É.

7 8

[math-fun] The information in a dice roll
by Bill Gosper 08 May '16

08 May '16

I bought a Dice Lab d120 http://www.newyorker.com/tech/elements/the-dice-you-never-knew-you-needed and asked young Rohan how many rolls, on the average would I need to simulate a roll of two ordinary dice. I expected the answer 1.1: Divide the range into 36+36+36+12, and if you land in the 12, roll again for a trit. But Rohan responded with a rapid-fire sequence of constructions that converged toward an answer of .748+ Indeed, log(36)/log(120) can be approached by on-line radix-converting a real fraction base 120 to base 36. But lg 36 ~5.17 bits is the information assuming the dice are distinguishable. It seems to me that for indistinguishable dice, the ensemble is 1+1,2+2,...,6+6, 1+2|2+1, ... , 5+6|6+5 , for which I get 2 lg 3 + 7/6 ~ 4.3366 bits. For six rolls, this gives lg(3^12*2^7 = 68024448) bits. Given a "digit" base 68024448, can anyone think of a way to convert it to six rolls of a pair of indistinguishable dice? Or am I completely confused? --rwg

2 1