The Comical Misunderstandings of O'Leary and Marks

I rarely read Denyse O'Leary's blog because it is so unreadable: she is, without a doubt, one of the worst writers in Canada. But today I noted this post praising a recent talk by Robert Marks, the Baylor engineering professor and intelligent design advocate, on the subject of algorithmic information theory, and the work of Turing, Gödel, and Chaitin.

I wasn't at all surprised to see that O'Leary doesn't really understand what's going on. After all, she has no training in science and mathematics, and her books demonstrate her lack of understanding. In her post's most comical moment, she gives Alan Turing's first name as "Alvin", apparently confusing computer science's most famous theoretician with a chipmunk.

But Marks is not stupid, so I was surprised to see several significant misunderstandings in his powerpoint presentation.

Mistake 1: The title is wrong. He says, "Things Gödel Proves a Computer Will Never Do". But it was Turing, not Gödel, who proved that there are problems that a Turing machine cannot solve.

Mistake 2: Marks calls the idea that "There exist things that are true that cannot be derived from fundamental principles" a "new startling mathematical idea from algorithmic information theory". But it isn't. It's an old idea from Gödel, dating from 1931.

Mistake 3: Marks says "we can't write a computer program to determine anything another arbitrary computer program will do. (This is called Rice’s theorem.)". This is false (and I have just finished teaching a course about the subject). Rice's theorem is about the languages accepted by Turing machines, not the machines themselves. For example, the problem "given a computer program, does it run for more than 100 steps on empty input?" is certainly solvable, simply by simulating the program in question. Less trivially, the problem of deciding whether a given Turing machine ever makes a left move on a given input is also solvable. I sometimes give this problem as a homework problem in my course. Marks, apparently, would get it wrong.

Mistake 4: Marks says that "Gödel’s Proof (1931) showed, from any set of assumptions, there are truths that cannot be proven." Again, not true. Presburger arithmetic, for example, is complete, consistent, and decidable.

Mistake 5: This objection may be more contentious. Marks thinks the work of Gödel and Turing has important implications for physics. I don't, and the reason is that we don't prove our theories in physics the same way we prove our theorems in mathematics. Physical theories represent our current understanding of an approximation to the natural world, not diktats on how it must behave.

If anything, it at least possible that novel physical theories overturn our understanding of the importance of, say, the halting problem. As Robert Geroch recently remarked at the Perimeter Institute, the existence of Hogarth-Malament spacetime might imply that the halting problem is solvable (it provides an infinite timelike curve entirely in the history of another point, so we could set up the computation "back then" and see if it ever terminated "later").

Marks clearly derives his understanding of Gödel and Turing from reading popular works, not textbooks on the subject. I'd recommend he read Torkel Franzen's Gödel's Theorem: An Incomplete Guide to Its Use and Abuse.

As for O'Leary's claim that Gödel's and Turing's work somehow puts a "nail in the coffin of materialism", the kindest thing I can say is that she has not proved her case. Indeed, she hasn't even presented a case.