Is there a nonrecursive decidable equational theory?

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)
DOI 10.1023/A:1015659418145
 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
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 15,904
External links
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.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

14 ( #180,241 of 1,725,430 )

Recent downloads (6 months)

4 ( #167,246 of 1,725,430 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.