There's an absolutely fundamental famous problem called the halting problem. The problem is to decide whether a computer program will ever halt.
Most people don't understand why this is a problem at first. If you take a computer program and you put it into a computer, and it halts, you know it's halted. If you want to decide if a program will halt in an hour, you run it for an hour, and it's either halted or it hasn't. If you want to decide whether it halts in a day, you run it for a day, and it either halts or it doesn't.
What turns out to be a tremendously fundamental conceptual problem---and this has been known since the 30's---is to decide if a program will ever halt, where there's no limit on the time it takes.
Of course if a program does halt eventually, if we're very very patient we can find that out, by just running it. Maybe in a million years or in a billion years (I'm speaking now as a mathematician---this is all rather theoretical) we'll see that it halted.
What turns out to be the absolutely fundamental problem is to decide that a program that doesn't halt will never do it.
And then, instead of asking whether or not a program halts, you ask what is the probability that a program chosen at random will halt. That's when you get complete randomness. That's when I've shown you get complete absolute randomness, unpredictability and incomprehensibility.
D: Is this in the ordinary arithmetic that people learn at school?
C: That's a very good question.
Clearly, there's nothing more certain than the fact that two plus two is equal to four. I'm not saying that sometimes it will come out five and sometimes it's going to come out three. I'm only dealing with the whole numbers. Questions like this are clearly very easy to settle. This is probably the most solid and concrete part of mathematics.
Instead the first step is to mirror the halting problem. The same way that one asks whether or not a program ever halts, one can look at equations involving whole numbers and ask whether or not they have a solution.
That's the first step. That's a more abstract question.
If there is a solution for an equation, one can eventually discover that, by experimenting and trying different possibilities for the solution. The problem is to prove that there is no solution. That's equivalent to the halting problem, and escapes the power of mathematics in some cases.
But it doesn't give complete randomness.
What I've done is to go to a slightly more abstract question. That question is, to ask about an equation involving whole numbers, not whether or not it has a solution, but does it have an infinity of solutions or only a finite number of solutions (and no solution is a finite number of solutions).
If you construct the equations in the right way, and then you ask whether the number of solutions is finite or infinite, I can show that you get complete randomness. You get something that is completely incomprehensible, that is completely unpredictable, and that no matter how much cleverness a mathematician will apply, will forever be incomprehensible and show absolutely no pattern or structure.
Since this is rather unbelievable, I thought that it was important to actually write the equations down and show them to people, to make this randomness as tangible as possible. These equations turn out to be enormous. In fact the first one is two hundred pages long. I had to use a computer to write it out.
D: So this calls for pessimism?
C: No, I think it's wonderful! Who would have thought that the whole numbers had it in them to behave in this fascinating, rich, unexpected fashion! Who knows what else they're capable of doing! I think this is very exciting.