Effective computation by humans and machines

Minds and Machines 12 (2):221-240 (2002)

Authors
Oron Shagrir
Hebrew University of Jerusalem
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)
Reprint years 2004
DOI 10.1023/A:1015694932257
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 46,405
Through your library

References found in this work BETA

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Is the Church-Turing Thesis True?Carol E. Cleland - 1993 - Minds and Machines 3 (3):283-312.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.
Mechanical Procedures and Mathematical Experience.Wilfried Sieg - 1994 - In Alexander George (ed.), Mathematics and Mind. Oxford University Press. pp. 71--117.

View all 21 references / Add more references

Citations of this work BETA

The Physical Church-Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.
Foundational Analyses of Computation.Yuri Gurevich - 2012 - In S. Barry Cooper (ed.), How the World Computes. pp. 264--275.

View all 6 citations / Add more citations

Similar books and articles

Parallel Machines.Andrew Boucher - 1997 - Minds and Machines 7 (4):543-551.
Kolmogorov Complexity for Possibly Infinite Computations.Verónica Becher & Santiago Figueira - 2005 - Journal of Logic, Language and Information 14 (2):133-148.
Transcending Turing Computability.B. J. Maclennan - 2003 - Minds and Machines 13 (1):3-22.
Persuasion and the Expressivity of Gestures in Humans and Machines.Isabella Poggi & Pelachaud & Catherine - 2008 - In Ipke Wachsmuth, Manuela Lenzen & Günther Knoblich (eds.), Embodied Communication in Humans and Machines. Oxford University Press.
Two Dogmas of Computationalism.Oron Shagrir - 1997 - Minds and Machines 7 (3):321-44.

Analytics

Added to PP index
2009-01-28

Total views
75 ( #116,902 of 2,286,214 )

Recent downloads (6 months)
8 ( #128,004 of 2,286,214 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature