[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 
problem
 >not depending on Church's Thesis?

 >Adam
 
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

------------------------------------------------------------------------
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  
:http://www.cle.unicamp.br/prof/carnielli/
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