This is the first example that the OP made me think of—unless it’s disqualified because no one has actually found a counter-example yet; it’s just been proved (first by Littlewood in 1914) that there is one. But it was a conjecture that, for a long time, a lot of mathematicians thought was true, because the evidence was so in its favor.
I stumbled upon this thread while Googling for something else, thought I should mention Graham’s number, but see Chronos beat me to it.
Graham’s number G(64), which is almost indescribably preposterously large, is just an upper bound for a certain unknown Ramsay number, for which the lower bound was only 6. Graham’s paper closes with the amusing line: “As you can see there is room for some improvement in these bounds.”
Unfortunately I can’t find Graham’s paper on-line just now.
One place that mentions it is Robert Munafo’s website, with many large numbers and other interesting stuff:
James
Quoth Indistinguishable:
Assuming that [your fixed language of choice] is complex enough to be able to express that sentence, then that sentence does not specify any number at all, since it’s impossible to determine what the largest specifiable number is.
(One small typo on my part: Where I wrote “[longer than your upper bound of choice]”, I should of course have written instead “[at least as long as your upper bound of choice]”)
As for Chronos’s statement, I may or may not agree with it, but I’m not quite sure yet; could you explain more precisely what you mean by it? E.g., a sentence (rather, technically, a noun phrase) like “The largest number output by a program of length less than 1000 characters in (some completely defined, deterministic standardization of) C++”. Is this the sort of thing you would classify under “impossible to determine” and “does not specify any number at all”? Why or why not?
Isn’t this just the Busy Beaver function for n=1000 ?
And for that particular programming language, yes. As you note, my post #38 was just a way of saying “The Busy Beaver function for [your language of choice] evaluated at [your number of choice]”.
g(g64)
The problem is that in order to know what the largest number that can be output by such a program is, you’d have to have all of the numbers output by such programs. But due to the halting problem, you can never be certain that you have all such numbers. Basically, you can systematically produce, and run in parallel, all programs up to your specified length. At any given time, some of them have concluded and returned a number, some of them have concluded and returned something that isn’t a number, and some of them are still running. The ones that return something that isn’t a number, we can just ignore. The ones that have returned a number, we can easily go through and see what the largest of those numbers is. But for the ones that are still running, they might keep running forever, or they might eventually return a number, possibly one that’s larger than any of the numbers we have already. There’s no way to tell.
Ok. So, in saying “does not specify any number at all”, you are (correctly) pointing out that the relevant noun phrase gives no indication of how to go about algorithmically calculating its referent, as well as perhaps putting forth the position that for the purposes of the “Let’s name large numbers” game, all that should count are specifications which do come in the form of such an explicit recipe (so that, for example, “The smallest counterexample to the Goldbach conjecture, if one exists, or 0 otherwise” would also not count as specifying a particular number)? Fair enough; you can choose whatever rules for the name-large-numbers game you like which you find most entertaining. Or are you going further and saying something more than just this?
I can’t believe someone seriously wrote a shrewd businessduck. Some people have too much time on their hands.