Abstract
This is a survey of a century long history of interplay between Hilbert’s tenth problem (about solvability of Diophantine equations) and different notions and ideas from the Computability Theory.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Adleman, L., Manders, K.: Computational complexity of decision procedures for polynomials. In: 16th Annual Symposium on Foundations of Computer Science, pp. 169–177 (1975)
Adleman, L., Manders, K.: Diophantine complexity. In: 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, October 25-26, 1976, pp. 81–88. IEEE, Los Alamitos (1976)
Blum, M.: A machine-independent theory of the complexity of recursive functions. Journal of the ACM 14(2), 322–336 (1967)
Chaitin, G.: Algorithmic Information Theory. Cambridge University Press, Cambridge (1987)
Davis, M.: Arithmetical problems and recursively enumerable predicates (abstract). Journal of Symbolic Logic 15(1), 77–78 (1950)
Davis, M.: Arithmetical problems and recursively enumerable predicates. J. Symbolic Logic 18(1), 33–41 (1953)
Davis, M.: Speed-up theorems and Diophantine equations. In: Rustin, R. (ed.) Courant Computer Science Symposium 7: Computational Complexity, pp. 87–95. Algorithmics Press, New York (1973)
Davis, M.: Computability and Unsolvability. Dover Publications, New York (1982)
Davis, M., Putnam, H., Robinson, J.: The decision problem for exponential Diophantine equations. Ann. Math. 74(2), 425–436 (1961) (Reprinted in The collected works of Julia Robinson, Feferman, S. (ed.) Collected Works, 6, 1996, xliv+p. 338. American Mathematical Society, Providence, RI, ISBN: 0-8218-0575-4)
Gödel, K.: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme. I. Monatsh. Math. und Phys. 38(1), 173–198 (1931)
Hack, M.: The equality problem for vector addition systems is undecidable. Theoretical Computer Science 2(1), 77–95 (1976)
Hilbert, D.: Mathematische Probleme. Vortrag, gehalten auf dem internationalen Mathematiker Kongress zu Paris 1900. Nachr. K. Ges. Wiss., Göttingen, Math.-Phys.Kl., 253–297 (1900); See also Hilbert, D.: Gesammelte Abhandlungen, vol. 3, p. 310. Springer, Berlin (1935) (Reprinted: New York : Chelsea (1965)); English translation: Bull. Amer. Math. Soc., 8, 437–479 (1901-1902); Reprinted in : Mathematical Developments arising from Hilbert problems. In: Browder, (ed.) Proceedings of symposia in pure mathematics, vol. 28, pp.1–34. American Mathematical Society (1976)
Hodgson, B.R., Kent, C.F.: A normal form for arithmetical representation of NP-sets. Journal of Computer and System Sciences 27(3), 378–388 (1983)
Jones, J.P., Matijasevič, J.V.: Exponential Diophantine representation of recursively enumerable sets. In: Stern, J. (ed.) Proceedings of the Herbrand Symposium: Logic Colloquium 1981. Studies in Logic and the Foundations of Mathematics, vol. 107, pp. 159–177. North Holland, Amsterdam (1982)
Jones, J.P., Matijasevič, J.V.: A new representation for the symmetric binomial coefficient and its applications. Les Annales des Sciences Mathématiques du Québec 6(1), 81–97 (1982)
Jones, J.P., Matijasevich, Y.V.: Direct translation of register machines into exponential Diophantine equations. In: Priese, L. (ed.) Report on the 1st GTI-workshop, vol. 13, pp. 117–130, Reihe Theoretische Informatik, Universität-Gesamthochschule Paderborn (1983)
Jones, J.P., Matijasevič, Y.V.: Register machine proof of the theorem on exponential Diophantine representation of enumerable sets. J. Symbolic Logic 49(3), 818–829 (1984)
Jones, J.P., Matijasevič, Y.V.: Proof of recursive unsolvability of Hilbert’s tenth problem. Amer. Math. Monthly 98(8), 689–709 (1991)
Kent, C.F., Hodgsont, B.R.: An arithmetical characterization of NP. Theoretical Computer Science 21(3), 255–267 (1982)
Ord, T., Kieu, T.D.: On the existence of a new family of Diophantine equations for Ω. Fundam. Inform. 56(3), 273–284 (2003)
Kreisel, G.: Davis, Martin; Putnam, Hilary; Robinson, Julia. The decision problem for exponential Diophantine equations. Mathematical Reviews 24#A3061, 573 (1962)
Lambek, J.: How to program an infinite abacus. Canad. Math. Bull. 4, 295–302 (1961)
Lipmaa, H.: On Diophantine Complexity and Statistical Zero-Knowledge Arguments. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol. 2894, pp. 398–415. Springer, Heidelberg (2003)
Manders, K.L., Adleman, L.: NP-complete decision problems for binary quadratics. J.Comput. System Sci. 16(2), 168–184 (1978)
Martin-Löf, P.: Notes on Constructive Mathematics. Almqvist & Wikseil, Stockholm (1970)
Matiyasevich, Y.V.: Diofantovost’ perechislimykh mnozhestv. Dokl. AN SSSR 191(2), 278–282 (1970); Translated in: Soviet Math. Doklady 11(2), 354-358 (1970)
Matiyasevich, Y.V.: Sushchestvovanie neèffektiviziruemykh otsenok v teorii èksponentsial’no diofantovykh uravneniĭ. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (LOMI) 40, 77–93 (1974); Translated in: Journal of Soviet Mathematics 8(3), 299–311 (1977)
Matiyasevich, Y.: Novoe dokazatel’stvo teoremy ob èksponentsial´no diofantovom predstavlenii perechislimykh predikatov. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR (LOMI) 60, 75–92 (1976); Translated in: Journal of Soviet Mathematics 14(5), 1475–1486 (1980)
Matiyasevich, Y.: Desyataya Problema Gilberta, Moscow, Fizmatlit (1993); English translation: Hilbert’s tenth problem. MIT Press, Cambridge (1993); French translation: Le dixième problème de Hilbert, Masson (1995), http://logic.pdmi.ras.ru/~yumat/H10Pbook , mirrored at, http://www.informatik.uni-stuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook
Matiysevich, Y.: A direct method for simulating partial recursive functions by Diophantine equations. Annals Pure Appl. Logic 67, 325–348 (1994)
Matiyasevich, Y.: Hilbert’s tenth problem: what was done and what is to be done. Contemporary mathematics 270, 1–47 (2000)
Melzak, Z.A.: An informal arithmetical approach to computability and computation. Canad. Math. Bull. 4, 279–294 (1961)
Minsky, M.L.: Recursive unsolvability of Post’s problem of “tag” and other topics in the theory of Turing machines. Ann. of Math. 74(2), 437–455 (1961)
Minsky, M.L.: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs (1967)
Pollett, C.: On the Bounded Version of Hilbert’s Tenth Problem. Arch. Math. Logic 42(5), 469–488 (2003)
Post, E.L.: Formal reductions of the general combinatorial decision problem. Amer. J. Math. 65, 197–215 (1943); Reprinted in “The collected works of E.L. Post”, Davis, M. (ed.) Birkhäuser, Boston (1994)
Shepherdson, J.C., Sturgis, H.E.: Computability of recursive functions. J. ACM 10(2), 217–255 (1963)
Tseitin, G.S.: Odin sposob izlozheniya teorii algorifmov i perechislimykh mnozhestv. Trudy Matematicheskogo instituta im. V. A. Steklova 72, 69–99 (1964); English translation in Proceedings of the Steklov Institute of Mathematics
van Emde Boas, P.: Dominos are forever. In: Priese, L. (ed.) Report on the 1st GTI-workshop, vol. 13, pp. 75–95, Reihe Theoretische Informatik, Universität-Gesamthochschule Paderborn (1983)
Vinogradov, A.K., Kosovskiĭ, N.K.: Ierarkhiya diofantovykh predstavleniĭ primitivno rekursivnykh predikatov. In: Vychislitel’naya tekhnika i voprosy kibernetiki, vol. 12, pp. 99–107. Lenigradskiĭ Gosudarstvennyĭ Universitet, Leningrad (1975)
Yukna, S.: Arifmeticheskie predstavleniya klassov mashinnoĭ slozhnosti. In: Matematicheskaya logika i eë primeneniya, vol. 2, pp. 92–107. Institut Matematiki i Kibernetiki Akademii Nauk Litovskoĭ SSR, Vil’nyus (1982)
Yukna, S.: Ob arifmetizatsii vychisleniĭ. In: Matematicheskaya logika i eë primeneniya, vol. 3, pp. 117–125. Institut Matematiki i Kibernetiki Akademii Nauk Litovskoĭ SSR, Vil’nyus (1983)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Matiyasevich, Y. (2005). Hilbert’s Tenth Problem and Paradigms of Computation. In: Cooper, S.B., Löwe, B., Torenvliet, L. (eds) New Computational Paradigms. CiE 2005. Lecture Notes in Computer Science, vol 3526. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11494645_39
Download citation
DOI: https://doi.org/10.1007/11494645_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26179-7
Online ISBN: 978-3-540-32266-5
eBook Packages: Computer ScienceComputer Science (R0)