Graduate studies at Western
Minds and Machines 12 (2):221-240 (2002)
|Abstract||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.
Leon Horsten (1995). The Church-Turing Thesis and Effective Mundane Procedures. Minds and Machines 5 (1):1-8.
Carol E. Cleland (1993). Is the Church-Turing Thesis True? Minds and Machines 3 (3):283-312.
Paolo Cotogno (2003). Hypercomputation and the Physical Church-Turing Thesis. British Journal for the Philosophy of Science 54 (2):181-223.
Tim Button (2009). Hyperloops Do Not Threaten the Notion of an Effective Procedure. Lecture Notes in Computer Science 5635:68-78.
David Israel (2002). Reflections on Gödel's and Gandy's Reflections on Turing's Thesis. Minds and Machines 12 (2):181-201.
Dina Goldin & Peter Wegner (2008). The Interactive Nature of Computing: Refuting the Strong Church–Turing Thesis. [REVIEW] Minds and Machines 18 (1):17-38.
B. Jack Copeland (2008). The Church-Turing Thesis. In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.
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 downloads14 ( #90,533 of 739,318 )
Recent downloads (6 months)2 ( #37,030 of 739,318 )
How can I increase my downloads?