Wikipedia:Reference desk/Archives/Mathematics/2014 August 16

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 16

Knuth's up-arrow notation

How much money is being paid by the check in this xkcd comic? I found Knuth's up-arrow notation but didn't understand it. 00:22, 16 August 2014 (UTC) — Preceding unsigned comment added by 71.79.68.10 (talk)

It is an extremely large number. It is way to big to write the digits. In fact, it is proabably way to big to even write the number of digits. Offhand, I'd guess that the number of digits in the number is way bigger than the number of atoms in the universe. Bubba73 ^{You talkin' to me?} 00:46, 16 August 2014 (UTC)

Even the number of digits in the number of digits in the number is larger than the number of atoms in the visible universe, as is the number of digits in the number of digits in the number of digits in the number, and so in. In fact, the number of times I would have to prepend "number of digits in" before the number could be written down is larger than the number of atoms in the visible universe. As is the number of digits in it. -- BenRG (talk) 01:33, 16 August 2014 (UTC)

It's even bigger than that: The number of digits in the number of times you would have to prepend "number of digits in" before the number is larger than the number of atoms in the visible universe. Sławomir Biały (talk) 12:01, 16 August 2014 (UTC)

Can anyone figure out what the third term (i.e. S_¤¤(1000)) on the right is meant to be? —Quondum 13:59, 16 August 2014 (UTC)

I was only focused on the term with the arrows. I thought maybe the S thingie was something to do with states in statistical mechanics, although it would be quite amusing if this was actually some stupendously small number, rendering the amount on the check some trivial number of cents. This seems unlikely though. Sławomir Biały (talk) 14:10, 16 August 2014 (UTC)

When the general context is xkcd humor, anything could be the case. But in the context of the specific xkcd what if page, it seems that a large number is intended. —Quondum 15:15, 16 August 2014 (UTC)

It may be S_BB, referring to the busy beaver function. -- BenRG (talk) 18:39, 16 August 2014 (UTC)

Sounds right. In this case, not only is it a huge number, it's also probably non-computable. -- Meni Rosenfeld (talk) 22:19, 16 August 2014 (UTC)

Not sure exactly what you mean by that. Every natural number, of course, is a computable number well, that is, its image under the natural map into the reals is, hi Bo.

Maybe you have in mind some sort of feasible computation, something that can actually be done within the bounds of physical realizability? In that case, we have other problems, because (say) the decimal representation of the number isn't one that can be feasibly written down, never mind computed, which makes it sort of trivial to say it can't be feasibly computed. If you allow more compact representations, then what's wrong with one that just represents it in terms of the Busy Beaver function? That representation is certainly computable.

So not saying you're wrong, just that it's not terribly clear what the claim means. --Trovatore (talk) 22:44, 16 August 2014 (UTC)

Hmm... I'm not sure myself what I mean, but it's certainly not that it's not feasible in the physical universe (that could be said about the Knuth arrow number here, but I wouldn't call it non-computable. Given a classical computer and a huge, but finite, amount of RAM and CPU time, I can tell you the value of any digit you please of this number).

Now that you say it, it does sound obvious that every natural number is computable, but since the BB function is not computable, it makes sense to me that some of its values (such as $S(1000)$) are non-computable in some way. Maybe not that the number itself is not computable, but that it's impossible to compute the equivalence of its BB representation and its more usual representations, such as binary expansion.

Maybe something along the lines of "there exists an integer $n$ such that for every $m\in \{0,1\}$, there is no proof in ZFC that the nth binary digit of $S(1000)$ is m"? (where, when we make this statement formal, we don't substitute the actual number for S(1000), we write down the definition.) Does that make sense?

Or maybe I'm just wrong and there is no sense in which particular values of the BB function are not computable. -- Meni Rosenfeld (talk) 07:53, 17 August 2014 (UTC)

It makes sense, although I'm not sure it's true at 1000. It's certainly true for some $S_{BB}(k)$, purely on the grounds of noncomputability; otherwise, we could compute $S_{BB}$ by enumerating all ZFC proofs until we find the one that gives us the value of $S_{BB}$ on our desired input. In fact, we can construct a $k$ where it holds: let $M$ be the machine that searches for a ZFC proof of $0=1$, then outputs the Gödel number of that proof. Let $k$ be the number of states in $M$. Then a ZFC proof of $S_{BB}(k)$ would allow you to prove consistency of ZFC simply by checking that none of the first $S_{BB}(k)$ proofs prove $0=1$.--80.109.80.78 (talk) 08:43, 17 August 2014 (UTC)

I thought something like that might have been what you (Meni) had in mind.

Yes, absolutely, it could be the case that you can't prove in ZFC what the value of BB(1000) is. I don't know whether that's actually the case or not, but it may well be. Definitely there is some N such that you can't prove in ZFC what the value of BB(N) is.
That does not, however, make the value non-computable. It just means that ZFC is insufficiently strong to decide what it is. There is a real answer, Platonistically; a particular first-order theory just might not get you there.
There is no such thing as a non-computable natural number, or a non-computable value of a function from the naturals to the naturals. Non-computability applies only when you have infinitely many values to produce. Any finitely many natural numbers are always computable.
Here's the confusion, maybe. Computability is not about justifying an answer. It's only about whether there can exist a program that correctly finds the answer, whether the program is justified or not. The program might produce the answer completely by accident, as it were, and it would nevertheless witness computability. --Trovatore (talk) 09:26, 17 August 2014 (UTC)

Going back to the psychology/intent of the xkcd strip: I find it interesting that it used a product of three big numbers, each of which seems to require a deeper level of understanding of its sheer size, perhaps so that the smaller numbers fill in where understanding of the larger number(s) is just missing. There is also an interesting irony in the strip: that the cheque (check) would be inherently valueless, something that is not alluded to in the strip but could not have escaped Randall. I am reminded of a challenge run by Scientific American decades ago: readers were to mail in a whole number, and the reader submitting the largest number would receive $1,000,000 divided by the sum of all received numbers (or something to that effect). They even pointed out the optimal strategy. Apparently some of the numbers submitted were of the same ilk as on the xkcd cheque, so no money needed to be paid. —Quondum 15:24, 17 August 2014 (UTC)

That was the Luring lottery. Some people did submit the largest number they could manage to define on a postcard. Hofstadter wrote in his next column about how sad that made him because it showed how blindly selfish some of his readers were, in contrast to his superrational self, of course. I think the selfish ones were the people who tried to extract a substantial payout from SA (that it could ill afford) while doing nothing of value themselves. The people who submitted large numbers saved SA from a potentially difficult situation, and some of them were apparently pretty creative about it, unlike the people who followed Hofstadter's instructions. Anyway, getting back to the check, yes, it didn't make sense. -- BenRG (talk) 22:37, 17 August 2014 (UTC)

Interesting point. I have never agreed with Hofstatder about "superrationality", but this is an angle that I can't recall ever occurred to me.

(Would a mil actually have hurt SA that badly, even if they'd had to pay out the whole thing? I guess a million dollars was a lot of money back then.) --Trovatore (talk) 23:33, 17 August 2014 (UTC)