Tuesday, November 16, 2010

Through a crystal darkly

In previous remarks on randomness and computation, I mentioned the work of Gregory Chaitin, a mathematician and theorist who has written and spoken (he is a brilliant speaker) extensively for both specialist and general audiences. Chaitin's technical work is highly regarded, but his interpretations and extrapolations are sometimes a little idiosyncratic and he is inclined to sound a bit New Agey at times. (He is rumored to receive help in his thinking from a giant crystal!)

Paul Davies (a physicist and writer) is, by contrast, sober and restrained - even a little pedestrian by comparison - but he is a reliable guide within his areas of expertise. I recently came across a foreword by Davies to a book of Chaitin's essays* in which Davies gives his perspective on the significance of Chaitin's work and its implications for physics and our view of the world generally.

Chaitin (who had been obsessed from his childhood years with Kurt Gödel's incompleteness theorem) "greatly extended the scope of Gödel's basic insight," writes Davies, "and recast the notion of incompleteness in a way that brings it much closer to the real world of computers and physical processes. A key step in his work is the recognition of a basic link between mathematical undecidability and randomness. Something is random if it has no pattern, no abbreviated description, in which case there is no algorithm shorter than the thing itself which captures its content. And a random fact is true for no reason at all; it is true 'by accident' so to speak ... Chaitin was able to demonstrate that mathematics is shot-through with randomness ... Mathematics, supposedly the epitome of logical orderliness is exposed as harboring irreducible arbitrariness." (p. vi)

"[M]athematics contains randomness - or accidental, reasonless truths," Davies explains, "because a ... universal Turing machine [an idealized computer], may or may not halt in executing its program, and there is no systematic way to know in advance if a function is computable (i.e. the Turing machine will halt) or not." (p. viii)

But this limitation on what we can know or predict (known as Turing uncomputability) applies not just to mathematics and computers but also to scientific theories. On Chaitin's view, a scientific theory is like a computer program that predicts our observations (the experimental data).

Indeed, in the words of Paul Davies, " ... we may regard nature as an information processing system, and a law of physics as an algorithm that maps the input data (initial conditions) into output data (final state). Thus in some sense the universe is a gigantic computer, with the laws playing the role of universal software." (p. viii)

And if the laws of physics are computer algorithms, there will be randomness in the laws of physics stemming from Turing uncomputability. But, according to Davies, the randomness will, in reality, be "even more pronounced than that which flows from Turing uncomputability." (p. viii)

He points out that the real universe differs in a crucial respect from the concept of a Turing machine. "The latter is supposed to have infinite time at its disposal: there is no upper bound on the number of steps it may perform to execute its program. The only relevant issue is whether the program eventually halts or not, however long it takes. The machine is also permitted unlimited memory ... If these limitless resources are replaced by finite resources, however, an additional, fundamental, source of unknowability emerges. So if, following Chaitin, we treat the laws of physics as software running on the resource-limited hardware known as the observable universe, then these laws will embed a form of randomness, or uncertainty, or ambiguity, or fuzziness - call it what you will - arising from the finite informational processing capacity of the cosmos." (pp. viii-ix)

There are, it seems, different forms or levels or randomness. The 'mild' form which - as chaos theory shows - is implicit even in classical, deterministic physics; the pseudo-randomness which can be generated by simple computer algorithms; the well-known randomness inherent in quantum mechanics; and perhaps the deepest levels of all stemming from proven features of idealized computers (Turing machines) and from seeing the universe itself as a giant computer - one with specific limitations on its processing capacities.

These are difficult (and to some extent speculative) ideas. But I think they are worth pursuing and may even have profound implications for how we see ourselves and our world.

It is, of course, impossible to draw definitive political or metaphysical conclusions from them, but, if the ideas are sound, there will be such conclusions to draw.

Let me just mention two thoughts which come immediately to mind: Chaitin's and Davies' notions are utterly incompatible with any political ideology which attempts to predict, plan and control human affairs; and they also appear to undermine perspectives which incorporate notions of a providential force operating behind the scenes and impinging on natural processes, historical events and/or individual destinies. 

* Thinking about Gödel and Turing: essays on complexity, 1970-2007 (World Scientific, 2007).