Abstract
We raise some issues posed by the use of representations for data structures. A nefarious representation can turn the incomputable into computable, the non-recursively-enumerable into regular, and the intractable into trivial. To overcome such problems, we propose criteria for “honesty” of implementation. In particular, we demand that inputs to functions and queries to decision procedures be specified as constructor terms.
Goldstein: And what causes you to say that?
Davis: Honesty.
—Martin Davis: An Interview Conducted by Andrew Goldstein
(IEEE History Center, July 18, 1991)
For Martin—scientist, scholar, and thinker.
This author’s research benefited from a fellowship at the Institut d’Études Avancées de Paris (France), with the financial support of the French state, managed by the French National Research Agency’s “Investissements d’avenir” program (ANR-11-LABX-0027-01 Labex RFIEA+).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Allowing different representations for input and output, as in “A more general notion of simulation is obtained if we let drop the requirement that \(\smash {\mathfrak {R}^{\scriptscriptstyle (1)}}\) and \(\smash {\mathfrak {R}^{\scriptscriptstyle (2)}}\) have the same input and output sets.... \(\smash {\mathfrak {R}^{\scriptscriptstyle (1)}}\) can be weakly simulated on \(\smash {\mathfrak {R}^{\scriptscriptstyle (2)}}\) if there exist such \(\mathscr {E}\) and \(\mathscr {D}\) with the property that for each program \(\pi _1\) for \(\mathfrak {R}^{\scriptscriptstyle (1)}\) there exists a program \(\pi _2\) on \(\smash {\mathfrak {R}^{\scriptscriptstyle (2)}}\) such that \(\smash {\mathscr {D}\mathfrak {R}^{\scriptscriptstyle (2)}_{\pi _2} \mathscr {E}=\mathfrak {R}^{\scriptscriptstyle (1)}_{\pi _1}}\)” [14, p. 21], can lead—if one is not careful—to the same kinds of problems we will encounter in Sect. 6.9.
- 2.
Unlike the development in [4], where effectiveness of an algorithm was at issue, here we are not insisting that the generators form a free term algebra (a Herbrand universe): more than one term may designate the same abstract element.
- 3.
- 4.
References
Abramsky, S. (2011). Undecidability of the halting problem: A self-contained pedagogical presentation. Unpublished note.
Boker, U. (2008). The influence of domain interpretations on computational models. Ph.D. thesis, Tel Aviv University, School of Computer Science.
Boker, U., & Dershowitz, N. (2006). Comparing computational power. Logic Journal of the IGPL, 14, 633–648. Retrieved February 9, 2016, from http://nachum.org/papers/ComparingComputationalPower.pdf.
Boker, U., & Dershowitz, N. (2008). The Church-Turing Thesis over arbitrary domains. In: A. Avron, N. Dershowitz and A. Rabinovich (Eds.), Pillars of computer science, essays dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday. Lecture Notes in Computer Science (Vol. 4800, pp. 199–229). Berlin, Germany: Springer. Retrieved February 9, 2016, from http://nachum.org/papers/ArbitraryDomains.pdf.
Boker, U., & Dershowitz, N. (2010). Three paths to effectiveness. In A. Blass, N. Dershowitz and W. Reisig (Eds.), Fields of logic and computation: Essays dedicated to Yuri Gurevich on the occasion of his 70th birthday. Lecture Notes in Computer Science (Vol. 6300, pp. 36–47). Berlin, Germany: Springer. Retrieved February 9, 2016, from http://nachum.org/papers/ThreePathsToEffectiveness.pdf.
Cai, J. -Y. (1991). Computations over infinite groups. In L. Budach (Ed.), Proceedings of the 8th International Symposium on Fundamentals of Computation Theory (FCT), Gosen, Germany. Lecture Notes in Computer Science (Vol. 529, pp. 22–32). Springer.
Davis, M. (1957). The definition of universal Turing machine. Proceedings of the American Mathematical Society, 8, 1125–1126.
Dershowitz, N. (2012). The generic model of computation. In Proceedings of the Seventh International Workshop on Developments in Computational Models (DCM 2011, July 2012, Zürich, Switzerland). Electronic Proceedings in Theoretical Computer Science (pp. 59–71). Retrieved February 9, 2016, from http://nachum.org/papers/Generic.pdf.
Dershowitz, N., & Falkovich, E. (2011). A formalization and proof of the Extended Church-Turing Thesis. In Proceedings of the Seventh International Workshop on Developments in Computational Models (DCM 2011). Electronic Proceedings in Theoretical Computer Science (Vol. 88, pp. 72–78). Zürich, Switzerland. Retrieved February 9, 2016, from http://nachum.org/papers/ECTT_EPTCS.pdf.
Dershowitz, N., & Falkovich, E. (2012) Honest universality. Special issue of the Philosophical Transactions of the Royal Society A, 370, 3340–3348. Retrieved February 9, 2016, from http://nachum.org/papers/HonestUniversality.pdf.
Dershowitz, N., & Falkovich, E. (2017). The invariance thesis. Logical Methods in Computer Science. Retrieved February 9, 2016, from http://nachum.org/papers/InvarianceThesis.pdf. To appear.
Dershowitz, N., & Gurevich, Y. (2008). A natural axiomatization of computability and proof of Church’s Thesis. Bulletin of Symbolic Logic, 14, 299–350. Retrieved February 9, 2016, from http://nachum.org/papers/Church.pdf.
Endrullis, J., Grabmayer, C., & Hendriks, D. (2015). Regularity preserving but not reflecting encodings. In Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Kyoto, Japan (pp. 535–546). IEEE. Retrieved February 9, 2016, from http://arxiv.org/pdf/1501.04835v1.pdf.
Engeler, E. (1968). Formal languages: Automata and structures. Lectures in Advanced Mathematics. Chicago, IL: Markham Publishing Company.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York, NY: W. H. Freeman.
Gurevich, Y. (2000). Sequential abstract state machines capture sequential algorithms. ACM Transactions on Computational Logic, 1, 77–111.
Harel, D., Kozen, D., & Tiuryn, J. (2000). Dynamic logic. Cambridge, MA: MIT Press.
Knuth, D. E. (1968). Algorithm and program; information and data. Communications of the ACM, 9, 654.
Minsky, M. L. (1967). Computation: Finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall.
Rogers, Jr., H. (1965). On universal functions. Proceedings of the American Mathematical Society, 16, 39–44. Retrieved February 9, 2016, from http://www.jstor.org/stable/2033997.
Schroeppel, R. (1972). A two counter machine cannot calculate \(2^{{\rm {N}}}\). Artificial Intelligence Memo #257, Massachusetts Institute of Technology, A. I. Laboratory. Retrieved February 9, 2016, from ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-257.pdf.
Shapiro, S. (1982). Acceptable notation. Notre Dame Journal of Formal Logic, 23, 14–20.
Weihrauch, K. (1987). Computability. EATCS Monographs on Theoretical Computer Science (Vol. 9). Berlin, Germany: Springer.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this chapter
Cite this chapter
Boker, U., Dershowitz, N. (2016). Honest Computability and Complexity. In: Omodeo, E., Policriti, A. (eds) Martin Davis on Computability, Computational Logic, and Mathematical Foundations. Outstanding Contributions to Logic, vol 10. Springer, Cham. https://doi.org/10.1007/978-3-319-41842-1_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-41842-1_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-41841-4
Online ISBN: 978-3-319-41842-1
eBook Packages: Religion and PhilosophyPhilosophy and Religion (R0)