Skip to main content
SpringerLink
Log in

Is There a Nonrecursive Decidable Equational Theory?

  • Published:
Minds and Machines Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Arbib, M. (1968), The Algebraic Theory of Machines, Languages, and Semigroups, New York: Academic Press.

    Google Scholar 

  • Blum, L., Cucker, F., Shub, M., and Smale, S. (1998), Complexity and Real Computation, NewYork: Springer.

    Google Scholar 

  • Blum, L., Shub, M., and Smale, S. (1989), 'On a Theory of Computation and Complexity over the Real Numbers: NP-Completeness, Recursive Functions and Universal Machines',' Bulletin Amer. Math. Soc. 21, pp. 1–46.

    Google Scholar 

  • Borges, J. L. (1962), 'The Library of Babel',' in Labyrinths; Selected Stories & Other Writings, New York: New Directions.

    Google Scholar 

  • Bringsjord, S. (1998), 'The Narrational Case Against Church's Thesis',' to appear in S. Bringsjord, and M. Zenzen, Super-Minds: A Defense of Uncomputable Cognition, Dordrecht: Kluwer Academic. Available on the WWW at: http://www.rpi.edu/~brings/SELPAP/CT/ct/ dated 1998.

    Google Scholar 

  • Brown, J. (2000), Minds, Machines, and the Multiverse, New York: Simon and Schuster.

    Google Scholar 

  • Carroll, R. T. (2001), http://skepdic.com/akashic.html (online Skeptic's Dictionary).

  • Chaitin, G. J. (1999), The Unknowable, New York: Springer.

    Google Scholar 

  • Cleland, C. E. (1993), 'Is the Church-Turing Thesis True?',' Minds and Machines 3, pp. 283–312.

    Google Scholar 

  • Cleland, C. E. (1995), 'Effective Procedures and Computable Functions',' Minds and Machines 5, pp. 9–23.

    Google Scholar 

  • Cleland, C. E. (2001a), 'Recipes, Algorithms, and Programs',' Minds and Machines 11, pp. 219–237.

    Google Scholar 

  • Cleland, C. E. (2001b), 'Effective Procedures and Causal Processes' (preprint).

  • Cleland, C. E. (2001c), personal communication.

  • Copeland, B. J. (1996), 'What is Computation?',' Synthese 108, pp. 335–359.

    Google Scholar 

  • Copeland, B. J. (1997), 'The Church-Turing Thesis',' in J. Perry and E. Zalta, eds., The Stanford Encyclopaedia of Philosophy, World Wide Web: Stanford University, http://plato.stanford.edu/.

    Google Scholar 

  • Copeland, B. J. (1998), 'Even Turing Machines Can Compute Uncomputable Functions',' in C Calude, J. Casti and M. Dinneen, eds., Unconventional Models of Computation, London: Springer, pp. 150–164.

    Google Scholar 

  • Copeland, B. J. and Proudfoot, D. (1999), 'Alan Turing's Forgotten Ideas in Computer Science',' Scientific American 280, pp. 99–103.

    Google Scholar 

  • Davis, M. (1958), Computability and Unsolvability, New York: McGraw-Hill.

    Google Scholar 

  • Ehrenfeucht, A., Geiser, J., Gordon, C. E., and deJongh, D. H. J. (1971), 'A Semantics for Non-Iterated Local Observation I' (preprint).

  • Esenin-Volpin, A. S. (1961), 'Le programme ultra-intuitioniste des fondements des Mathématiques',' in Infinitistic Methods: Proc. Symp. Found. Math., Warsaw 1959, Oxford: Pergamon Press, pp. 201–233.

    Google Scholar 

  • Yessenin-Volpin, A. S. (1970), 'The Ultra-Intuitionistic Criticism and the Antitraditional Program for Foundations of Mathematics',' in A. Kino, J. Myhill, and R. E. Vesley, eds., Intuitionism and Proof Theory, proceedings of the summer conference at Buffalo, N.Y., 1968, Amsterdam: North-Holland, pp. 3–52.

    Google Scholar 

  • of_babel.html (online illustration for Borges, 1962).

  • Geiser, J. R. (1974), 'A Formalization of Essenin-Volpin's Proof Theoretical Studies by Means of Nonstandard Analysis', Journal of Symbolic Logic 39, pp. 81–87.

    Google Scholar 

  • Hawkins, J. D. and Lewis, A. (2000), 'Infinite Time Turing Machines',' Journal of Symbolic Logic 65, pp. 567–604.

    Google Scholar 

  • Henkin, L., Monk, J. D., and Tarski, A. (1971), Cylindric Algebras, Part I, Amsterdam: North-Holland.

    Google Scholar 

  • Heyting, A., ed., (1959), Constructivity in Mathematics, Amsterdam: North-Holland.

  • Isles, D. (1992), 'What Evidence is There That 2∧65536 is a Natural Number?',' Notre Dame Journal of Formal Logic 33, pp. 465–480.

    Google Scholar 

  • Kalmár, L. (1959), 'An Argument Against the Plausibility of Church's Thesis',' in Heyting, A., ed., Constructivity in Mathematics, Amsterdam: North Holland, pp. 72–80.

    Google Scholar 

  • Kanerva, P. (1988), Sparse Distributed Memory, Cambridge MA: MIT Press.

    Google Scholar 

  • Lambek, J. (1997), 'Programs, Grammars, Arguments',' Bulletin of Symbolic Logic 3, pp. 312–328.

    Google Scholar 

  • Lewis, H. R. and Papadimitriou, C. H. (1998), Elements of the Theory of Computation (2nd edition), Upper Saddle River NJ: Prentice-Hall.

    Google Scholar 

  • McKenzie, R. N., McNulty, G. F., and Taylor, W. F. (1987), Algebras, Varieties, and Lattices, Monterey: Wadsworth.

    Google Scholar 

  • Mal'cev, A. I. (1966), 'Tozhdestvennye Sootnosheniya na Mnogoobraziyakh Kvazigrupp, (translated by Benjamin Wells under the title 'Identical Relations in Varieties of Quasigroups' in Mal'tsev (1971)), Mat. Sbornik (nov. ser.) 69(111) 3, pp. 3–9.

    Google Scholar 

  • Mal'tsev, A. I. (1969), 'Identical relations on varieties of quasigroups',' Amer.Math. Soc. Translations (2)82 (1969), pp. 225–235. Translation of Mal'cev (1966) by K. A. Hirsch.

    Google Scholar 

  • Mal'tsev, A. I. (1971), The Metamathematics of Algebraic Systems—Collected Papers: 1936–1967, (newly translated, edited, and annotated by Benjamin Wells), Amsterdam: North-Holland.

    Google Scholar 

  • Mandelbrot, B. B. (1983), 'On the Quadratic Mapping z ? z 2 ? µ for Complex µ and z: the Fractal Structure of its M Set, and Scaling',' Physica 7D, pp. 224–239.

    Google Scholar 

  • Mandelbrot, B. B. (1988), The Fractal Geometry of Nature, New York: WH Freeman.

    Google Scholar 

  • Meseguer, J. and Goguen, J. A. (1985), 'Initiality, Induction, and Computability',' in Nivat and Reynolds, Algebraic Methods in Semantics, New York: Cambridge University Press.

    Google Scholar 

  • Peitgen, H.-O., Jürgens, H., and Saupe, D. (1992), Chaos and Fractals: New Frontiers of Science, New York: Springer.

    Google Scholar 

  • Péter, R. (1959), 'Rekursivität und Konstruktivität',' in Heyting, A., ed., Constructivity in Mathematics, Amsterdam: North Holland.

    Google Scholar 

  • Pkhakadze, Sh. S. (1984), An Example of an Intuitively Computable and Everywhere Defined Function and Church's Thesis, Tbilisi State University, Georgia, USSR.

    Google Scholar 

  • Post, E. (1943), 'Formal Reductions of the General Combinatorial Problem',' Amer. J. Math. 65, pp. 197–215.

    Google Scholar 

  • PPP (2001), http://www.fmag.unict.it/PolPhil/LvovWarsaw/LvovWarsaw.html#anchor97717 Raman, V. V. (2001), personal communication.

  • Rogers, H. (1967), The Theory of Recursive Functions and Effective Computability, New York: McGraw-Hill.

    Google Scholar 

  • Shapiro, S. C. (1998), 'A Procedural Solution to the Unexpected Hanging and Sorites Paradoxes',' Mind 107, pp. 751–761.

    Google Scholar 

  • Sieg,W. (1997), 'Step by Recursive Step: Church's Analysis of Effective Computability',' Bulletin of Symbolic Logic 3, pp. 154–180.

    Google Scholar 

  • Siegelman, H. T. (1999), Neural Networks and Analog Computation: Beyond the Turing Limit, Boston: Birkhäuser.

    Google Scholar 

  • Soare, R. I. (1996), 'Computability and Recursion',' Bulletin of Symbolic Logic 2, pp. 284–321.

    Google Scholar 

  • Sullivan, M.A. (1997), http://www.bluffton.edu/~sullivanm/kresgec/intwhole.jpg (online image of MIT Kresge Chapel altar screen).

  • Tarski, A. (1941), Introduction to Logic and to the Methodology of Deductive Sciences, enlarged and revised edition and translation of O logice matematycznej i metodzie dedukcyjnej (1936), New York: Oxford University Press; 4th edition, edited by Jan Tarski (1994), New York: Oxford University Press.

    Google Scholar 

  • Tarski, A. (1951), A Decision Method for Elementary Algebra and Geometry (2nd edition), Berkeley: University of California.

    Google Scholar 

  • Tarski, A. (1983), Logic, Semantics, Metamathematics: Papers from 1923 to 1938, (2nd edition), Indianapolis: Hackett.

    Google Scholar 

  • Tarski, A., Mostowski, A., and Robinson, R. M. (1968), Undecidable Theories, (2nd edition), Amsterdam: North-Holland.

    Google Scholar 

  • 13a.html (online image of the Pala d'Oro altarpiece, Basilica of San Marco, Venice).

  • Wells, B. (1981), 'A Finitely Based, Pseudorecursive Variety of Semigroups',' Abstracts Amer. Math.Soc. 2, pp. 287–288.

    Google Scholar 

  • Wells, B. (1983), Pseudorecursive Varieties and Their Implications for Word Problems, doctoral dissertation, University of California, Berkeley.

    Google Scholar 

  • Wells, B. (1986), 'Pseudorecursiveness: Implications for Decidability and Computability',' Journal of Symbolic Logic 51, pp. 858–859.

    Google Scholar 

  • Wells, B. (1987), 'Uniform problems without uniform solutions',' paper delivered at Algebras, Lattices and Logic, Asilomar, July 1987.

  • Wells, B. (1995), 'Simple Recursively-based Pseudorecursive Varieties of Semigroups',' Bulletin of Symbolic Logic 1, p. 371.

    Google Scholar 

  • Wells, B. (1996), 'Pseudorecursive Varieties of Semigroups—I',' Int. J. of Algebra and Computation 6, pp. 457–510.

    Google Scholar 

  • Wells, B. (2000), 'Pseudorecursiveness and Hypercomputation: a Legacy of Nonuniformity',' paper delivered at the Hypercomputation Conference, University of London, May 2000.

  • Wells, B. (2002a), 'Abstracting, Extending, and Specializing Pseudorecursiveness',' for proceedings of the Tarski Centenary Conference, Warsaw, May–June 2001 (in preparation).

  • Wells, B. (2002b), 'Pseudorecursiveness and Hypercomputation: a Legacy of Lacking Uniformity',' for special issue of Minds and Machines collecting papers from the Hypercomputation Conference, London, May 2000 (in preparation).

  • Woleński, J. (1989), Logic and Philosophy in the Lvov-Warsaw School, Dordrecht, Boston: Kluwer Academic Publishers.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departments of Mathematics and Computer Science, University of San Francisco, San Francisco, CA, USA

    Benjamin Wells

Authors
  1. Benjamin Wells
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wells, B. Is There a Nonrecursive Decidable Equational Theory?. Minds and Machines 12, 301–324 (2002). https://doi.org/10.1023/A:1015659418145

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1015659418145

Search

Navigation