Happy St. Patrick’s Day 2014

Neil L. is not a computer scientist—he is a Leprechaun. He has visited me every year since I started writing GLL, always visiting on St. Patrick’s day.

Today I want to report on what happened this year.

Days ago I received a email from him—a first. It said:

If you agree to not catch me, I will be at your place at 12:01am Monday. Neil L.

One year I did catch him, affording me three wishes. I thought I would get some of the secrets of the universe, but he outsmarted me.

I replied back that yes I would stop trying to catch him. I got no reply. In any event I decided I would stay up late Sunday night and see if he would appear.

Just after midnight I smelled a pungent odor, then saw a puff of green smoke, and there was Neil L. standing before me. His pipe in his mouth was putting out that green smoke, which has a strong but surprisingly pleasant smell. My dad was a pipe smoker when I was young, quitting later in life—of course his tobacco smoke was never green.

Neil said, “Good day to you on this fine St. Patrick’s Day. I read your reply, quite clever.” I responded that I did not think I was being clever at all. Neil smiled, took another puff, and said “Come on—saying I will not try to catch you—come now.” He added that I must promise not to catch him. I nodded back yes, and he sat down on a chair across from where I was sitting. His short legs dangled off the floor.

Neil’s Answer

We sat there for a moment in silence, then as I was about to speak, he interrupted and said, “I will answer ye any one question, no tricks, straight up.” I looked back surprised and figured that I had nothing to lose so I asked the question,

Is P=NP?

Neil puffed away for quite a while and then said, “I appreciate your not trying to be tricky with your question. I could answer of course no, since the letters ‘P’ and ‘NP’ are different. But I will be straightforward with you. No teasing, no games today.” I was excited, perhaps I would finally know the answer.

He added, “I could make you swear that you cannot repeat this to anyone, but I do not need to, for none will believe ye.” I said OK, so what is the answer? Neil smiled and said:

“We have not yet determined the answer. That’s the truth. No tricks. I swear as a Leprechaun, may you find all my gold coins if I lie.”

I thought, what does that mean? Not determined yet? A mathematical statement is either true or it’s false. No tricks.

Neil’s Explanation

I asked what did he mean by “not yet determined?” Either P=NP or P≠NP, I responded. Neil smiled and said that he would explain. He said:

“You live in a world that is really a simulation. We control it all.”

I looked at him, thinking this was another trick. Neil registered my shock and added: “Yes it must be hard for you to believe, but it is true. How else can you explain a Leprechaun that appears and disappears.” With that he puffed some more on his pipe and laughed and added, “I told you no one will believe ye.”

Okay I said, could he explain what he meant by “not yet determined”? He nodded yes. “The simulation mostly runs itself quite well, but there are situations where it gets stuck and the committee of seven then step in and decide what it should do.”

I asked what is the ‘committee of seven’? He answered, “It is a group of over fifty-seven wise ones who are tasked with maintaining the simulation and fixing any unexpected problems. We cannot be expected to have foreseen all possible situations, so they are the ones who decide things.” Another puff and more green smoke, and he continued, “Don’t even ask why it’s the committee of seven, it’s too long a story.”

I finally laughed and said that this was his best visit ever—what a silly story. I told him that I did not believe a word of it. Neil looked at me and said he understood, yet he could give me some “proof.” I said that would be great.

Neil’s Proof

Neil answered, “Look I know it is hard for ye to believe, but I will give ye examples of why it is true.” The first he gave is that in ancient times there were more miracles and strange occurrences, including demons and the like. Did I not agree? I said that that was the folklore but… He interrupted and said “Ay—that was when we first began to run the simulation; we were new at it and made mistakes. We are much better today. Much.”

I started to say yes, nothing like that happens today, but Neil waved me off and said, “we don’t make errors but we still have fun—especially with your sports.” I gave him a cold stare, but he continued: “You are a fan of sailing, if I recall. What are the odds of coming back from 8–1 down in a best-of-9 series?” He was talking about the Oracle US team’s comeback in last September’s America’s Cup final. I rounded the simple coin-flip answer: “About 250–1 against, more since they looked badly beaten.” Neil asked whether there had been anywhere near 250 final series since the America’s Cup began, and needed no answer from me as he puffed with a grin.

Commercial T-shirt source

“Do you mess with bookies?” I blurted out, then felt ashamed for incivility. But Neil leaned forward with a hand gesture and hush for my attention: “The simulation gives us a budget of improbability, and by the Rule of Improbability we have only a tiny window to deviate. But we are free to choose which improbable events happen to maximize our fun, so long as we do not also violate the Rule of Indistinguishability.” Without even pausing for my query, he went on: “That Rule is the same one you use in defining computational zero knowledge—we can prove things to you, but it would take you too much effort to prove our tricks to a third party. To keep it, we put much effort into not messing with things. For instance our simulator had to work hard this weekend to calculate the true odds and allowances for Warren Buffett’s $1,000,000,000 Bracket Challenge, but we’re all set for “March Madness” now.”

I asked if they could mess with physics, and he told me about a third rule: “The Rule of Consistency is that we may not overturn any past experimental results once their confidence has gone beyond 5 sigma.” Of course humanity has only had the 5-sigma rule for declaring things like the Higgs Boson or primordial gravity waves to exist for a short time, so I asked what about physics in the past. Neil continued, “I know nothing about this, but there was a problem with something called beta-decay.” I jumped in and said: yes there is a surprising effect—it is one of few physical effects ever discovered that tells left from right. Neil added, “Yes that is it. Some fool made a mistake and caused that to happen. Once it got into the world the committee thought it was fun to have it. A kind of insider joke. Of course it meant we had to re-program the physics part of the simulator to compute using Dirac notation, long before Dirac invented it.”

The Meta Question

I was still numb from the story—it could not be true? Yet. What he just said about “programming” made me realize, surely the laws of computability and complexity must apply to them too. Now I knew I had him, so I asked:

Surely P=NP must have an answer in your world—which your committee is subject to. What is the answer there?

Neil answered calmly, “As I said, it is not yet determined.”

I expostulated, “Not yet determined for us you said. But surely it is determined for them.”

A little patronizingly Neil replied, “Nay me lad. By me honor, when I said it is not yet determined I spoke true. I did say there are over fifty-seven on the committee of seven. We cannot violate consistency amongst ourselves for a mathematical proposition.”

I remembered from writing our recent simulation post that people who live in simulations would write their own simulations that other people could live in, ad-infinitum all the way down. For Neil to be right it could be infinities all the way up too. Then I realized, “Ah—I see why you said ‘over fifty-seven’ before: there’s you plus your committee of 7, then each of those is subject to a committee of 7, so and it goes on from there. But how can there be infinitely many leprechauns?”

To my surprise he gave a pained start: “Ay, ye have catched me in a secret, and ye did not try to—it was me saying too much. So I must now tell ye exactly how many leprechauns we are, and it will prove to ye what I said about your mathematics.” I stood as he stood up as if to leave, and I saw he was really a little guy, only my size. Neil spoke once more as his pipe puffed mightily.

“We have other committees and hierarchies with other numbers, so our total is the sum of all the natural numbers —and the smoke will tell you what that is.”

With a “pouf” he vanished, but once again his smoke stayed behind, and some of it knotted itself into what first looked like a snake until I recognized it was making the Greek letter zeta. Then I saw the value, and I realized that choosing it must have caused endless committees endless mirth in their endless—but thereby finite—hierarchy:

I rushed to look this up in a book, the first to hand being a physics book on String Theory which I had just ordered from Amazon, and sure enough there it was:

Open Problems

Ken and I wish you a happy and safe St. Patrick’s Day. Do you believe a word of our Leprechaun, Neil? I do not. “Not determined yet”—that is ridiculous. It is silly, yet how can I distinguish

I obtained two surprising data points for 2012 and 2013 yesterday which strengthen my own evidence against a different kind of “inflation” that almost all strong chess players are said to believe in.