Heath Robinson goes to Church
I talked last time about left-handed amino acids and right-handed sugars. This was one of the examples of ‘emergence’ Stuart Kauffman mentions in his book Reinventing the Sacred. I now want to talk about his computing example, because I really don’t get this one.
[Third in a series on Stuart A Kauffman’s Reinventing the Sacred which began with Reinventing the sand dune.]
By the way, I’m not saying I disagree with the concept of ‘emergence’ or with the idea that the apparent fact of ‘emergence’ casts doubt on the strict version of ‘reductionism’ he knocks in his book. What I’m saying is ‘So what?’. This is particularly because of what he says about the ‘emergence’ of agency, meaning, values and ethics, and that as a result there is a ‘sacredness’ in the universe which we could justifiably refer to as ‘God’.
In Reinventing the sand dune I said I had two main gripes about Kauffman’s book. One was the assumption that ‘emergence’ was a necessary and welcome antidote to ‘reductionism’. The other was his use of ‘sacred’ and ‘God’ to describe aspects of reality.
But these two may boil down to the same objection. It’s possible that ‘strict’ reductionism is the only coherent version of reductionism, and that uncontroversial evidence or demonstration of ‘emergence’ is enough to falsify that strict reductionism. If that’s true I can accept it. But I don’t see how that kind of ‘emergence’ (and consequent ‘anti-reductionism’) can support what he says about eg the reality of ethics and why we should see the universe as sacred.
As I read I felt I was being conned, and that’s what I’m trying to unravel. There seemed to be at least two main points in the argument where I suspected a sleight of hand – but it may turn out to have been just one big one.
Enough preamble. The example of ‘emergence’ (or evidence of the falsity of reductionism) I am going to discuss now is the one Kauffman gives from computing, again following Philip W Anderson. Maybe Kauffman doesn’t present it as evidence of emergence per se but as evidence that reductionism is false. His writing isn’t exactly clear, and it seems to get more opaque just when it needs to be more lucid.
The example is that of a generic ‘Turing machine’, of which the most familiar modern manifestation is the digital computer. A Turing machine like a PC can carry out any well-specified algorithm (ie sequence of mathematical and/or logical operations).
Alonzo Church came up with a proof of the Turing machine’s so-called ‘halting problem’. The ‘halting problem’ is that there can be no general program or algorithm capable of examining any other program or algorithm (plus, if necessary, an appropriate input) and calculating whether it would complete in a finite number of steps or run forever. There could be a specific program P1 which could examine another specific program P2 and input I and decide whether P2 with input I would ever complete. But there can be no completely general program P1 capable of doing this for any other program.
(The only purely general way to see if any program P2 completes is to run it and see if it completes. But even this is not a complete answer. If P2 does complete we know it will complete. But what if it doesn’t complete in any specific time frame? How do we know it won’t complete in the next second or the next minute?)
Alonzo Church proved why there can be no completely general program or algorithm capable of doing this for any other program or algorithm. His proof is apparently related to Gödel’s Incompleteness Theorem in mathematics.
The Turing machine does not have to be a PC or an Apple Mac or an IBM mainframe. It could be completely mechanical rather than electronic – it could even be an army of people filling and emptying buckets of water to represent 1 and 0 symbols.
Kauffman uses the example of an algorithm to add up the first 100 digits of a large number and output the answer (say ‘550’). As this algorithm could be carried out on an endless variety of physical machines, he says there can be no specific set of physical conditions which are necessary and sufficient for the computer to get to the point where it completes and outputs ‘The sum of the first 100 digits is 550’. It could be a sequence of electronic events inside a PC; or another sequence of electronic events inside that same PC; or another sequence of electronic events inside another PC; or a sequence of people pouring water in and out of buckets; or someone patiently moving beads on an abacus; or any imaginable Heath Robinson (Americans read Rube Goldberg) device capable of carrying out the algorithm.
This example algorithm is of course one which we know will complete, but this presumably does not matter for Kauffman’s argument. We should forget for the moment that we do know this, because if we now apply the ‘halting problem’ to all these examples we are saying there is no general program or algorithm capable of calculating how many steps any of the PCs would take to do this calculation, or how many steps the bucket pourers would take to complete the calculation, or how many steps any of the other devices would take – and to be able to do the same for every other possible algorithm.
But this fact – ie the fact of the halting problem now proven by Church – cannot be a fact about the physics of all these devices, because this fact is independent of their individual physical characteristics. Therefore it cannot be ‘reduced’ to their physics. Kauffman calls this the ‘multiple-platform argument’.
But again what puzzles me is how this supports his overall thesis about emergence and sacredness. Or indeed: so what?
If the example is just an elaborate way to demonstrate the inadequacy of a kind of dogmatic strict reductionism, then so much the worse for that kind of reductionism.
But I’m not so sure the kind of strict reductionism Kauffman seems to have in mind is even coherent, or can be coherently stated.
If Church’s proof is sound, and that therefore the halting problem is true, then is it a truth of mathematics-and-logic – as Gödel’s Incompleteness Theorem would also be. So it is a part of mathematics-and-logic. (I’ll use ‘mathematics-and-logic’ to mean ‘mathematics and/or logic’ to avoid having to worry about where the boundary is between them, or whether there really is a boundary.)
Take a much simpler mathematical example: a triangle on a plane surface. It could be a white paper triangle, a red paper triangle, a plastic triangle, a triangle made of three stars in the sky as seen from earth, a triangle made up of another three stars in the sky, …etc. Of all these triangles it is a fact that their three angles add up to 180°. That fact is not based on their individual attributes or the physics of the particles they are individually made of. By definition you couldn’t specify an infinite list of statements about all the triangles in the universe. But even if you could, the fact that their angles add up to 180° does not reduce to a set of facts about these physical triangles.
Does this mean the fact that the three angles of a triangle add up to 180° is ‘emergent’ and that therefore reductionism is false?
If so, we need to look a bit deeper into this idea of ‘reductionism’ – which as I mentioned in Reinventing the sand dune appears to subsume or overlap with determinism. Take Laplace’s statement (which Kauffman quotes as definitive of this kind of reductionism) that a sufficient intelligence could compute the entire future and past of the universe if it knew the positions and velocities of all the particles in the universe. That statement includes the word ‘compute’, which means applying mathematics-and-logic – including the fact that the three angles of a triangle add up to 180°? If it includes that then surely this mathematics-and-logic also includes Church’s proof of the halting problem and Gödel’s Incompleteness Theorem?
I’m not claiming that either Church’s proof of the halting problem or Gödel’s proof of the Incompleteness Theorem are needed to carry out any of the computations entailed by the reductionist-determinist program. But you need mathematics-and-logic to carry out the reductionist-determinist program, and mathematics-and-logic includes Church’s proof of the halting problem and Gödel’s Incompleteness Theorem. So this reductionism-determinism presupposes a body of propositions which include Church’s proof of the halting problem and Gödel’s proof of the Incompleteness Theorem.
Which must therefore mean that in order to give a coherent account of the kind of ‘reductionism’ Kauffman has in mind, one which is vulnerable to the fact of ‘emergent’ truths, we need to presuppose something which itself includes ‘emergent’ truths, and is therefore outside that ‘reductionism’. This seems a bit of a contradiction.
Let’s be clear about what Kauffman actually says:
Let’s be clear about what Anderson’s argument does not say: it does not say that any laws of physics are violated. Physics is perfectly intact, it is merely that a determined physicist cannot come up with a list of physical events that are jointly necessary and sufficient for the water buckets, the silicon chip, or whatever else to compute the sum of the first 100 digits.
I may be missing something really subtle in advanced mathematics-and-logic, but Kauffman seems to confusing two things. One is the sets of facts about possible specific physical implementations of a computing device. The other is what makes Church’s proof of the halting problem or Gödel’s proof of the Incompleteness Theorem true.
I’ll try and unravel this next time.
© Chris Lawrence 2011.