Monday, January 01, 2007

Gregory Chaitin on physics and mathematics

I stumbled on this interesting discussion with Gregory Chaitin, one of the discoverers of algorithmic information theory, on the relationship between physics and mathematics. Some excerpts below.

Cristian Calude: I suggest we discuss the question, Is mathematics independent of physics?

Gregory Chaitin: Okay.

CC: 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?

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

CC: 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.

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

CC: 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.

GC: 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.


[GC:] 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.

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

GC: 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 (ℵ0)?
universe with continuity and real numbers (ℵ1)?
universe with higher-order cardinals (≥ ℵ2)?
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?

CC: 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...

GC: 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.''


CC: 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 sparing partners and to do research on new openings.

GC: 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.

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

GC: 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.

CC: 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?

GC: 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!

CC: 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!

GC: What do you mean, Cris?

CC: 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...

GC: 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...

CC: 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?

*P. J. Cohen, ``Skolem and pessimism about proof in mathematics,'' Phil. Trans. R. Soc. A (2005) 363, 2407-2418; J. T. Schwartz, ``Do the integers exist? The unknowability of arithmetic consistency,'' Comm. Pure & Appl. Math. (2005) LVIII, 1280-1286.

GC: No.

CC: 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.''

GC: 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.

CC: 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?

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


Anonymous said...

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

Interestingly, most CS theorists believe that randomness does NOT help when it comes to computational complexity (P=BPP).

Steve Hsu said...


I'm confused by that, since there seem to integrals I can do (to some chosen accuracy) exponentially faster if I have access to a random number generator. This is how we do lattice QCD, for example. If it turns out that only pseudorandom numbers exist, I won't be able to do those integrals to arbitrary accuracy, so there seems to be a sharp difference of the type Chaitin mentions.

I'm not sure where that fits in computational complexity theory, though.

Anonymous said...

Interesting discussion. I just posted a short quote from it, and a link to this page of this blog, at the "Stupidity from our old friend Sal" thread of the Good Math, Bad Math science blog

Blog Archive