David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
One of us has previously argued that the Church-Turing Thesis (CTT), contra Elliot Mendelson, is not provable, and is — light of the mind’s capacity for effortless hypercomputation — moreover false (e.g., ). But a new, more serious challenge has appeared on the scene: an attempt by Smith  to prove CTT. His case is a clever “squeezing argument” that makes crucial use of Kolmogorov-Uspenskii (KU) machines. The plan for the present paper is as follows. After covering some necessary preliminaries regarding the nature of CTT, and taking note of the fact that this thesis is “intrinsically cognitive” (§2), we: sketch out, for context, an open-minded position on CTT and related matters (§3); explain the formal structure of squeezing arguments (§4); after a review of KU-machines, formalize Smith’s case (§5); give our objections to certain assumptions in Smith’s argument (§6); support these objections with some evidence from general but limited-agent problem solving (§7); and explain why Smith’s argument is inconclusive (§8). We end with some brief, concluding remarks, some of which point toward near-future work that will build on the present paper (§9)
|Keywords||No keywords specified (fix it)|
|Categories||categorize this paper)|
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
No references found.
Citations of this work BETA
Naveen Sundar Govindarajalulu, Selmer Bringsjord & Joshua Taylor (2015). Proof Verification and Proof Discovery for Relativity. Synthese 192 (7):2077-2094.
Joe Johnson, Naveen Govindarajulu & Selmer Bringsjord (2014). A Three-Pronged Simonesque Approach To Modeling And Simulation In Deviant “Bi-Pay” Auctions, And Beyond. Mind and Society 13 (1):59-82.
Similar books and articles
Gualtiero Piccinini (2007). Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy. Synthese 154 (1):97-120.
Oron Shagrir (2002). Effective Computation by Humans and Machines. Minds and Machines 12 (2):221-240.
Dina Goldin & Peter Wegner (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. [REVIEW] Minds and Machines 18 (1):17-38.
Tim Button (2009). SAD Computers and Two Versions of the Church–Turing Thesis. British Journal for the Philosophy of Science 60 (4):765-792.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Saul A. Kripke (2013). The Church-Turing ‘Thesis’ as a Special Corollary of Gödel’s Completeness Theorem. In B. J. Copeland, C. Posy & O. Shagrir (eds.), Computability: Turing, Gödel, Church, and Beyond. MIT Press
Oron Shagrir & Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Benjamin Wells (2002). Is There a Nonrecursive Decidable Equational Theory? Minds and Machines 12 (2):301-324.
John T. Kearns (1997). Thinking Machines: Some Fundamental Confusions. [REVIEW] Minds and Machines 7 (2):269-87.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University
Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.
Eli Dresner (2008). Turing-, Human- and Physical Computability: An Unasked Question. [REVIEW] Minds and Machines 18 (3):349-355.
Itamar Pitowsky (2003). Physical Hypercomputation and the Church–Turing Thesis. Minds and Machines 13 (1):87-101.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Leon Horsten (1995). The Church-Turing Thesis and Effective Mundane Procedures. Minds and Machines 5 (1):1-8.
Added to index2012-02-27
Total downloads35 ( #91,859 of 1,724,890 )
Recent downloads (6 months)9 ( #72,195 of 1,724,890 )
How can I increase my downloads?