Why care about the Church-Turing thesis?

The Church-Turing thesis (CT) says that every function that is computable in an intuitive sense is computable by an ordinary computer. Here are some reasons why you might be interested:

1. In one sense, the CT tells us the limits of physical computation: what can be computed and what cannot. For most functions cannot be computed by ordinary computers; they are usually called uncomputable functions. Is it possible to do better? Is it possible to build something computationally more powerful than what ordinary computers (like the one you are using now) can compute? This is the question addressed in my upcoming talk (see previous post). It’s a very intricate question, which has recently been subject to a lively debate.

2. Many people believe the mind-brain is a computing mechanism. If this is correct and CT is true in the relevant sense, then computers can do everything that minds can. But it’s not trivial to specify what the relevant sense is, and what the exact consequences are. If the mind-brain is not a computing mechanism, however, the Church-Turing thesis is not directly relevant to the power of minds.

3. Many people actually think that CT or some mathematical result related to it entails that the mind is a computing mechanism. In an important recent paper (published in J. Phil 2000, click here for an abstract), Jack Copeland argues conclusively that this is a fallacy. More sophisticated people have used CT in arguments that the mind-brain is a computing mechanism, but this is still a mistake. I have written a paper (forthcoming in Synthese) that shows in some detail where those arguments go wrong.

The Physical Church-Turing Thesis: Modest of Bold?

This is the title of my talk at the Eastern APA, in the session on Classical Computation and Hypercomputation (see previous post). The other presenter is Oron Shagrir and the commentator is Jack Copeland. Jack is probably the most distinguished philosopher of AI and computation, and Oron is one of the best philosophers in this area. Both are probably less well known in the US than they deserve. They are, respectively, from Israel and New Zealand. If you are based in the US, you may not have many other opportunities to see them in action. So if you are in NYC next week, you should consider coming to our session on Wednesday.

Eastern APA: Classical Computation and Hypercomputation

There will be a session on hypercomputation and related matters (such as the Church-Turing thesis) at the meeting of the American Philosophical Association, Eastern Division, in NYC, on Wednesday, December 28, between 5:15 and 7:15. As far as I know, it’s the first APA session entirely devoted to recent discussions of hypercomputation and the Church-Turing thesis.