I am currently reading a book called

*Thinking about Godel and Turing*by Gregory J. Chaitin. This book, I must admit, is slightly over my head, so I walk on tippy toes holding my head back in order to keep my nose above water. I read a lot of books by people who are much cleverer than me, but then I guess I am the audience they are writing for. Richard Feynman was once called the smartest person in the world, or some such honorific, by OMNI magazine (the first issue if I recall correctly), which suitably embarrassed him, but he was one of the great physicists of his generation, if not the greatest, and yet also one of the greatest teachers. I have read no one who writes so well for people with lesser abilities than himself. I can think of other writers: Roger Penrose comes to mind, who can write for people less clever than himself; Paul Davies is another, and one would also have to include Stephen Hawking. These are to be contrasted with other academic writers I have read, who do their best to show how much cleverer they are than their readers, but risk misleading them by talking authoratively on topics outside their field. I am not an academic and I have no expertise, so, if I be so charged, I stand guilty. I am the first to admit that I am not as clever as I may appear. I am intellectually curious and I can write well, that is all. And yes, I am provocative – no apologies there.

Gregory Chaitin’s book is really a collection of essays, often transcripts of lectures or public addresses he’s given over the past 30 years. As such, he is also writing for people less clever than himself, and I think he does a commendable job. He also generously acknowledges his heroes (especially Leibniz). I only hope I don’t misinterpret him in my attempt to glean something philosophically meaningful from his text. I have to say that I found his ideas, and his exposition of them, exciting to read.

The 20th Century will be remembered for a number of things: Peter Watson performs an excellent job documenting many of its achievements in art and science in a narrative form with his magnum opus,

*A Terrible Beauty*. (Another writer who knows how to illuminate without his ego intruding in the process.) I’ve had disagreements with Watson, philosophically, and we’ve had brief correspondence, but I think this book is an achievement of almost heroic proportions, not least because he can write with equal erudition on art and science.

For my mind, the 2 outstanding events of the 20th Century, which will be remembered throughout human history, are powered flight leading to exploration beyond our planet and the invention of the computer with all its consequences. But Chaitin rightly points out that there were 2 revolutions that occurred early last century, at about the same time that humankind took flight in a literal sense, that will also be remembered as historical milestones. I’m talking about Einstein’s theories of relativity and the development of quantum mechanics. In addition to these revolutions, Chaitin adds a third: Kurt Godel’s proof of his ‘Incompleteness Theorem’ in mathematics (1931) and Alan Turing’s related theorem concerning the so-called ‘halting problem’ for computers (1936). This particular revolution requires some elaboration.

Firstly, when Turing developed his thesis, computers didn’t exist, and, in fact, Turing’s paper is better remembered for containing the purely conceptual idea of the ‘Universal Turing Machine’, which is what all modern computers are, including the one I’m now writing on. So this revolution is directly related to the more concrete revolution I referred to in the opening of my last paragraph. But Chaitin’s point, that this revolution, first enumerated by Godel, being of equal significance as relativity theory and quantum mechanics, should not be lost.

But before I continue on this theme, I would like to say something about Turing, one of my heroes. Turing is probably best known for his pivotal role in breaking the ‘enigma’ code during WWII, but I would also hope he be remembered for his tragic death, so that ignorance and prejudice would not claim such a brilliant mind in the future. Turing was one of the greatest minds of the 20th Century, arguably, second only to Einstein. Turing may not have physically invented the computer (a moot point), and it certainly would have evolved without him, in the same way that Einstein didn’t invent the Lorentz transformations that lie at the heart of relativity, and certainly relativity’s consequences would have also been discovered without him. But both men thought outside the square in a way that goes beyond cliche, and both men were ahead of their time by at least a generation, and both men were undisputed geniuses.

Turing’s death, however, is comparable to the deaths of two other great minds of science and philosophy: Socrates and Lavoisier. Socrates (arguably the father of Western philosophy) was forced to suicide for political reasons, and Lavoisier (the ‘father of chemistry’) was guillotined in the aftermath of the French Revolution. All these deaths were the result of political and social forces present at the time, and all were regretted almost immediately afterwards. One might say that they were all victims of ignorance, and that includes Turing. Turing suicided by eating an apple injected with cyanide after he was legally prosecuted for being homosexual (he was blackmailed first) and forced to take hormonal treatment that had him growing breasts. This should be kept in mind when we have conservatives in both religion and politics who think the legal attitude towards homosexuality has been ‘socially disastrous’ (Cardinal George Pell quoted by a reviewer of his latest book,

*God and Caesar*). Unfortunately and tragically, Turing was born ahead of his time in more ways than one.

A philosophical detour onto another path, we’re now back to the topic at hand. Not quite 10 years ago, when I was studying philosophy in an undergraduate course, I had to write an essay on Immanuel Kant with the subject:

*What is transcendental idealism?*In preparation I read large parts of his seminal work,

*The Critique of Pure Reason*, about as dense a text as one could find. Apparently Kant’s lectures were very popular and much more accessible than his writings. Unfortunately, he lived before the age of electronics, otherwise we might have transcripts of his lectures rather than his essays.

*The Critique of Pure Reason*is the only book I’ve read that contains at least one sentence over a page long. You may be wondering what this has to do with Godel and Turing: well, Kant wrote a great deal about epistemology which is effectively the subject of Chaitin’s book. Of more relevance to this discussion, is my conclusion in that essay: if there is a ‘transcendental idealism’, it must be the world of mathematics.

I won’t reiterate my arguments here (perhaps a future posting), but it suggests a starting point for the question that heads this essay. Kant understood that our knowledge, our perception and our interpretation of the world had 2 components: an empirical component based on experience and an ‘a priori’ component based on reasoning and imagination. It is this latter component that leads to the concept of ‘transcendental idealism’ and has more than a passing resemblance to Plato’s ‘forms’. I don’t wish to get too esoteric about this, so I will present the same idea in a more prosaic context. I’ve said elsewhere that the success of science is a direct consequence of a continuing dialectic between theory and experiment, or theory and observation. This is exactly the same thing that I believe Kant was talking about, keeping in mind that he lived in the time following Newton when it was believed we all existed in a clockwork universe.

My own particular take on this is that mathematics is the principal medium that allows this dialectic to occur. Without mathematics our comprehension of the universe (the entire natural world in fact) would be limited in the extreme. This realisation, in Western philosophy at least, began with Pythagoras, was given impetus by Galileo, Kepler, Newton and Leibniz (along with many others), but only found it’s true significance in the 20th century, with Einstein (following Maxwell), along with Bohr, Schrodinger, Heisenberg and all those who have contributed since. Chaitin’s book, as I’ve already said, is effectively about epistemology and, in particular, the epistemology of science and mathematics. In fact, Chaitin’s entire thesis is that they are more closely related than we tend to think, but I’m getting ahead of myself.

Firstly, I need to share with you Chaitin’s excitement, and sense of historical significance, that he finds in Godel’s Incompleteness Theorem of 1931. Before this theorem, and even after it, mathematicians have believed that mathematics is inherently axiomatic (going back to Euclid, another Greek), which is its strength and its claim to objective truth. But even before Godel, as Chaitin points out, Georg Cantor and Bertrand Russell had already shown that mathematical certainty could be a chimera. Cantor is best known for his ‘diagonal method’ of showing why there are more ‘real numbers’ than ‘rationals’ (Penrose gives a good exposition in

*The Emperor’s New Mind*). Turing, by the way, employed Cantor’s diagonal method in the most critical step of his ‘halting problem’ proof, so it has far-reaching consequences.

Over a hundred years ago, Cantor postulated the idea of infinite sets (transfinite numbers), which was such a radical and controversial idea for its time, that, according to Chaitin, Cantor suffered a breakdown as a result of the criticism and was never given a position in a first rate institution. Being ahead of your time can sometimes be a career stopper, no matter what your achievements. These days, Cantor is regularly referred to in mathematical texts on number theory.

Godel gave a proof, that took the whole mathematical world by surprise, that the so-called axiomatic method was flawed, or, at the very least, could not be unconditionally relied upon. Effectively, Godel’s proof and Turing’s, which is even more demonstrative, says that, no matter what formal mathematical system you have, based on a set of known axioms, there is always the possibility of mathematical ‘truths’ that cannot be derived from these axioms. So the method of determining mathematics that we have all relied upon since the concept of numbers was derived, is not so deterministic after all. Now, as Chaitin points out, despite the absolute shock this conclusion created, people have largely carried on as if it never happened. Many people see it as an esoteric anomaly that has no bearing on real mathematical problems, but, as Chaitin points out, that is not the case.

The best example would be Reimann’s hypothesis and the Zeta function. There have been some excellent books written on this subject (

*Prime Obsession*by John Derbyshire,

*The Music of the Primes*by Marcus du Sautoy and Stalking the Reimann Hypothesis by Dan Rockmore are three I enjoyed reading). I won’t elaborate, except to say that it is a convoluted and intriguing journey into the mathematical realm, and it is to do with the distribution of primes, but it’s the perfect example. It’s the perfect example because computer programmes (Turing machines) have calculated it to be correct to astronomical magnitudes, but there is still no proof. It demonstrates perfectly the so-called ‘halting problem’ because if the programme halts the hypothesis is false, and if the hypothesis is correct, then the programme will never stop (unless instructed to of course). But more than this, most mathematicians accept it as true, despite the lack of a ‘formal’ proof, and it is now used as an ‘axiom’ for other mathematical proofs, albeit conditionally. And this is what Godel said, that there can be an axiom, or axioms, outside the formal system you are using that can be the basis of newly discovered mathematical ‘truths’. Another, more readily comprehended example, also given in Chaitin’s book, is Goldbach’s conjecture: all even numbers above 2 are the sum of 2 primes. (You can check this for yourself with the first 10 even numbers, remembering that 1 is not considered a prime.) A relatively simple computer programme can be written to check this, but, again, it only stops if the conjecture is wrong. (This has been checked to 10 raised to the power of 14, 1 with 14 zeros after it).

Now, strictly speaking, what I have just described isn’t the halting problem, but a consequence of it. What Turing said (proved, in fact) is that there is no way of knowing if a programme will halt or not for a particular theorem. If we knew that, then, obviously, we would be able to say in advance if these conjectures were true or false.

Chaitin makes the comparison between this discontinuity of axioms and physics. He gives the example of Maxwell’s equations having no basis in Newton’s equations, yet forming an ‘axiom’ for Einstein’s equations of relativity. Likewise, quantum mechanics has no basis in either Newtonian mechanics or Einstein’s relativity, but has become a new ‘axiom’ for future theories (Thomas Kuhn calls them paradigms). Chaitin argues, that not only does this demonstrate that mathematics and physics are more closely related than we consider, but that there is good reason to suggest that mathematics should be done more like physics, where new axioms may not have to rely on previous ones. Chaitin calls this proposed methodology ‘quasi-empiricism’, a term coined by Imre Lakatos.

Chaitin goes even further on this subject, and claims that the similarity between physics and mathematics lies at their base, which is randomness. In fact, Chaitin claims that this is his major contribution to mathematics, arising from his invention of the term ‘Ω’ (Omega), though he calls it a discovery, to designate the probability of a programme ‘halting’, otherwise known as the ‘halting probability’. I won’t elaborate too much on this, so, if you want to know more, you will need to read his book. For Chaitin, ‘Ω’ is the logical extension of Godel’s and Turing’s landmark theories, and proof of mathematics’ inherent irreducibility (his term). The significance of this ‘discovery’, according to Chaitin, is that it’s proof that there is no mathematical ‘theory of everything’ (TOE) – no all encompassing meta-mathematical theory. But he sees this as liberating. To quote: ‘Ω shows that one cannot do mathematics mechanically and that intuition and creativity are essential.’

Another person who discusses these issues (raised by Godel and Turing) in devoted detail, is Roger Penrose (

*The Emperor’s New Mind*), but in the context of Platonism. Penrose is a self-confessed ‘Platonist’, meaning he believes that mathematics exists in an independent realm to the human mind. This is a contentious viewpoint (I discuss it from a different perspective in my Sep.07 posting:

**Is mathematics invented or discovered?**). Chaitin says very little on this question (see below), but quotes Godel, who was a ‘Platonist’, and Einstein, who was not. Paul Davies, who writes an excellent foreword to Chaitin’s book, makes the case, in a couple of books, (

*The Mind of God*and

*The Goldilocks Enigma*) that mathematics ‘shadows’ the natural world, but doesn’t call himself a Platonist. Stephen Hawking, who famously worked with Penrose on singularities and black holes, doesn't share his colleague's philosophical viewpoint at all, and calls himself an 'unashamed reductionist' and a 'positivist'. Most philosophers dismiss the notion of Plato’s forms, but mathematics is an area where it persists. I dislike the term but I agree with the philosophical premise: mathematics has an independent existence to human thought. Plato’s forms originally applied to everything, not just mathematics, so somewhere there was a perfect world (like heaven) and Earth was merely a facsimile of it. This is similar to some people’s interpretation of Taoism, but it’s not mine. But this brings me to the subject alluded to in the title of this posting: mathematics is arguably the only evidence we have of a transcendental, or metaphysical, realm.

Interestingly, people on both sides of this argument present Godel’s famous Incompleteness Theorem as supporting their philosophical point of view. Chaitin himself says, ‘[Godel’s theorem] exploded the normal Platonic view of what math is all about’, without elaborating on what he means by ‘normal Platonic view’ in this context. Russell, according to one account I read, was derisively disappointed when he met Godel and discovered he was unashamedly a Platonist. Many people I’ve met, philosophers in particular, believe that Russell and Wittgenstein settled this question for good, but I’m not sure that many physicists would agree. I once had a conversation with a philosophy lecturer, whom I greatly respected, who asked me if I thought that mathematics done by some hypothetical inhabitants in the constellation Andromeda would be the same as mathematics done by us on Earth. I answered: Of course; to which he responded: But you’re assuming that Andromedans would use base 10 arithmetic. I said that this is like saying that a tiger in China is not a tiger because it is called something else in Chinese. I used this analogy because he had used it himself to make an epistemological point earlier in the discussion. Unfortunately, he just assumed that I didn’t know what I was talking about, and I never got the opportunity to enlighten him further.

Using the same hypothetical, Chaitin quotes Stephen Wolfram (

*A New Kind of Science*), whom I haven’t read, who argues, and gives examples, of mathematics that might be different to what we are familiar with. But I would suggest, that unless the laws of the universe are significantly different on another planet, then the mathematics any inhabitants developed would be the same as ours. Because, as Davies and Penrose point out, mathematics and the natural world are married in a way that is inescapable to anyone who explores them deeply enough. Even on our own planet, different cultures developed mathematical ideas independently but were ultimately convergent. So whilst I agree that mathematics may be a boundless realm, its marriage to the natural world suggests inevitable avenues of investigation and discovery.

Penrose, in particular, argues a very strong case for Platonism. In

*The Emperor’s New Mind*, he spends an entire chapter on the Mandelbrot set (with a detour to Cantor, Euler and Gauss) and presents it as an exemplar of Platonist mathematics. The entire Mandelbrot set exists only in an infinite realm so that no one will ever see it in its entirety, yet it is generated by a simple algorithm or formula. (This leads to a discussion on complexity, which is also a key theme in Chaitin’s book, but I will return to complexity in a moment.) For Penrose, the Mandelbrot set is evidence that something can only exist in a mathematical realm that we only get a glimpse of – this is a very profound idea. (To get a glimpse, check the following link: Mandelbrot Set ) Is this different to any other work of art? Well, Penrose makes the same analogy, but the fundamental difference is that mathematics doesn’t manifest itself as a ‘unique’ or ‘one-off’ creation, as works of art do. (Someone else could have discovered Reimann’s geometry or Schrodinger’s equations, but no one else could have created Beethoven’s symphonies or Bach’s Brandenburg concertos). And it is difficult to escape the connection between mathematics and the natural world, the Mandelbrot set notwithstanding.

In any discussion on mathematics, including Chaitin's, one cannot escape infinity – it infiltrates all attempts to capture it and tie it down. It’s also what makes it elusive (take the Reimann hypothesis) and boundless in every sense (look at Π and e). It’s what takes it outside human experience and makes it ‘magical’ (like the calculus). In Euler’s famous equation, infinities abound, yet it’s a simple relationship between e, Π, i, 1 and 0 (where i is the square route of minus 1). Feynman called it ‘the most remarkable formula in math’ when he thought he had ‘discovered’ it a month before his 15th birthday. ( See link: Euler's Equation ) To appreciate the complexity that lies behind this simple equation, and the way it ties together so many branches of mathematics, you need to go to Euler's Formula.

For Penrose, it’s almost religious:

‘The notion of mathematical truth goes beyond the whole concept of formalism [this is Godel’s theorem in a nutshell]. There is something absolute and “God-given” about mathematical truth. This is what mathematical Platonism… is. Any particular formal system has a provisional and “man-made” quality about it… Real mathematical truth goes beyond mere man-made constructions.’

Strong words indeed. This has been a lengthy treatise, but not one that is especially decisive or well-argued. I have hardly touched the subject of complexity, which is a key component of Chaitin’s thesis, indeed his life’s work. One of the points he makes is that mathematical complexity may provide a key to understanding biological evolution – after all, DNA is the world’s most extraordinary piece of software. Complexity, as described by Chaitin, is effectively the difference in the length of an algorithm (in bits) to the length of the results it produces (he defines it in a logarithmic expression). The Mandelbrot set is a good example, because a very short algorithm can produce an extraordinarily detailed and complex picture of infinite proportions via a computer. DNA is, in effect, a very small molecular structure that can produce extremely complex and diverse organic entities that have life (ad infinitum it would appear); so I would argue that it’s more than just an analogy. (Chaitin makes the point that, with its 4 bases, human DNA contains 6 trillion bits of information; 6 followed by 9 zeros.)

Perhaps there is another level of complexity behind DNA in the same way that quantum mechanics exists behind classical physics. No one can anticipate what we will find. When Darwin hypothesised about evolution, no one would have predicted genes, let alone DNA. And when Newton proposed gravity no one would have predicted relativity theory, let alone quantum mechanics. We think, just like they did, that we’ve discovered everything there is to discover, but we haven’t.

This essay only scratches the surface of Chaitin’s multi-layered thesis, so, if it stimulates you, read his book. My favourite chapter is titled

*On the intelligibility of the universe*, where he liberally quotes great minds like: Einstein, Feynman and Born; all ruminating on the theoretical component of the dialectic of science that I referred to earlier.

Does Chaitin believe in a mathematical transcendental realm? Well, he certainly believes in a metaphysical approach, subscribing to a “digital philosophy” (his quotation marks), along with Edward Fredkin and Stephen Wolfram. He calls it a ‘neo-Pythagorean vision of the world’, where ‘God is not a mathematician’, but ‘a computer programmer.’ But he adds the following caveat: this is a new viewpoint, and it will be interesting to see how far it takes us.

Personally, whilst I don’t have the intellectual abilities of these people, and therefore I can’t challenge their premise, I believe there is more to the universe than algorithms. For a start, I don't believe the human mind runs on algorithms, despite what some cognitive psychologists might think (on that point I agree with John Searle and Roger Penrose).

So Chaitin argues that most real numbers are uncomputable and this makes mathematics infinitely complex (if a number can't be calculated there is no formula or algorithm for it, which makes it infinitely complex by Chaitin's own mathematical definition of complexity, though he credits Leibniz with the original idea). Also, I accept his argument that there is no overall meta-mathematical theorem - no TOE for mathematics - because that is the essence of Godel's and Turing's proofs. I agree with his statement that intuition and creativity are essential, because history has demonstrated that beyond dispute. I would not be surprised if, as he speculates, mathematics gives us an unexpected insight into biology and evolution, though, obviously, I've no idea how it might happen. And, as I have said elsewhere, I believe it is our knowledge of mathematics that will determine the limits of our knowledge of the physical universe and the natural world. In my opinion, this was Pythagoras's great paradigmatic insight and his legacy to philosophy and science.

Mathematics can take us into worlds that we don’t normally perceive: higher dimensions, complex planes, infinite series and infinitesimal intervals – but in the world we live in, it continues to uncover riches and mysteries beyond our imagination.

You may also want to read my post on The Laws of Nature (Mar.08).