[FOM] Comment on Church's Thesis

Walter Carnielli carniell at cle.unicamp.br
Wed Jan 7 14:29:18 EST 2004

Addamo wrote:

 >Do you or anybody know a proof of the undecidability of the Halting 
 >not depending on Church's Thesis?

Hi, Adam:

In effect, you do not need any appeal to Church's thesis in order  to 
prove the undecidabiity of the  Halting
problem,or anything else in computability. Besides doing all proofs in 
detail, we dedicate an entire chapter of
our book  below (Chapter 25, pages 223-238) discussing the thesis, 
including  bad uses of it. Church's thesis
is not part of the mathematical  arsenal, but a bridge between  
mathematics and philosophy; even if Church's
thesis were to be abandoned, the theory of recursive functions would no 
loose its mathematical status: it could
turn perhaps less interesting or less significant, but  no less correct.

Richard L. Epstein  and  Walter A. Carnielli,
"Computability: computable functions, logic and the foundations of 
mathematics,  with the timeline Computability and Undecidability". 
Second edition. Wadsworth/Thomson Learning,Belmont, CA, 2000.

Best regards,


Walter A. Carnielli                                  
Centre for Logic, Epistemology and the History of Science - CLE
State University of Campinas - UNICAMP 
P.O. Box 6133
13083-970 Campinas -SP, Brazil

Fax: +55 -19- 3289-3269                        www  
Tel.: +55 -19 -3788-6518                       e-mail: 
carniell at cle.unicamp <mailto:carniell at cle.unicamp.br>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/fom/attachments/20040107/a4575549/attachment.html

More information about the FOM mailing list