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.