Saturday, April 26, 2008

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.

13 comments:

Anonymous said...

Sigh. Gödel's incompleteness theorems has got to be two of the most abused theorems in all of mathematics.

I have to say that I'm impressed with your willingness to give Marks the benefit of doubt, given the tendency of IDists to twist and spin anything and everything.

Anonymous said...

Vis-a-vis Marks' "Mistake 5", Chaitin does state the following:

I should state here that AIT has an intimate connection with physics.

over here in the second para of the "Afterthoughts..." section. Of course, "intimate connection" may not be the same as "implication".

Also, I am not sure how physicist's view Chaitin's own ideas/works.

Jeffrey Shallit said...

I think Chaitin has a tendency to, shall we say, somewhat overstate the importance of work he is involved with.

Anonymous said...

Any theory rich enough to prove theorems of mathematical physics will contain incompleteness phenomena. Some computer scientists advocate axiomatizing the existence of "feasible incompleteness phenomena" by adopting "P does not equal NP" as a physical law. It is still unclear whether either form of incompleteness phenomena has any material impact on the physical world. Godel sentences are not "natural," in the sense that they do not appear in problems studied by natural scientists. Even the statement, "There are truths that are experimentally observable but not rigorously provable," is not clearly related to the Incompleteness Theorem, nor to P/NP, since interesting, observable truths may correspond to a small part of the tautologies derivable from a theory by symbolic manipulation. The case for a relationship between incompleteness/infeasibility and physical science remains to be made.

RBH said...

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.

That captures the essential difference between the intelligent design creationists and science. ID creationists regard theories as determining reality; scientists regard reality as determining theories.

Put more simply, ID creationists regard scientific "laws" as legislation, not generalizations about nature.

Lippard said...

Thanks for the reference to Torkel Franzen's book. The name was familiar to me, so I did a quick Google search, which refreshed my memory of having interacted with him on Usenet in the alt.atheism newsgroup. I'm sorry to learn from his Wikipedia page that he died two years ago this month from bone cancer.

Eamon Knight said...

Engineering prof, huh? Speaking as another engineer, Marks' claims sound like something I might say about Turing and Godel, if I didn't know just enough to recognize how tenuous my grasp of that stuff actually is, and keep quiet.

truti said...

Jeffrey,

Is it right at all to say that we prove theories in physics? We only experiment and verify isn't it?

Could you provide us a quick and simple idea of Godel's proof of god?

Thanks!

Jeffrey Shallit said...

Truti:

We don't prove theories in science the same way we prove theorems in mathematics. I think, colloquially, people often speak of a particular theory being proved, but this just means that it has passed a significant test or tests that would have disproved the theory if another result had been obtained.

All our scientific theories are susceptible of being overturned by more fruitful or comprehensive theories -- the way that Newtonian mechanics was overthrown by Einstein.

As for Gödel's "proof" of god, it is based on modal logic. I have never been very impressed by the reasonableness of modal logic, and I haven't made any effort to understand Gödel's proof.

truti said...

Jeffrey,

Thanks!

Anonymous said...

Haha, I remember using Godel's theorems and Halting Problem myself, as I was trying to explain to a friend of mine why I sympathise with Christianity, but not as a "proof", rather as a description of "how it feels". I am _not_ a ID supporter, though; it's extremely foolish that they try to reinforce a _belief_ system with [pseudo]scientific methods.

(Alex Karpov)

Fr. Terry Donahue, CC said...

Mistake 5: This objection may be more contentious. Marks thinks the work of Gödel and Turing has important implications for physics.

In 2003, Stephen Hawking addressed this issue in a talk entitled "Gödel and the end of physics":

"Up to now, most people have implicitly assumed that there is an ultimate theory, that we will eventually discover. Indeed, I myself have suggested we might find it quite soon. However, M-theory has made me wonder if this is true. Maybe it is not possible to formulate the theory of the universe in a finite number of statements. This is very reminiscent of Goedel's theorem. This says that any finite system of axioms, is not sufficient to prove every result in mathematics...
What we need, is a formulation of M theory, that takes account of the black hole information limit. But then our experience with supergravity and string theory, and the analogy of Goedel's theorem, suggest that even this formulation, will be incomplete.
"


So at the very least, Stephen now leans towards thinking that Gödel does have "important implications for physics".

Stanley Jaki proposed this connection in 1966.

Suggesting that there is such an implication/connection strikes me as an interesting possibility, rather than a mistake.

Jeffrey Shallit said...

Saying that M-theory is "reminiscent" of Gödel's theorem is a far cry from saying that Gödel puts limits on our physical theories.

Torkel Franzen, in his book Gödel's Theorem, addresses this point, and he is not very kind to the physicists who think Gödel has implications for physics.