David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Minds and Machines 12 (2):221-240 (2002)
There is an intensive discussion nowadays about the meaning of effective computability, with implications to the status and provability of the Church–Turing Thesis (CTT). I begin by reviewing what has become the dominant account of the way Turing and Church viewed, in 1936, effective computability. According to this account, to which I refer as the Gandy–Sieg account, Turing and Church aimed to characterize the functions that can be computed by a human computer. In addition, Turing provided a highly convincing argument for CTT by analyzing the processes carried out by a human computer. I then contend that if the Gandy–Sieg account is correct, then the notion of effective computability has changed after 1936. Today computer scientists view effective computability in terms of finite machine computation. My contention is supported by the current formulations of CTT, which always refer to machine computation, and by the current argumentation for CTT, which is different from the main arguments advanced by Turing and Church. I finally turn to discuss Robin Gandy's characterization of machine computation. I suggest that there is an ambiguity regarding the types of machines Gandy was postulating. I offer three interpretations, which differ in their scope and limitations, and conclude that none provides the basis for claiming that Gandy characterized finite machine computation.
|Keywords||effective computability Gandy machines human computation machine computation physical computation The Church–Turing Thesis|
|Categories||categorize this paper)|
|Through your library||Configure|
Similar books and articles
B. Maclennan (2003). Transcending Turing Computability. Minds and Machines 13 (1):3-22.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
Dina Goldin & Peter Wegner (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. [REVIEW] Minds and Machines 18 (1):17-38.
David Israel (2002). Reflections on Gödel's and Gandy's Reflections on Turing's Thesis. Minds and Machines 12 (2):181-201.
Tim Button (2009). Hyperloops Do Not Threaten the Notion of an Effective Procedure. Lecture Notes in Computer Science 5635:68-78.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.
Leon Horsten (1995). The Church-Turing Thesis and Effective Mundane Procedures. Minds and Machines 5 (1):1-8.
B. Jack Copeland & Oron Shagrir (2007). Physical Computation: How General Are Gandy's Principles for Mechanisms? [REVIEW] Minds and Machines 17 (2):217-231.
Added to index2009-01-28
Total downloads15 ( #88,744 of 1,004,811 )
Recent downloads (6 months)2 ( #39,235 of 1,004,811 )
How can I increase my downloads?