Finding the largest integer describable with a string of symbols of predefined length

Question

(This question is motivated by the reading of the article Large numbers and unprovable theorems by Joel Spencer, which can be found at http://mathdl.maa.org/images/upload_library/22/Ford/Spencer669-675.pdf and that I recommend).

We all know of the game where a card of a predefined size, say 3x5 cm, is given to every contender, and whoever writes the biggest (positive) integer on his, wins. Naive answers are easily defeated by iteration of fast-growing functions; those are defeated by induction, and these by transfinite induction. However, if a system of axioms is prefixed, then we cannot pursue this strategy forever: for example, if we are only willing to accept Peano's Axioms (PA), then $f_{\alpha}(n)$ (where $\alpha$ is an ordinal number and $f$ is defined à la Ackermann) is computable (in the sense that the axioms ensure that a program to compute it exists and will terminate in finite time) when $\alpha < \epsilon_0$, but not if $\alpha = \epsilon_0$.

This problem suggests two related questions to me:

• It is known that the Ackermann function is well-defined inside AP, and that other functions which grow much faster, like the one in the strong version of the finite Ramsey Theorem of Paris-Harrington, or Goodstein's function whenever it grows fast (I think), or $f_{\epsilon_0}(9)$, cannot be defined everywhere just by application of AP, because they "grow too fast for AP". Is there a rigorous definition of what it means for a function to grow too fast for AP (or any other arithmetical axiom system)? Can we establish in any sense a "limit" for this process? For example, can we find a "threshold function" F, depending on the axioms, such that if f dominates F then f is not computable and if F dominates f then it will be? (I'm thinking about something among the lines of the convergence of the p-series for p>0 whenever p>1 and its divergence whenever p<=1).

• Building in the exposition above Spencer observes that, between experts, this game is not funny and reduces to claims of legitimacy (over the validity of the axioms they are supposed to use), since if we allow just a fixed amount of characters for describing our number, and our axioms system is prefixed also, then THERE in fact IS a largest number computable on that system (and thus competitors would come to a draw). However, what happens if we consider the following metagame? Instead of fixing the axiom system beforehand, we allow every contender to (secretly) choose his own system of axioms for arithmetic, in the hope that his will allow faster-growing computable functions than those of the others. Doing this, the contender takes the risk, while trying to get more and more power from the axioms, of actually getting an inconsistent system! Whoever gets the biggest (computable) number in a consistent axiom system wins. Is this game interesting, or is it "flawed" too? In adittion, inconsistency may be proved within the axiom system, but its consistency would have to be proven in a more powerful framework. Which one would you select and why? What about the metametagame of letting those frameworks to the election of the players? Is that still interesting?

Answer 1

My first remark is that if you allow players to pick their own theories, but only allow consistent theories to win, then you will not be able to compute the winner of the contest. The reason is that the consistency of a theory is not in general a computable question.

To see this, suppose that we had an algorithm that could compute consistency of any given finite theory. Using it, I claim that we can solve the halting problem. Given any Turing machine program $p$ and input $n$, form the theory $T$ asserting the basic facts of arithmetic (a small fragment of PA suffices), plus the assertion that $p$ never halts on input $n$. If $p$ does halt on input $n$, then this theory is inconsistent. And if it doesn't, then the theory is consistent, being true in the standard model. So if we could check consistency, we could solve the halting problem. Since that is impossible, we cannot check consistency in a computable manner.

My second remark is that if all players work in a fixed consistent theory $T$, but play descriptions of numbers that succeed to define unique numbers provably in the theory $T$, then you still won't be able to compute the winner. For example, perhaps one player plays the definition: the smallest size proof of a contradiction in some theory $S$, if $S$ is inconsistent, otherwise $10$, which $T$ can prove uniquely describes a number, without setttling the question of Con(S). But if another player plays $12$, then you will seem to need to decide Con(S) in order to determine the winner, which is impossible by my previous remarks. 

Answer 2

Although one cant find a threshold function with exactly the properties you ask for, there is often something quite close to a threshold function, given as follows:

For an integer n, consider all Turing machines of size n such that the given theory can prove they halt with a proof of size at most n. Then define f(n) to be the largest number of steps that any of these machines take before halting.

This function is computable if the theory satisfies some form of consistency, possibly omega consistency. The theory cannot show that this is computable, and although there are smaller functions that the theory cannot show are computable, they are in some sense not much smaller. So for most practical purposes it is a threshold function.

Answer 3

"For example, can we find a "threshold function" F, depending on the axioms, such that if f dominates F then f is not computable and if F dominates f then it will be? (I'm thinking about something among the lines of the convergence of the p-series for p>0 whenever p>1 and its divergence whenever p<=1)."

This is a well studied phenomenon. The answer is no and it follows from the theory of subrecursive degrees. Typically there will be a dense structure of subrecursive degrees in the threshold region. A possible standard reference for PRA might be: The Ackermann functions are not optimal, but by how much? H. Simmons: Journal of Symbolic Logic 75 (1):289-313 (2010). There is also more extensive work by Lars Kristiansen et al on the subject. Even some analogy with forcing pops up in this context (joint work with Sy Friedman et al.)

Andreas Weiermann

Answer 4

Given a computable function f(n), the function g(n) = nf(n) is also computable and dominates it.

Similarly, given a non-computable function f(n), the function g(n) = f(n)/n is also non-computable (let's ignore the fact that f(n) need not be divisible by n) and is dominated by it.

So F can be neither computable nor non-computable. In classic logic we've reached a contradiction.

Another problem with your definition is that you might have incomparable functions, i.e. functions where the test is inconclusive.

Answer 5

Building in the exposition above Spencer observes that, between experts, this game is not funny and reduces to claims of legitimacy (over the validity of the axioms they are supposed to use), since if we allow just a fixed amount of characters for describing our number, and our axioms system is prefixed also, then THERE in fact IS a largest number computable on that system (and thus competitors would come to a draw).

The problem with this, as I understand it, is that once you allow enough characters, even with a finite (but sufficiently-strong) set of axioms, there's no longer a proof that the number you've described is the largest computable, as you can't prove that all the other descriptions terminate with smaller numbers (i.e., this is effectively the halting problem in disguise). You know that there's a largest number but you can never be certain that some given number is actually it.

Answer 6

Scott Aaronson has written a lovely essay on just this question, although focusing on computation instead of logic. http://www.scottaaronson.com/writings/bignumbers.html

Answer 7

It obviously depends on the common language of attendants. In this situation, no previous knowledge should be assumed. If one needs two pages to define a function and just write it as a simple symbol, it is cheating. From informational aspect, how many bits we can use to express a concept in most compact and not ambigious form from none, is the real problem. You can write down "Pi" easily,but you can not write down a infinity sequence of Pi. But the first expression is cheating, it depends on our education experience, and the second form is not applicable. A proper answer may be a finate size program which can output Pi digits in non-stop mode. But it may not be the smallest in size.