Graduate studies at Western
|Abstract||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)|
|Through your library||Only published papers are available at libraries|
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 downloads23 ( #60,278 of 740,210 )
Recent downloads (6 months)1 ( #61,680 of 740,210 )
How can I increase my downloads?