A Dialogue on Mathematics and Physics

Cristian S. Calude and Gregory J. Chaitin

 

Cristian Calude: Let’s recall David Deutsch’s 1982 statement:

The reason why we find it possible to construct, say, electronic calculators, and indeed why we can perform mental arithmetic, cannot be found in mathematics or logic. The reason is that the laws of physics ‘happen’ to permit the existence of physical models for the operations of arithmetic such as addition, subtraction and multiplication.

Does this apply to mathematics too?

Gregory Chaitin: Yeah sure, and if there is real randomness in the world then Monte Carlo algorithms can work, otherwise we are fooling ourselves.

Calude: So, if experimental mathematics is accepted as ‘mathematics’, it seems that we have to agree that mathematics depends ‘to some extent’ on the laws of physics.

Chaitin: You mean math conjectures based on extensive computations, which of course depend on the laws of physics since computers are physical devices?

Calude: Indeed. The typical example is the four-color theorem, but there are many other examples. The problem is more complicated when the verification is not done by a conventional computer, but, say, a quantum automaton. In the classical scenario the computation is huge, but in principle it can be verified by an army of mathematicians working for a long time. In principle, theoretically, it is feasible to check every small detail of the computation. In the quantum scenario this possibility is gone.

Chaitin: Unless the human mind is itself a quantum computer with quantum parallelism. In that case an exponentially long quantum proof could not be written out, since that would require an exponential amount of ‘classical’ paper, but a quantum mind could directly perceive the proof, as David Deutsch points out in one of his papers.

Calude: Doesn’t Roger Penrose claim that the mind is actually a quantum computer?

Chaitin: Yes, he thinks quantum gravity is involved, but there are many other possible ways to get entanglement.

Calude: How can such a parallel quantum proof be communicated and checked when it exists only in the mind of the mathematician who ‘saw’ it?

Chaitin: Well, I guess it’s like the design of a quantum computer. You tell someone the parallel quantum computation to perform to check all the cases of something, and if they have a quantum mind maybe they can just do it. So you could publish the quantum algorithm as a proof, which the readers would do in their heads to verify your claim.

Calude: On paper you have only the quantum algorithm; everything else is in the mind! What about disagreements, how can one settle them ‘keeping in mind’ (no pun!) that quantum algorithms are probabilistic? Aren’t we in danger of loosing an essential feature of mathematics, the independent checkability of proofs in finite time?

Chaitin: Well, even now you don’t publish all the steps in a proof, you depend on people to do some of it in their heads. And if one of us has a quantum mind, then probably everyone does, or else that would become a prerequisite, like a high IQ, for doing mathematics!

Calude: Theoretical physics suggests that in certain relativistic space-times, the so-called Malament-Hogarth space-times, it may be possible for a computer to receive the answer to a yes/no question from an infinite computation in a finite time. This may lead to a kind of ‘realistic scenario’ for super-Turing computability.

Chaitin: Well, to get a big speed-up you can just take advantage of relativistic time dilation due either to a very strong gravitational field near the event horizon of a black hole or due to very high-speed travel (near the speed of light). You assign a task to a normal computer, then you slow down your clock so that you can wait for the result of an extremely lengthy computation. To you, it seems like just a short wait, to the computer, aeons have passed…

Calude: Physicist Seth Lloyd¹ has found that the ‘ultimate laptop’, a computer with a mass of one kilogram confined to a volume of one litre, operating at the fundamental limits of speed and memory capacity determined by the physics of our universe, can perform 10⁵¹ operations per second on 10³¹ bits. This device sort of looks like a black hole.

Chaitin: And he’s just published a book called Programming the Universe. The basic idea is that the universe is a computation, it’s constantly computing its own time evolution.

Calude: What about the Platonic universe of mathematical ideas? Is that ‘muddied’ by physics too? To exist mathematics has to be communicated, eventually in some written form. This depends upon the physical universe!

Chaitin: Yes, proofs have to be written on paper, which is physical. Proofs that are too long to be written down may exist in principle, but they are impossible to read.

Calude: Talking about writing things down, logicians have studied logics with infinitely long formulas, with infinite sets of axioms, and with infinitely long proofs.

Chaitin: How infinite? ℵ₀, ℵ₁, ℵ₂?

Calude: Could it be that such eccentric proofs correspond to something ‘real’?

Chaitin: Well, if people had ℵ₂ minds, then formulas ℵ₀ characters long would be easy to deal with! There’s even a set-theoretical science fiction novel by Rudy Rucker called White Light in which he tries to describe what this might feel like. I personally like a world which is discrete and ℵ₀ infinite, but why should Nature care what I think?

In one of his wilder papers, physicist Max Tegmark suggests that any conceptually possible world, in other words, one that isn’t self-contradictory, actually exists. Instead of conventional Feynman path integrals summing over all histories, he suggests some kind of crazy new integral over all possible universes! His reasoning is that the ensemble of all possible universes is simpler than having to pick out individual universes!

Leibniz had asked why is there something rather than nothing, because nothing is simpler than something, but as Tegmark points out, so is everything. In his approach you don’t have to specify the individual laws for this particular universe, it’s just one of many possibilities.

Calude: What about constructive mathematics?

Chaitin: Of course the mathematical notion of computability depends upon the physical universe you are in. We can imagine worlds in which oracles for the halting problem exist, or worlds in which Hermann Weyl’s one second, half second, quarter second, approach actually enables you to calculate an infinite number of steps in exactly two seconds. But I guess computability can handle this, everything relativises, you just add an appropriate oracle. All the proofs go through as before.

Calude: Are you talking about a physical Church-Turing Thesis?

Chaitin: Yes I am—but I think the notion of a universal Turing machine changes in a more fundamental way if Nature permits us to toss a coin, if there really are independent random events.² If Nature really lets us toss a coin, then, with extremely high probability, you can actually compute algorithmically irreducible strings of bits, but there’s no way to do that in a deterministic world.

Calude: Didn’t you say that in your 1966 Journal of the ACM paper?

Chaitin: Well yes, but the referee asked me to remove it, so I did. Anyway, that was a long time ago.

Calude: A spin-off company from the University of Geneva, id Quantique, markets a quantum mechanical random number generator called Quantis. Quantis is available as an OEM component which can be mounted on a plastic circuit board or as a PCI card; it can supply a (theoretically, arbitrarily) long string of quantum random bits sufficiently fast for cryptographic applications. A universal Turing machine working with Quantis as an oracle seems different from a normal Turing machine. Are Monte Carlo simulations powered with quantum random bits more accurate than those using pseudo-randomness?

Chaitin: Well yes, because you can be unlucky with a pseudo-random number generator, but never with real random numbers. People have gotten anomalous results from Monte Carlo simulations because the pseudo-random numbers they used were actually in sync with what they were simulating. Also real randomness enables you, with probability one, to produce an algorithmically irreducible infinite stream of bits. But any infinite stream of pseudo-random bits is extremely redundant and highly compressible, since it’s just the output of a finite algorithm.

Calude: In a universe in which the halting problem is solvable many important current open problems will be instantly solved: the Riemann hypothesis or the Goldbach Conjecture.

Chaitin: Yes, and you could also look through the tree of all possible proofs in any formal axiomatic theory and see whether something is a theorem or not, which would be mighty handy.

Calude: Talking about the Riemann hypothesis, which is about primes, there’s the surprising connection with physics noticed by Freeman Dyson that the distribution of the zeros of the Riemann function looks a lot like the Wigner distribution for energy levels in a nucleus.³

And in an inspiring paper on ‘missed opportunities’ written by Dyson in 1972, he observes that relativity could have been discovered 40 years before Einstein if mathematicians and physicists in Göttingen had spoken to each other.

Chaitin: Well in fact, relativity was discovered before Einstein by Poincaré—that’s why the transformation group for Maxwell’s equations is called the Poincaré group—however Einstein’s version was easier for most people to understand.

But mathematicians shouldn’t think they can replace physicists: There’s a beautiful little 1943 book on Experiment and Theory in Physics by Max Born where he decries the view that mathematics can enable us to discover how the world works by pure thought, without substantial input from experiment.

Calude: What about set theory? Does this have anything to do with physics?

Chaitin: I think so. I think it’s reasonable to demand that set theory has to apply to our universe. In my opinion it’s a fantasy to talk about infinities or Cantorian cardinals that are larger than what you have in your physical universe. And what’s our universe actually like?

• a finite universe?
• discrete but infinite universe (ℵ₀)?
• universe with continuity and real numbers (ℵ₁)?
• universe with higher-order cardinals (≥ ℵ₂)?

Does it really make sense to postulate higher-order infinities than you have in your physical universe? Does it make sense to believe in real numbers if our world is actually discrete? Does it make sense to believe in the set {0, 1, 2, …} of all natural numbers if our world is really finite?

Calude: Of course, we may never know if our universe is finite or not. And we may never know if at the bottom level the physical universe is discrete or continuous…

Chaitin: Amazingly enough, Cris, there is some evidence that the world may be discrete, and even, in a way, two-dimensional. There’s something called the holographic principle, and something else called the Bekenstein bound. These ideas come from trying to understand black holes using thermodynamics. The tentative conclusion is that any physical system only contains a finite number of bits of information, which in fact grows as the surface area of the physical system, not as the volume of the system as you might expect, whence the term ‘holographic’.

Calude: That’s in Lee Smolin’s book Three Roads to Quantum Gravity, right?

Chaitin: Yes. Then there are physical limitations on the human brain. Human beings and computers feel comfortable with different styles of proofs. The human push-down stack is short. Short-term memory is small. But a computer has a big push-down stack, and its short-term memory is large and extremely accurate. Computers don’t mind lots of computation, but human beings prefer ideas, or visual diagrams. Computer proofs have a very different style from human proofs. As Turing said, poetry written by computers would probably be of more interest to other computers than to humans!

Calude: In a deterministic universe there is no such thing as real randomness. Will that make Monte Carlo simulations fail?

Chaitin: Well, maybe. But one of the interesting ideas in Stephen Wolfram’s A New Kind of Science is that all the randomness in the physical universe might actually just be pseudo-randomness, and we might not see much of a difference. I think he has deterministic versions of Boltzmann gas theory and fluid turbulence that work even though the models in his book are all deterministic.

Calude: What about the axioms of set theory shouldn’t we request arguments for their validity? An extreme, but not unrealistic view discussed by physicist Karl Svozil, is that the only ‘reasonable’ mathematical universe is the physical universe we are living in (or where mathematics is done). Pythagoreans might have subscribed to this belief.

Should we still work with an axiom—say the axiom of choice—if there is evidence against it (or there is not enough evidence favouring it) in this specific universe? In a universe in which the axiom of choice is not true one cannot prove the existence of Lebesgue non-measurable sets of reals (Robert Solovay’s theorem).

Chaitin: Yes, I argued in favor of that a while back, but now let me play Devil’s advocate. After all, the real world is messy and hard to understand. Math is a kind of fantasy, an ideal world, but maybe in order to be able to prove theorems you have to simplify things, you have to work with a toy model, not with something that’s absolutely right. Remember you can only solve the Schrödinger equation exactly for the hydrogen atom! For bigger atoms you have to work with numerical approximations and do lots and lots of calculations…

Calude: Maybe in the future mathematicians will work closely with computers. Maybe in the future there will be hybrid mathematicians, maybe we will have a man/machine symbiosis. This is already happening in chess, where Grandmasters use chess programs as sparring partners and to do research on new openings.

Chaitin: Yeah, I think you’re right about the future. The machine’s contribution will be speed, highly accurate memory, and performing large routine computations without error. The human contribution will be new ideas, new points of view, intuition.

Calude: But most mathematicians are not satisfied with the machine proof of the four-color conjecture. Remember, for us humans, Proof = Understanding.

Chaitin: Yes, but in order to be able to amplify human intelligence and prove more complicated theorems than we can now, we may be forced to accept incomprehensible or only partially comprehensible proofs. We may be forced to accept the help of machines for mental as well as physical tasks.

Calude: We seem to have concluded that mathematics depends on physics, haven’t we? But mathematics is the main tool to understand physics. Don’t we have some kind of circularity?

Chaitin: Yeah, that sounds very bad! But if math is actually, as Imre Lakatos termed it, quasi-empirical, then that’s exactly what you’d expect. And as you know Cris, for years I’ve been arguing that information-theoretic incompleteness results inevitably push us in the direction of a quasi-empirical view of math, one in which math and physics are different, but maybe not as different as most people think. As Vladimir Arnold provocatively puts it, math and physics are the same, except that in math the experiments are a lot cheaper!

Calude: In a sense the relationship between mathematics and physics looks similar to the relationship between meta-mathematics and mathematics. The incompleteness theorem puts a limit on what we can do in axiomatic mathematics, but its proof is built using a substantial amount of mathematics!

Chaitin: What do you mean, Cris?

Calude: Because mathematics is incomplete, but incompleteness is proved within mathematics, meta-mathematics is itself incomplete, so we have a kind of unending uncertainty in mathematics. This seems to be replicated in physics as well: Our understanding of physics comes through mathematics, but mathematics is as certain (or uncertain) as physics, because it depends on the physical laws of the universe where mathematics is done, so again we seem to have unending uncertainty. Furthermore, because physics is uncertain, you can derive a new form of uncertainty principle for mathematics itself…

Chaitin: Well, I don’t believe in absolute truth, in total certainty. Maybe it exists in the Platonic world of ideas, or in the mind of God—I guess that’s why I became a mathematician—but I don’t think it exists down here on Earth where we are. Ultimately, I think that that’s what incompleteness forces us to do, to accept a spectrum, a continuum, of possible truth values, not just black and white absolute truth.

In other words, I think incompleteness means that we have to also accept heuristic proofs, the kinds of proofs that George Pólya liked, arguments that are rather convincing even if they are not totally rigorous, the kinds of proofs that physicists like. Jonathan Borwein and David Bailey talk a lot about the advantages of that kind of approach in their two-volume work on experimental mathematics. Sometimes the evidence is pretty convincing even if it’s not a conventional proof. For example, if two real numbers calculated for thousands of digits look exactly alike…

Calude: It’s true, Greg, that even now, a century after Gödel’s birth, incompleteness remains controversial. I just discovered two recent essays by important mathematicians, Paul Cohen⁴ and Jack Schwartz.⁵ Have you seen these essays?

Chaitin: No.

Calude: Listen to what Cohen has to say:

I believe that the vast majority of statements about the integers are totally and permanently beyond proof in any reasonable system.

And according to Schwartz,

truly comprehensive search for an inconsistency in any set of axioms is impossible.

Chaitin: Well, my current model of mathematics is that it’s a living organism that develops and evolves, forever. That’s a long way from the traditional Platonic view that mathematical truth is perfect, static and eternal.

Calude: What about Einstein’s famous statement that

Insofar as mathematical theorems refer to reality, they are not sure, and insofar as they are sure, they do not refer to reality.

Still valid?

Chaitin: Or, slightly misquoting Pablo Picasso, theories are lies that help us to see the truth!

Calude: Perhaps we should adopt Svozil’s attitude of ‘suspended attention’ (a term borrowed from psychoanalysis) about the relationship between mathematics and physics…

Chaitin: Deep philosophical questions are never resolved, you just get tired of discussing them. Enough for today!

 

Notes