David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Jack Alan Reynolds
Learn more about PhilPapers
Minds and Machines 12 (2):301-324 (2002)
The Church-Turing Thesis (CTT) is often paraphrased as ``every computable function is computable by means of a Turing machine.'' The author has constructed a family of equational theories that are not Turing-decidable, that is, given one of the theories, no Turing machine can recognize whether an arbitrary equation is in the theory or not. But the theory is called pseudorecursive because it has the additional property that when attention is limited to equations with a bounded number of variables, one obtains, for each number of variables, a fragment of the theory that is indeed Turing-decidable. In a 1982 conversation, Alfred Tarski announced that he believed the theory to be decidable, despite this contradicting CTT. The article gives the background for this proclamation, considers alternate interpretations, and sets the stage for further research.
|Keywords||Church-Turing Thesis effective procedure pseudorecursive theory quotidian procedure Turing decidability|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
No references found.
Citations of this work BETA
Benjamin Wells (2004). Applying, Extending, and Specializing Pseudorecursiveness. Annals of Pure and Applied Logic 126 (1-3):225-254.
Similar books and articles
Guido Gherardi (2011). Alan Turing and the Foundations of Computable Analysis. Bulletin of Symbolic Logic 17 (3):394-430.
P. D. Welch (2000). Eventually Infinite Time Turing Machine Degrees: Infinite Time Decidable Reals. Journal of Symbolic Logic 65 (3):1193-1203.
Robert I. Soare (1996). Computability and Recursion. Bulletin of Symbolic Logic 2 (3):284-321.
Douglas Cenzer & Andre Nies (2001). Initial Segments of the Lattice of Π01 Classes. Journal of Symbolic Logic 66 (4):1749 - 1765.
Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare (2004). Bounding Prime Models. Journal of Symbolic Logic 69 (4):1117 - 1142.
Gualtiero Piccinini (2007). Computationalism, the Church–Turing Thesis, and the Church–Turing Fallacy. Synthese 154 (1):97-120.
Samuel Coskey & Joel David Hamkins (2010). Infinite Time Decidable Equivalence Relation Theory. Notre Dame Journal of Formal Logic 52 (2):203-228.
Michael Rescorla (2007). Church's Thesis and the Conceptual Analysis of Computability. Notre Dame Journal of Formal Logic 48 (2):253-280.
Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
Barbara F. Csima (2004). Degree Spectra of Prime Models. Journal of Symbolic Logic 69 (2):430 - 442.
Added to index2009-01-28
Total downloads9 ( #168,390 of 1,140,007 )
Recent downloads (6 months)2 ( #92,708 of 1,140,007 )
How can I increase my downloads?