Deviant encodings and Turing’s analysis of computability

Abstract

Turing’s analysis of computability has recently been challenged; it is claimed that it is circular to analyse the intuitive concept of numerical computability in terms of the Turing machine. This claim threatens the view, canonical in mathematics and cognitive science, that the concept of a systematic procedure or algorithm is to be explicated by reference to the capacities of Turing machines. We defend Turing’s analysis against the challenge of ‘deviant encodings’.Keywords: Systematic procedure; Turing machine; Church–Turing thesis; Deviant encoding; Acceptable encoding; Turing’s analysis of computability; Turing’s Notational Thesis.

Download options

PhilArchive



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

External links

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

Through your library

Analytics

Added to PP
2010-09-14

Downloads
64 (#182,492)

6 months
1 (#386,499)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Diane Proudfoot
University of Canterbury

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.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Acceptable Notation.Stewart Shapiro - 1982 - Notre Dame Journal of Formal Logic 23 (1):14-20.

View all 6 references / Add more references

Similar books and articles

Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Accelerating Turing Machines.B. Jack Copeland - 2002 - Minds and Machines 12 (2):281-300.
Alan Turing and the Foundations of Computable Analysis.Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (3):394-430.
Infinite Time Turing Machines.Joel David Hamkins - 2002 - Minds and Machines 12 (4):567-604.
Infinite Time Turing Machines.Joel David Hamkins & Andy Lewis - 2000 - Journal of Symbolic Logic 65 (2):567-604.
Turing's Golden: How Well Turing's Work Stands Today.Justin Leiber - 2006 - Philosophical Psychology 19 (1):13-46.
Hypercomputation.B. Jack Copeland - 2002 - Minds and Machines 12 (4):461-502.
Effective Computation by Humans and Machines.Shagrir Oron - 2002 - Minds and Machines 12 (2):221-240.
Omnibus Review. [REVIEW]John Crossley - 1991 - Journal of Symbolic Logic 56 (3):1089-1090.
[Omnibus Review].John N. Crossley - 1991 - Journal of Symbolic Logic 56 (3):1089-1090.