Introduction:

The evolution of combinatorics and computer science is interesting to survey because most mathematicians initially viewed combinatorics in particular as an arcane bag of tricks that didn’t constitute very deep mathematics. So computer science developed largely as a separate tribe with a strong Hungarian influence. Perhaps mathematicians in the future will say that this was the beginning of constructive approaches to mathematics. But, the future is not promised and it is not easy to overcome the inertia of scientific conventions and tribalism.

I would like to illustrate the difficulties classical mathematicians face with a simple example.

An elementary problem for classical mathematicians:

Is it reasonable to say that \(f(n)=n!\) is defined for \(n>e^{e^{100}}\)? I think this is a reasonable question more mathematicians should consider.

Even if we had an algorithm for evaluating \(f(n)\) whose time-complexity scaled linearly in the input size:

\begin{equation} \ln(e^{e^{100}}) \text{nanoseconds} \approx e^{e^{100}} \text{nanoseconds} \approx 10^{27} \text{years} \end{equation}

which is more than \(10^{17}\) times the age of the universe.

It is meaningless to say that \(f(n)\) is defined for \(n>e^{e^{100}}\) or ‘all integers’ if there is no realistic method for evaluating \(f\) at \(n\). This example is just one instance of an exponentially large class of problems where traditional mathematics faces important epistemological constraints.

A modest proposal:

I can propose two ways forward. One way forward is for more mathematicians to systematically teach courses on the time and space complexity of algorithms to the next generation. Another way forward, which has largely developed in the form of Monte Carlo Methods, would be to encourage greater use of experimental and scientific methods in mathematics as it becomes very hard to say anything precise about combinatorially large objects.

Ultimately, I think we will need to completely rethink the foundations of mathematics in terms of the ideas of Shannon, Church, Kolmogorov and Turing.