Is there a nonrecursive decidable equational theory?

Minds and Machines 12 (2):301-324 (2002)
Abstract
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)
Reprint years 2004
DOI 10.1023/A:1015659418145
Options
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history
Request removal from index
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 25,662
Through your library
References found in this work BETA

No references found.

Add more references

Citations of this work BETA
Applying, Extending, and Specializing Pseudorecursiveness.Benjamin Wells - 2004 - Annals of Pure and Applied Logic 126 (1-3):225-254.

Add more citations

Similar books and articles
Alan Turing and the Foundations of Computable Analysis.Guido Gherardi - 2011 - Bulletin of Symbolic Logic 17 (3):394-430.
Computability and Recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Initial Segments of the Lattice of Π01 Classes.Douglas Cenzer & Andre Nies - 2001 - Journal of Symbolic Logic 66 (4):1749 - 1765.
Bounding Prime Models.Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight & Robert I. Soare - 2004 - Journal of Symbolic Logic 69 (4):1117 - 1142.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2010 - Notre Dame Journal of Formal Logic 52 (2):203-228.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - Journal of Symbolic Logic 71 (2):399 - 424.
Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.

Monthly downloads

Added to index

2009-01-28

Total downloads

16 ( #287,447 of 2,143,787 )

Recent downloads (6 months)

1 ( #387,161 of 2,143,787 )

How can I increase my downloads?

My notes
Sign in to use this feature


Discussion
Order:
There  are no threads in this forum
Nothing in this forum yet.

Other forums