[FOM] Re: Comment on Church's Thesis (Harvey Friedman)

[Dennis E. Hamilton]

Tim,

The Sliced-Bread illustration for Church's Thesis is a delight.  Thanks for that.

Although this does not come at what Harvey may have had in mind with the digraph computational model in his (unnumbered) New Years Eve note <http://www.cs.nyu.edu/pipermail/fom/2003-December/007782.html>, it does touch nicely on the question that Adam raised on 6 January <http://www.cs.nyu.edu/pipermail/fom/2004-January/007793.html>.

I want to put in a clarification because I have found it to be important in preventing C-T creep. 

First, I find one of the most useful treatments to be in

[Boolos2002] Boolos, George S., Burgess, John P., Jeffrey, Richard.  Computability and Logic. ed.4.  Cambridge University Press (Cambridge: 2002).  ISBN 0-521-00758-5 pbk.

There, Church's Thesis and Turing's Thesis are distinguished and the important notion of effective computability as a separate informal topic is preserved.  Adam and I rooted around here a little, and this is also consistent with the 3rd edition.  But in the 4th edition the authors take even more care to avoid treating effective computability (or effective procedure) as something that is formalized.  They are also careful to avoid giving the appearance of relying on the Church or Turing theses as premises.  (They do make the straightforward observation that, given the Turing-uncomputability of a halting function and "Assuming Turing's thesis, it follows that [the halting problem] is not solvable at all [p.40].")  

So, the clarification.  Turing's thesis is that Turing Computability = Effective Computability.  

Church's Thesis, in the original 1935 statement (using the term "Effective Calculability") is that lambda-definability = recursivity = effective computability, with the demonstration of the first equivalence taken as evidence for the second, roughly.  There are many conditions on this statement, including that we are talking about the effective computability of functions on the positive integers.

I base these observations on the papers as they are made available in

[Davis1965] Davis, Martin (ed.). The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Raven Press (New York: 1965). ISBN 0-911216-01-4. 

	-	-	-	-	-	-	-	-	-

About C-T creep:

I've noticed a tendency to speak of a Church-Turing thesis.  This collapse appears to be based on the demonstration that the (Turing) computable functions are equivalent to the lambda-definable ones in Turing's original paper [if he actually accomplished that -- I have not done the work to confirm it].  Turing writes in a way where tacit acceptance of Church's Thesis seems to be implied. He doesn't require it, he simply writes as if lambda-definability = effective computability, whether out of belief or assumption that it is just equivalent nomenclature, I cannot tell.

The subtlety of effective computability as an informal notion, in contrast to Turing computability, lambda-definability, and recursive (definability?) is sometimes lost in textbooks where C-T is sketched and taken as a broader statement to be accepted.  (This is then often taken as a straw man that some choose to argue against after assuming there is more to Church's thesis than is actually the case.)  

I propose that it serves us better to keep all of the notions straight and separated.

-- Dennis

-----Original Message-----
From: Timothy Y. Chow
Sent: Monday, January 12, 2004 08:58

[ ... ] Church's
Thesis says that out of all possible specifications that you might
imagine, this is the correct one.  So it says something like

"Turing machine = effective algorithm"

[ ... ]