The Church-Turing Thesis over Arbitrary Domains | SpringerLink
Skip to main content
Springer Nature Link
Log in

The Church-Turing Thesis over Arbitrary Domains

  • Chapter
Pillars of Computer Science

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4800))

  • 1042 Accesses

Abstract

The Church-Turing Thesis has been the subject of many variations and interpretations over the years. Specifically, there are versions that refer only to functions over the natural numbers (as Church and Kleene did), while others refer to functions over arbitrary domains (as Turing intended). Our purpose is to formalize and analyze the thesis when referring to functions over arbitrary domains.

First, we must handle the issue of domain representation. We show that, prima facie, the thesis is not well defined for arbitrary domains, since the choice of representation of the domain might have a non-trivial influence. We overcome this problem in two steps: (1) phrasing the thesis for entire computational models, rather than for a single function; and (2) proving a “completeness” property of the recursive functions and Turing machines with respect to domain representations.

In the second part, we propose an axiomatization of an “effective model of computation” over an arbitrary countable domain. This axiomatization is based on Gurevich’s postulates for sequential algorithms. A proof is provided showing that all models satisfying these axioms, regardless of underlying data structure, are of equivalent computational power to, or weaker than, Turing machines.

This research was supported by the Israel Science Foundation (grant no. 250/05) and was carried out in partial fulfillment of the requirements for the Ph.D. degree of the first author.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Blass, A., Gurevich, Y.: Background, Reserve, and Gandy Machines. In: Clote, P.G., Schwichtenberg, H. (eds.) CSL 2000. LNCS, vol. 1862, Springer, Heidelberg (2000)

    Google Scholar 

  2. Boker, U., Dershowitz, N.: How to Compare the Power of Computational Models. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol. 3526, pp. 54–64. Springer, Heidelberg (2005)

    Google Scholar 

  3. Boker, U., Dershowitz, N.: Abstract effective models. In: Fernández, M., Mackie, I. (eds.) New Developments in Computational Models: Proceedings of the First International Workshop on Developments in Computational Models (DCM 2005), Lisbon, Portugal (July 2005), Electronic Notes in Theoretical Computer Science, 135(3), 15–23 (2006)

    Google Scholar 

  4. Boker, U., Dershowitz, N.: Comparing computational power. Logic Journal of the IGPL 14(5), 633–648 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  5. Church, A.: An unsolvable problem of elementary number theory. American Journal of Mathematics 58, 345–363 (1936)

    Article  MATH  MathSciNet  Google Scholar 

  6. Cutland, N.: Computability: An Introduction to Recursive Function Theory. Cambridge University Press, Cambridge (1980)

    MATH  Google Scholar 

  7. Davis, M.: Why Gödel didn’t have Church’s Thesis. Information and Control 54(1/2), 3–24 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  8. Dershowitz, N., Gurevich, Y.: A natural axiomatization of Church’s Thesis. Bulletin of the ASL (to appear), available as Technical report MSR-TR-2007-85, Microsoft Research, Redmond, WA (July 2007)

    Google Scholar 

  9. Froehlich, A., Shepherdson, J.: Effective procedures in field theory. Philosophical Transactions of the Royal Society of London 248, 407–432 (1956)

    Article  Google Scholar 

  10. Gandy, R.: Church’s thesis and principles for mechanisms. In: Barwise, J., et al. (eds.) The Kleene Symposium. Studies in Logic and The Foundations of Mathematics, vol. 101, pp. 123–148. North-Holland, Amsterdam (1980)

    Google Scholar 

  11. Gurevich, Y.: Sequential abstract state machines capture sequential algorithms. ACM Transactions on Computational Logic 1, 77–111 (2000)

    Article  MathSciNet  Google Scholar 

  12. Jones, N.D.: Computability and Complexity from a Programming Perspective. The MIT Press, Cambridge, MA (1997)

    MATH  Google Scholar 

  13. Kleene, S.C.: Recursive predicates and quantifiers. Transactions of the American Mathematical Society 53(1), 41–73 (1943)

    Article  MATH  MathSciNet  Google Scholar 

  14. Knuth, D.E.: The Art of Computer Programming. Fundamental Algorithms, vol. 1. Addison-Wesley, Reading, MA (1968)

    MATH  Google Scholar 

  15. Lambert Jr., W.M.: A notion of effectiveness in arbitrary structures. The Journal of Symbolic Logic 33(4), 577–602 (1968)

    Article  MATH  MathSciNet  Google Scholar 

  16. Mal’cev, A.: Constructive algebras I. Russian Mathematical Surveys 16, 77–129 (1961)

    Article  MathSciNet  Google Scholar 

  17. Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice-Hall, Englewood Cliffs, NJ (1967)

    MATH  Google Scholar 

  18. Montague, R.: Towards a general theory of computability. Synthese 12(4), 429–438 (1960)

    Article  MathSciNet  Google Scholar 

  19. Myhill, J.: Some philosophical implications of mathematical logic. Three classes of ideas 6(2), 165–198 (1952)

    Google Scholar 

  20. Rabin, M.O.: Computable algebra, general theory and theory of computable fields. Transactions of the American Mathematical Society 95(2), 341–360 (1960)

    Article  MATH  MathSciNet  Google Scholar 

  21. Rescorla, M.: Church’s thesis and the conceptual analysis of computability. Notre Dame Journal of Formal Logic 48(2), 253–280 (2007)

    Article  MathSciNet  Google Scholar 

  22. Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1966)

    Google Scholar 

  23. Schroeppel, R.: A two counter machine cannot calculate 2N. Technical report, Massachusetts Institute of Technology, Artificial Intelligence Laboratory (1972) (viewed November 28, 2007), ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-257.pdf

  24. Shapiro, S.: Acceptable notation. Notre Dame Journal of Formal Logic 23(1), 14–20 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  25. Shoenfield, J.R.: Recursion Theory. Lecture Notes in Logic, vol. 1. Springer, Heidelberg (1991)

    Google Scholar 

  26. Sieg, W.: Church without dogma—Axioms for computability. In: Löwe, B., Sorbi, A., Cooper, S.B. (eds.) New Computational Paradigms: Changing Conceptions of What is Computable, pp. 18–44. Springer, Heidelberg (2007)

    Google Scholar 

  27. Sieg, W.: Computability: Emergence and analysis of a mathematical notion. In: Irvine, A. (ed.) Handbook of the Philosophy of Mathematics (to appear)

    Google Scholar 

  28. Sieg, W., Byrnes, J.: An abstract model for parallel computations: Gandy’s thesis. The Monist 82(1), 150–164 (1999)

    Google Scholar 

  29. Sommerhalder, R., van Westrhenen, S.C.: The Theory of Computability: Programs, Machines, Effectiveness and Feasibility. Addison-Wesley, Workingham, England (1988)

    Google Scholar 

  30. Trakhtenbrot, B.A.: Comparing the Church and Turing approaches: Two prophetical messages. In: Herken, R. (ed.) The Universal Turing Machine: A half-century survey, pp. 603–630. Oxford University Press, Oxford (1988)

    Google Scholar 

  31. Turing, A.M.: On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society 42, 230–265 (1936), Corrections in vol. 43, pp. 544–546 (1937), Reprinted in Davis, M. (ed.), The Undecidable, Raven Press, Hewlett, NY (1965)

    Google Scholar 

  32. Turing, A.M.: Systems of logic based on ordinals. Proceedings of the London Mathematical Society 45, 161–228 (1939)

    Article  MATH  Google Scholar 

  33. Weihrauch, K.: Computability. EATCS Monographs on Theoretical Computer Science, vol. 9. Springer, Berlin (1987)

    Google Scholar 

  34. Weihrauch, K. (ed.): Computable Analysis – An introduction. Springer, Berlin (2000)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science, Tel Aviv University, Ramat Aviv, 69978, Israel

    Udi Boker & Nachum Dershowitz

Authors
  1. Udi Boker
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Nachum Dershowitz
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Arnon Avron Nachum Dershowitz Alexander Rabinovich

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Boker, U., Dershowitz, N. (2008). The Church-Turing Thesis over Arbitrary Domains. In: Avron, A., Dershowitz, N., Rabinovich, A. (eds) Pillars of Computer Science. Lecture Notes in Computer Science, vol 4800. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78127-1_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78127-1_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78126-4

  • Online ISBN: 978-3-540-78127-1

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics