# Philosophical interpretation of computability of a finite math problem

There is an interesting debate in the area of Enumerative Combinatorics, a branch of Mathematics. Several mathematician are having a somewhat tongue-in-check debate whether a certain (very large and difficult to find exactly) number is computable. I am wondering if this conversation can be translated into the standard philosophy of science language.

Specifically, the authors argue about an integer N which is a 1,000-th number in a this sequence (the nature of the sequence is not particularly important for this discussion). Consider the following sequence of quotes:

Dr. Z.: "Not even God knows the number N".

Dr. S.: "I’m not sure how good Dr. Z.’s God is at math, but I believe that some humans will find N in the not so distant future."

Dr. C: "Dr. S. revealed that he has a bet with Dr. Z. about N. If someone comes up with the answer this year, Z. will pay S. 170 euros. The amount paid out will decrease by ten euros with every year that passes before the solution is found until the year 2030. If no solution is found by 2030, S will pay Z the whole 170 euros."

Dr. G.: "While making no Messianic claims, our asymptotics permit the approximate answer N=4.6x10^1017."

Question: How is this "God" vs. "human" problem articulated in the philosophy of mathematics? What are the competing theories? How do we understand the ability to guess an approximation based on experimental evidence?

• Their discussion seems to conflate the general concept of computability and the concept of computable-in-practice. The general concept was defined by Alan Turing. But maybe they're discussing whether one or the other applies? May 11 '15 at 10:08
• This is a finite problem, so theoretical computability is not an issue. But the appearance of "God" in mathematics makes me curious. Could it be that "Dr. Z's God" cannot do a large finite problem? May 11 '15 at 10:12
• Oh, interesting. In computational complexity we might be interested in whether there is an algorithm for determining N exactly in polynomial time, but in the meantime have poly (possibly even linear) algorithms that might make an informed guess. The most interesting part of the question might be read as asking us "how do we understand approximation here", which I don't know anything about but sounds like a neat PhilSci question. May 11 '15 at 10:47
• In terms of improving the question, (1) "Can this discussion be interpreted in philosophical terms?" is a pretty difficult type to be SE-answerable. Maybe Paul Ross has something useful on that. On that point, can you ask a more precisely answerable question, i.e. relate it to some standard theory in philosophy rather than a broad can? (Otherwise, I'm with Cheers and hth in seeing a lot of shorthand for class computability language). May 11 '15 at 10:53
• So maybe if you reworded your question part to be "how is this "God" vs. "human" problem articulated in the philosophy of math? What are the competing theories?" that would seem like an excellent question versus the present can. (I'd also suggest changing the title to make clearer you're wondering what the philosophical interpretations are related to this computability problem). May 11 '15 at 11:01

I think there are quite a number of misunderstandings in the terms used.

There are certain mathematicians who do not think numbers beyond a certain size exist. Physically the universe seems to have finitely many particles, and so there is an actual upper bound on the size of numbers we can ever write down in decimal notation. We may not even be able to express the upper bound, but it is there. If that is the criterion for "knowing a number", then not even God can write down the answer without first increasing the number of particles in the universe. But that does not mean the answer is not definable, which is a different concept. The largest prime less than 2^1000 is certainly unwritable in decimal, but I have just defined it and every mathematician agrees that such a number exists, except for the ultrafinitists who believe that a number only exists if it can be written down digit by digit. The sequence you linked to is one example of this type, and so Dr. Z's statement must be some kind of joke unless he is an ultrafinitist like Doron Zeilberger.

That said, there are certain statements expressed in Peano Arithmetic (PA) that are independent over PA in the sense that there are different models of PA in which those statements have different truth value. (A model of PA is a world that satisfies all the axioms of PA.) One might choose to adopt Zermelo-Frankel set theory (ZF), which is a stronger theory in which there is only one model of PA due to the axiom of induction. Note that "theory" here has nothing to do with scientific "theories".

The problem is that ZF is still a first-order theory (quantifying over only single objects in its domain) and hence by Godel's theorem logical entailment in ZF is equivalent to provability in ZF. Because statements in ZF can be encoded using the natural numbers and steps in a proof can be encoded via certain elementary number theoretic properties like divisibility, and then existence of a proof can be encoded, we can then encode the statement of the consistency of ZF itself as a single statement in PA. But that statement would be independent, by similar encoding of a sentence that is intended to mean "This statement is unprovable". (Self-reference is enabled by the encoding.) If it is provable, then it contradicts itself. If its negation is provable, then it is provable and thus the same contradiction comes. So either ZF is inconsistent or there is an independent statement in PA.

So there are no competing hypotheses in mathematics unlike in science. Every statement in its full context is either true or false or independent. One can choose different frameworks which may change the truth value of a statement, but there is no conflict. It just means that we can have three frameworks A,B,C such that the statement is true in A, false in B, and independent in C. If you are a platonist, you can say that at most one of the frameworks is correct.

Note that we cannot bring God into all this without specifying what exactly we mean by him knowing. It is simply ridiculous to assume that the whole world can be modeled by ZF, and even the natural numbers are idealized notions that do not actually exist in the real world. But if you say you want God to tell you whether some statement is true or false or undecidable in some theory, then if God knows everything then certainly he would be able to answer that. But if you want the exact numeric value you asked about, then how do you expect him to convey the answer?

The answer would be required to be in a certain format, such as allowing only certain operations, whether the answer can be "found" depends on the format. In this kind of precise sense and with the above considerations once you select a framework "God" is irrelevant and usually just refers to the truth value in a model, which would correspond to an oracle in computability theory. For example the halting problem is undecidable but, for a platonist who thinks that the natural numbers have a real existence, whether a program halts has a definite answer, and he can then define an oracle to give that answer and investigate what can be done with that oracle.

Finally, asymptotics is not guesswork of any sort nor does it have to do with scientific experimentation and approximation. Asymptotics is a mathematical tool that allows rigorous derivations of asymptotic bounds on functions.