Is the church-Turing thesis true?

Minds and Machines 3 (3):283-312 (1993)
Abstract
  The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other kind of effective procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1)
Keywords Causality  Church's Thesis  Procedure  Science  Turing Machines
Categories (categorize this paper)
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
 
Download options
PhilPapers Archive


Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 12,084
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA
Carol E. Cleland (1985). Causality, Chance and Weak Non-Super Venience. American Philosophical Quarterly 22 (4):287 - 298.

View all 14 references

Citations of this work BETA

No citations found.

Similar books and articles
Analytics

Monthly downloads

Added to index

2009-01-28

Total downloads

107 ( #11,172 of 1,101,880 )

Recent downloads (6 months)

22 ( #9,304 of 1,101,880 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Start a new thread
Order:
There  are no threads in this forum
Nothing in this forum yet.