{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T11:03:44Z","timestamp":1725879824583},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319418414"},{"type":"electronic","value":"9783319418421"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-41842-1_6","type":"book-chapter","created":{"date-parts":[[2017,2,1]],"date-time":"2017-02-01T17:01:15Z","timestamp":1485968475000},"page":"151-173","source":"Crossref","is-referenced-by-count":1,"title":["Honest Computability and Complexity"],"prefix":"10.1007","author":[{"given":"Udi","family":"Boker","sequence":"first","affiliation":[]},{"given":"Nachum","family":"Dershowitz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,1,31]]},"reference":[{"key":"6_CR1","unstructured":"Abramsky, S. (2011). Undecidability of the halting problem: A self-contained pedagogical presentation. Unpublished note."},{"key":"6_CR2","unstructured":"Boker, U. (2008). The influence of domain interpretations on computational models. Ph.D. thesis, Tel Aviv University, School of Computer Science."},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Boker, U., & Dershowitz, N. (2006). Comparing computational power. Logic Journal of the IGPL, 14, 633\u2013648. Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/ComparingComputationalPower.pdf .","DOI":"10.1093\/jigpal\/jzl003"},{"key":"6_CR4","unstructured":"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\u2013229). Berlin, Germany: Springer. Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/ArbitraryDomains.pdf ."},{"key":"6_CR5","unstructured":"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\u201347). Berlin, Germany: Springer. Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/ThreePathsToEffectiveness.pdf ."},{"key":"6_CR6","doi-asserted-by":"crossref","unstructured":"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\u201332). Springer.","DOI":"10.1007\/3-540-54458-5_46"},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"1125","DOI":"10.1090\/S0002-9939-1957-0095781-8","volume":"8","author":"M Davis","year":"1957","unstructured":"Davis, M. (1957). The definition of universal Turing machine. Proceedings of the American Mathematical Society, 8, 1125\u20131126.","journal-title":"Proceedings of the American Mathematical Society"},{"key":"6_CR8","unstructured":"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\u00fcrich, Switzerland). Electronic Proceedings in Theoretical Computer Science (pp. 59\u201371). Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/Generic.pdf ."},{"key":"6_CR9","unstructured":"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.\u00a088, pp. 72\u201378). Z\u00fcrich, Switzerland. Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/ECTT_EPTCS.pdf ."},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Dershowitz, N., & Falkovich, E. (2012) Honest universality. Special issue of the Philosophical Transactions of the Royal Society A, 370, 3340\u20133348. Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/HonestUniversality.pdf .","DOI":"10.1098\/rsta.2012.0220"},{"key":"6_CR11","unstructured":"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."},{"key":"6_CR12","doi-asserted-by":"crossref","unstructured":"Dershowitz, N., & Gurevich, Y. (2008). A natural axiomatization of computability and proof of Church\u2019s Thesis. Bulletin of Symbolic Logic, 14, 299\u2013350. Retrieved February 9, 2016, from http:\/\/nachum.org\/papers\/Church.pdf .","DOI":"10.2178\/bsl\/1231081370"},{"key":"6_CR13","unstructured":"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\u2013546). IEEE. Retrieved February 9, 2016, from http:\/\/arxiv.org\/pdf\/1501.04835v1.pdf ."},{"key":"6_CR14","volume-title":"Formal languages: Automata and structures. Lectures in Advanced Mathematics","author":"E Engeler","year":"1968","unstructured":"Engeler, E. (1968). Formal languages: Automata and structures. Lectures in Advanced Mathematics. Chicago, IL: Markham Publishing Company."},{"key":"6_CR15","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. New York, NY: W. H. Freeman."},{"key":"6_CR16","doi-asserted-by":"crossref","first-page":"77","DOI":"10.1145\/343369.343384","volume":"1","author":"Y Gurevich","year":"2000","unstructured":"Gurevich, Y. (2000). Sequential abstract state machines capture sequential algorithms. ACM Transactions on Computational Logic, 1, 77\u2013111.","journal-title":"ACM Transactions on Computational Logic"},{"key":"6_CR17","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2516.001.0001","volume-title":"Dynamic logic","author":"D Harel","year":"2000","unstructured":"Harel, D., Kozen, D., & Tiuryn, J. (2000). Dynamic logic. Cambridge, MA: MIT Press."},{"key":"6_CR18","first-page":"654","volume":"9","author":"DE Knuth","year":"1968","unstructured":"Knuth, D. E. (1968). Algorithm and program; information and data. Communications of the ACM, 9, 654.","journal-title":"Communications of the ACM"},{"key":"6_CR19","volume-title":"Computation: Finite and infinite machines","author":"ML Minsky","year":"1967","unstructured":"Minsky, M. L. (1967). Computation: Finite and infinite machines. Englewood Cliffs, NJ: Prentice-Hall."},{"key":"6_CR20","doi-asserted-by":"crossref","unstructured":"Rogers, Jr., H. (1965). On universal functions. Proceedings of the American Mathematical Society, 16, 39\u201344. Retrieved February 9, 2016, from http:\/\/www.jstor.org\/stable\/2033997 .","DOI":"10.1090\/S0002-9939-1965-0171705-4"},{"key":"6_CR21","unstructured":"Schroeppel, R. (1972). A two counter machine cannot calculate\u00a0 $$2^{{\\rm {N}}}$$ 2 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 ."},{"key":"6_CR22","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1305\/ndjfl\/1093883561","volume":"23","author":"S Shapiro","year":"1982","unstructured":"Shapiro, S. (1982). Acceptable notation. Notre Dame Journal of Formal Logic, 23, 14\u201320.","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Weihrauch, K. (1987). Computability. EATCS Monographs on Theoretical Computer Science (Vol.\u00a09). Berlin, Germany: Springer.","DOI":"10.1007\/978-3-642-69965-8"}],"container-title":["Outstanding Contributions to Logic","Martin Davis on Computability, Computational Logic, and Mathematical Foundations"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-41842-1_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,18]],"date-time":"2019-09-18T05:06:52Z","timestamp":1568783212000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-41842-1_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319418414","9783319418421"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-41842-1_6","relation":{},"ISSN":["2211-2758","2211-2766"],"issn-type":[{"type":"print","value":"2211-2758"},{"type":"electronic","value":"2211-2766"}],"subject":[],"published":{"date-parts":[[2016]]}}}