Effective computation by humans and machines

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.

Download options


    Upload a copy of this work     Papers currently archived: 72,805

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library


Added to PP

85 (#140,281)

6 months
1 (#386,031)

Historical graph of downloads
How can I increase my downloads?

References found in this work

On Computable Numbers, with an Application to the Entscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
An Unsolvable Problem of Elementary Number Theory.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (2):73-74.
A Note on the Entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.
The Church-Turing Thesis.B. Jack Copeland - 2008 - In Edward N. Zalta (ed.), The Stanford Encyclopedia of Philosophy. The Metaphysics Research Lab, Stanford University.

View all 23 references / Add more references

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.