SpringerLink
Log in

Computation Paradigms in Light of Hilbert's Tenth Problem

  • Chapter
New Computational Paradigms

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 Computability Theory. The present paper is an extended version of [83].

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

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. Adleman L., Manders K.: Diophantine complexity. In: 17th Annual Symposium on Foundations of Computer Science, 81-88 (1976)

    Google Scholar 

  2. Adler A.: Some recursively unsolvable problems in analysis. Proceedings of the American Mathematical Society, 22(2):523-526 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  3. Araki, T., Kasami, T.: Some undecidable problems for Petri nets. Systems-Computers-Controls, 7(1):20-28 (1976); Japanese original: Denshi Tsushin Gakkai Ronbunshi, 59D:25-32 (1976)

    MathSciNet  Google Scholar 

  4. Baader, F., Siekmann, J. H.: Unification theory. In: Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 2, 41-125, Oxford Univ. Press, New York (1994)

    Google Scholar 

  5. Baaz, M.: Note on the existence of most general semi-unifier. Arithmetic, Proof Theory, and Computational Complexity (Prague, 1991), 20-29, Oxford Logic Guides, Vol. 23, Oxford Univ. Press, New York (1993)

    Google Scholar 

  6. Baxter, L. D.: The undecidability of the third order dyadic unification problem. Information and Control, 38(2):170-178 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  7. Bezem, M., Keuzenkamp, J., Undecidable goals for completed acyclic programs. NewGeneration Comp. 12:209-213 (1994)

    Article  MATH  Google Scholar 

  8. Blum M.: A machine-independent theory of the complexity of recursive functions. Journal of the ACM, 14(2):322-336 (1967)

    Article  MATH  MathSciNet  Google Scholar 

  9. Boas, P. van E.: Dominos are forever. In: Priese, L. (ed) Report on the 1st GTI-workshop, Reihe Theoretische Informatik, Universität-Gesamthochschule Paderborn, 75-95 (1983)

    Google Scholar 

  10. Boas, P. van E.: The convenience of tillings. Lect. Notes Pure Appl. Math. 187:331-363 (1997)

    Google Scholar 

  11. Bockmayr, A.: A note on a canonical theory with undecidable unification and matching problem. Journal of Automated Reasoning, 3(4):379-381 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  12. Burke, E. K.: The undecidability of the unification problem for nilpotent groups of class ≥ 5. J. London Math. Soc. (2). 48:52-58 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  13. Caviness B. F.: On canonical forms and simplification. Journal of the ACM, 17(2):385-396(1970)

    Article  MATH  MathSciNet  Google Scholar 

  14. Chaitin G.: Algorithmic Information Theory. Cambridge University Press, Cambridge, England (1987)

    Book  Google Scholar 

  15. Cornelissen, G., Zahidi, K.: Topology of Diophantine sets: remarks on Mazur’s conjectures. Contemp. Math., 270:253-260 (2000)

    MathSciNet  Google Scholar 

  16. Da Costa, N. C. A., Doria, F. A.: Undecidability and incompleteness in classical mechanics. Int. J. Theor. Physics, 30(8):1041-1073 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  17. Davis M.: Arithmetical problems and recursively enumerable predicates (abstract). J. Symbolic Logic, 15(1):77-78 (1950)

    Google Scholar 

  18. Davis M.: Arithmetical problems and recursively enumerable predicates. J. Symbolic Logic, 18(1):33-41 (1953)

    Article  MATH  MathSciNet  Google Scholar 

  19. Davis M.: Speed-up theorems and Diophantine equations. In Rustin R. (ed.) Courant Computer Science Symposium 7: Computational Complexity, 87-95. Algorithmics Press, New York (1973)

    Google Scholar 

  20. Davis M.: Computability and Unsolvability. Dover Publications, New York (1982)

    MATH  Google Scholar 

  21. Davis, M., Putnam, H., Robinson, J.: The decision problem for exponential Diophantine equations. Ann. Math. (2), 74:425-436 (1961). Reprinted in Feferman, S. (ed.) The collected works of Julia Robinson, Collected Works, 6, American Mathematical Society, Providence, RI (1996)

    Google Scholar 

  22. Degtyarev, A., Voronkov, A.: Simultaneous rigid E -unification is undecidable. Lecture Notes in Computer Science, 1092:178-190 (1996)

    MathSciNet  Google Scholar 

  23. Denef, J.: Hilbert’s Tenth Problem for quadratic rings. Proc. Amer. Math. Soc., 48(1):214-220 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  24. Denef, J., Lipshitz, L.: Power series solutions of algebraic differential equations. Mathematische Annalen, 267(2):213-238 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  25. Denef, J., Lipshitz, L.: Decision problems for differential equations. J. Symbolic Logic,54(3):941-950 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  26. Farmer, W. M.: Simple second-order languages for which unification is undecidable. Theoretical Computer Sci., 87:25-41 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  27. Frisco, P.: Diophantine equations and splicing: a new demonstration of the generative capacity of H systems. Lect. Notes Computer Science, 2054:43-52 (2001)

    Article  Google Scholar 

  28. Gödel, K.: Über formal unentscheidbare Sätze der Principia Mathematica und ver-wandter Systeme. I. Monatsh. Math. und Phys. 38(1):173-198 (1931)

    Article  Google Scholar 

  29. Goldfarb, W., D.: The undecidability of the second-order unification problem. Theoretical Computer Science, 13(2):225-230 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  30. Goodstein, R. L.: Hilbert’s tenth problem and the independence of recursive difference. J. London Math. Soc. (Second Series), 10(2):175-176 (1975)

    Article  MATH  MathSciNet  Google Scholar 

  31. Goodstein, R. L., Lee, R. D.: A decidable class of equations in recursive arithmetic. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 12:235-239 (1966)

    Article  MATH  MathSciNet  Google Scholar 

  32. Grigor’ev, D. Yu., Singer, M. F.: Solving ordinary differential equations in terms of series with real exponents. Trans. Amer. Math. Soc., 327(1):329-351 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  33. Grunewald, F., Segal, D.: How to solve a quadratic equation in integers. Math. Proc. Cambridge Philos. Soc., 89(1):1-5 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  34. Grunewald, F., Segal, D.: On the integer solutions of quadratic equations. Journal of the Reine Angew. Math., 569:13-45 (2004)

    MATH  MathSciNet  Google Scholar 

  35. Gurari E. M.: Decidable problems for powerful programs. J. ACM, 32(2):466-483, (1985)

    Article  MATH  MathSciNet  Google Scholar 

  36. Gurari, E. M., Ibarra, O. H., Two-way counter machines and Diophantine equations, J. ACM, 29(3):863-873 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  37. Hack, M.: The equality problem for vector addition systems is undecidable. TheoreticalComputer Science, 2(1):77-95 (1976)

    MATH  MathSciNet  Google Scholar 

  38. Harel, D., Pnueli, A., Stavi, J.: Propositional dynamic logic of nonregular programs. Journal Computer and System Sciences, 26(2):222-243 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  39. Head, T.: Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behavior. Bull. Math. Biology, 49 (1987)

    Google Scholar 

  40. Hickey, T., Mudambi, S.: Global compilation of Prolog. J. Logic Programming, 7:193-230(1989)

    Article  Google Scholar 

  41. Hilbert, D.: Mathematische Probleme. Vortrag, gehalten auf dem internationalen Math-ematiker Kongress zu Paris 1900. Nachr. K. Ges. Wiss., Göttingen, Math.-Phys.Kl. 253-297 (1900). See also Hilbert, D.: Gesammelte Abhandlungen, Springer, Berlin 3 (1935) (Reprinted: Chelsea, New York (1965)). English translation: Bull. Amer. Math. Soc., 8:437-479 (1901-1902); reprinted in: Browder (ed.) Mathematical Developments arising from Hilbert Problems, Proceedings of Symposia in Pure Mathematics 28, Ame-rican Mathematical Society, 1-34 (1976)

    Google Scholar 

  42. Hodgson, B. R., Kent, C. F.: A normal form for arithmetical representation of NP -sets. J. Computer System Sci., 27(3):378-388 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  43. Howell, R. R., Rosier, L. E., Huynh, D. T., Yen H.-Ch.: Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states. The-oretical Computer Science, 46(2-3):107-140 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  44. Ibarra, O. H., Leininger, B. S.: The complexity of the equivalence problem for straight-line programs. Conference Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, Los Angeles, California, 273-280 (1980)

    Google Scholar 

  45. Ibarra, O. H., Leininger, B. S.: Straight-line programs with one input variable. SIAM Journal on Computing, 11(1):1-14 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  46. Ibarra, O. H., Leininger, B. S.: On the simplification and equivalence problems for straight-line programs, J. ACM, 30(3):641-656 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  47. Ibarra, O. H., Rosier L. e.: The equivalence problem and correctness formulas for a simple class of programs. Lecture Notes Comp. Sci., 176:330-338 (1984)

    Article  MathSciNet  Google Scholar 

  48. Jiménez, Á. R., Jiménez, M. J. P.: Generation of Diophantine sets by computing P systems with external output. Lect. Notes Comp. Sci., 2509:176-190 (2002)

    Article  Google Scholar 

  49. Jones, J. P.: Recursive undecidability—an exposition.Amer. Mathem. Monthly, 81(7):724-738 (1974)

    Article  MATH  Google Scholar 

  50. Jones, J. P.: Some undecidable determined games. International Journal of Game Theory, 11(2):63-70 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  51. Jones, J. P.: Universal Diophantine equation. J. Symbolic Logic 47:549-571 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  52. Jones, J. P.: Computational complexity of winning strategies in two players polynomial games (in Russian). Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matem-aticheskogo Instituta im. V. A. Steklova AN SSSR (LOMI), 192:69-73 (1991)

    Google Scholar 

  53. Jones, J. P., Fraenkel, A.S.: Complexities of winning strategies in Diophantine games. J. Complexity, 11:435-455 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  54. Jones, J. P., Matijasevič , Ju. V.: Exponential Diophantine representation of recursively enumerable sets. In: Stern, J. (ed) Proceedings of the Herbrand Symposium: Logic Colloquium’81, Studies in Logic and the Foundations of Mathematics, 107:159-177, North Holland, Amsterdam (1982)

    Google Scholar 

  55. Jones, J. P., Matijasevič Ju. V., : A new representation for the symmetric binomial coef-ficient and its applications. Annales Sci. Mathém. du Québec, 6(1):81-97 (1982)

    MATH  Google Scholar 

  56. Jones, J. P., Matijasevič , Ju. V.: Direct translation of register machines into exponen-tial Diophantine equations. In: Priese, L. (ed) Report on the 1st GTI-workshop, Reihe Theoretische Informatik, Universität-Gesamthochschule Paderborn, 117-130 (1983)

    Google Scholar 

  57. Jones, J. P., Matijasevič Ju. V., : Register machine proof of the theorem on exponen-tial Diophantine representation of enumerable sets. J. Symbolic Logic, 49(3):818-829 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  58. Jones, J. P., Matijasevič Ju. V.: Proof of recursive unsolvability of Hilbert’s tenth prob-lem. Amer. Math. Monthly, 98(8):689-709 (1991)

    Article  MATH  MathSciNet  Google Scholar 

  59. Kasami, T., Nobuki, T.: Equivalence problem of programs without loops. Systems-Computers-Controls, 2(4):83-84 (1971); Japanese original: Denshi Tsushin Gakkai Ronbunshi, 54-C:657-658 (1971)

    MathSciNet  Google Scholar 

  60. Kent, C. F., Hodgson, B. R.: An arithmetical characterization of NP. Theor. Computer Science, 21(3):255-267 (1982)

    Article  MATH  MathSciNet  Google Scholar 

  61. Kosovskiĭ, N. K.: On Diophantine representations of the sequence of solutions of Pell equation. Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematich-eskogo Instituta im. V. A. Steklova AN SSSR (LOMI), 20:49-59 (1971)

    Google Scholar 

  62. Kreisel, G., Davis, M., Putnam, H., Robinson, J.: The decision problem for exponential Diophantine equations. Mathem. Reviews, 24: #A3061, 573 (1962)

    Google Scholar 

  63. Kummer, M. :The complexity of recursion theoretic games. Trans. Amer. Math. Soc., 358:1, 59-86 (electronic) (2006)

    Article  MATH  MathSciNet  Google Scholar 

  64. Lachlan, A. H.: On some games which are relevant to the theory of recursively enumerable sets. Ann. Math. (2), 91:291-310 (1970)

    Article  MathSciNet  Google Scholar 

  65. Lambek, J.: How to program an infinite abacus. Canad. Math. Bull., 4:295-302 (1961)

    MathSciNet  Google Scholar 

  66. Levitz, H.: Decidability of some problem pertaining to base 2 exponential Diophan-tine equations, Zeitschrift Mathematische Logik Grundlagen Mathematik, 31(2):109-115 (1985)

    Article  MathSciNet  Google Scholar 

  67. Li, C., Dang, Z., Ibarra, O. H., Yen, H.-Ch.: Signaling P systems and verifications prob-lem. Lecture Notes Comput. Sci., 3580:1462-1473 (2005)

    Article  MathSciNet  Google Scholar 

  68. Lipmaa, H.: On Diophantine complexity and statistical zero-knowledge arguments. Lecture Notes Computer Science, 2894:398-415 (2003)

    MathSciNet  Google Scholar 

  69. Livesey, M., Siekmann, J., Szabó, P., and Unvericht, E.: Unification problems for com-binations of associativity, commutativity, distributivity and idempotence axioms. In: William H. J., Jr. (ed), Proceedings of the Fourth Workshop on Automated Deduction, 175-184, Austin, Texas, (1979)

    Google Scholar 

  70. Makanin, G. S.: The problem of solvability of equations in a free semigroup (in Russian). Math. Sbornik, 103:147-236 (1977); English transl. in: Math. USSR Sbornik, Math. USSR Sbornik, 32(2):129-198 (1977)

    Google Scholar 

  71. Manders, K. L., Adleman, L.: NP-complete decision problems for binary quadratics.J. Comput. System Sci., 16(2):168-184 (1978)

    Article  MATH  MathSciNet  Google Scholar 

  72. Markov, A. A.: Impossibility of certain algorithms in the theory of associative systems (in Russian), Dokl. Akad. Nauk SSSR, 55(7):587-590 (1947). Translated in: Compte rendus de l’Académie des Sciences de l’U.R.S.S., 55:583-586 (1947)

    Google Scholar 

  73. Martin-Löf, P. Notes on Constructive Mathematics. Almqvist & Wikseil, Stockholm (1970)

    Google Scholar 

  74. Matiyasevich, Yu. V.: The connection between Hilbert’s tenth problem and systems of equations between words and lengths (in Russian), Zap. nauch. Seminar. Leningr. otd. Mat. in-ta AN SSSR, 8:132-144 (1968). English translation: Seminars in Mathematics, V. A. Steklov Mathematical Institute, 8:61-67 (1970)

    Google Scholar 

  75. Matiyasevich, Yu. V.: Enumerable sets are Diophantine (in Russian). Dokl. AN SSSR, 191 (2):278-282 (1970); Translated in: Soviet Math. Doklady, 11(2):354-358

    Google Scholar 

  76. Matiyasevich, Yu. V.: Existence of noneffectivizable estimates in the theory of expo-nential Diophantine equations (in Russian). Zapiski Nauchnykh Seminarov Leningrad-skogo 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)

    Google Scholar 

  77. Matiyasevich, Yu. V.: A new proof of the theorem on exponential Diophantine represen-tation of enumerable sets (in Russian). 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)

    Google Scholar 

  78. Matiyasevich, Yu. V.: Some purely mathematical results inspired by mathematical logic, In: Proceedings of Fifth International Congress on Logic, Methodology and Philosophy of science, London, Ontario, 1975, Reidel, Dordrecht, 121-127 (1977)

    Google Scholar 

  79. Matiyasevich, Yu. V.: Algorithmic unsolvability of exponential Diophantine equations in three unknowns (in Russian), In: Markov, A.A., Homich V.I. (eds), Studies in the Theory of Algorithms and Mathematical Logic, Computing Center Russian Academy Sci., Moscow, 69-78 (1979); Translated in Selecta Mathematica Sovietica, 3:223-232 (1983/1984)

    Google Scholar 

  80. Matiyasevich, Yu. V.: Desyataya Problema Gilberta. Fizmatlit, Moscow, (1993). English translation: Hilbert’s Tenth Problem. MIT Press, Cambridge, MA (1993). French trans-lation: Le dixième Problème de Hilbert, Masson, Paris Milan Barselone (1995). URL: http://logic.pdmi.ras.ru/∼yumat/H10Pbook,

  81. Matiyasevich, Yu.: A direct method for simulating partial recursive functions by Dio-phantine equations. Annals Pure Appl. Logic, 67:325-348 (1994)

    MATH  MathSciNet  Google Scholar 

  82. Matiyasevich, Yu.: Hilbert’s tenth problem: what was done and what is to be done Contemporary mathematics, 270:1-47, (2000)

    MathSciNet  Google Scholar 

  83. Matiyasevich, Yu.: Hilbert’s tenth problem and paradigms of computation, Lecture Notes Computer Science, 3526:310-321 (2005)

    Google Scholar 

  84. Matiyasevich, Yu.: Diophantine flavor of Kolmogorov complexity. Trans. Inst. Informat-ics and Automation Problems National Acad. Sciences of Armenia, 27:111-122 (2006)

    Google Scholar 

  85. Matiyasevich, Yu.: Word Equations, Fibonacci Numbers, and Hilbert’s Tenth Problem. URL: http://logic.pdmi.ras.ru/∼yumat/Journal/jcontord.htm

  86. Matijasevič Yu. , Robinson, J.: Reduction of an arbitrary Diophantine equation to one in 13 unknowns. Acta Arithmetica, 27:521-553 (1975)

    MATH  MathSciNet  Google Scholar 

  87. Mayr E. W., Meyer, A. R.: The complexity of the finite containment problem for Petri nets. Journal of the ACM, 28(3):561-576 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  88. Mazur, B.: The topology of rational points. Experimental Mathematics, 1(1):35-45 (1992)

    MATH  MathSciNet  Google Scholar 

  89. Mazur, B.: Questions of decidability and undesidability in Number Theory. J. Symbolic Logic, 59(2):353-371 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  90. Melzak, Z. A.: An informal arithmetical approach to computability and computation. Canad. Math. Bull., 4:279-294 (1961)

    MATH  MathSciNet  Google Scholar 

  91. Minsky, M. L.: Recursive unsolvability of Post’s problem of “tag” and other topics in the theory of Turing machines. Ann. of Math. (2), 74:437-455 (1961)

    Article  MathSciNet  Google Scholar 

  92. Minsky, M. L.: Computation: Finite and Infinite Machines. Prentice Hall, EnglewoodCliffs, NJ (1967)

    MATH  Google Scholar 

  93. Ord, T., Kieu, T. D.: On the existence of a new family of Diophantine equations for Ω .Fundam. Inform. 56(3):273-284 (2003)

    MATH  MathSciNet  Google Scholar 

  94. Pappas, P.: A Diophantine problem for Laurent polynomial rings. Proceedings of the American Mathematical Society, 93(4):713-718 (1985)

    Article  MATH  MathSciNet  Google Scholar 

  95. Paun, Gh.: From cells to (silicon) computers, and back. This volume, pages 343-371

    Google Scholar 

  96. Pheidas, Th., Zahidi, K.: Undecidability of existential theories of rings and fields: a survey. Contemp. Math., 270:49-105 (2000)

    MathSciNet  Google Scholar 

  97. Pheidas, Th.: An effort to prove that the existential theory of Q is undecidable. Contemp. Math., 270:237-252 (2000)

    MathSciNet  Google Scholar 

  98. Pollett, Ch.: On the bounded version of Hilbert’s tenth problem. Arch. Math. Logic,42(5):469-488 (2003)

    MATH  MathSciNet  Google Scholar 

  99. Poonen, B.: Hilbert’s tenth problem and Mazur’s conjecture for large subrings of Q. J. Amer. Math. Soc., 16(4):981-990 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  100. 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).

    Google Scholar 

  101. Post, E. L.: Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc., 50:284-316 (1944); reprinted in: The Collected Works of  E. L. Post, Davis, M. (ed), Birkhäuser, Boston (1994).

    Google Scholar 

  102. Post, E. L.: Recursive unsolvability of a problem of Thue. J. Symbolic Logic, 12:1-11(1947); reprinted in: The Collected Works of E. L. Post, Davis, M. (ed), Birkhäuser,Boston (1994).

    Google Scholar 

  103. Prasad, K.: Computability and randomness of Nash equilibrium in infinite games. J. Mathem. Economics, 20(5):429-442 (1991).

    Article  MATH  Google Scholar 

  104. Reif, J. H., Lewis, H. R.: Efficient symbolic analysis of programs, J. Computer SystemSci., 32(3):280-314 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  105. Rabin M. O.: Effective computability of winning strategies. In: Dresher, M., Tucker, A. W., Wolff, P. (eds), Contributions to the Theory of Games. Volume III, Annals of Mathematics Studies, 39:147-157 Princeton University Press, Princeton, NJ (1957)

    Google Scholar 

  106. Reutenauer, Ch., Aspect Math’ematiques des R’eseaux de Pétri. Masson, Paris Milan Barcelone Mexico (1989); Engl. transl: The Mathematics of Petri Nets, Prentice-Hall, Englewood Cliffs, NJ (1990)

    Google Scholar 

  107. D. Richardson, Some undecidable problems involving elementary functions of a real variable. J. Symbolic Logic, 33(4):514-520 (1968)

    Article  MATH  MathSciNet  Google Scholar 

  108. Robinson, J. A.: A machine-oriented logic based on the resolution principle, J. Assoc. Comput. Mach. 12:23-41 (1965)

    MATH  MathSciNet  Google Scholar 

  109. Shepherdson, J. C., Sturgis, H. E.: Computability of recursive functions, J. ACM 10(2):217-255 (1963)

    Article  MATH  MathSciNet  Google Scholar 

  110. Shirayev, D. V.: Undecidability of some decision problems for straight-line programs (inRussian), Kibernetika, 1:63-66 (1989)

    Google Scholar 

  111. Shlapentokh, A.: Hilbert’s tenth problem over number fields, a survey. Contemp. Math., 270:107-143 (2000)

    MathSciNet  Google Scholar 

  112. Shlapentokh, A.: A ring version of Mazur’s conjecture on top[ology of rational points.Int. Math. Res. Notes, 2003(7):411-423 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  113. Shlapentokh, A.: Hilbert’s Tenth Problem. Diophantine Classes and Extensions to Global Fields. Cambridge Univ. Press, Cambridge, England (2007)

    MATH  Google Scholar 

  114. Siegel, C. L.: Zur Theorie der quadratischen Formen. Nachrichten Akademie Wissenschaften in Göttingen. II. Mathematisch-Physikalische Klasse, 3:21-46 (1972)

    Google Scholar 

  115. Siekmann, J. H., Unification theory. J. Symbolic Comp., 7:207-274 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  116. Singer, M. F.: The model theory of ordered differential fields. J. Symbolic Logic, 43:1, 82-91 (1978)

    Google Scholar 

  117. Skolem, Th.: Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschliesslich Zahlenvariablen, Fundamenta Mathematicae, 23:150-161 (1934)

    Google Scholar 

  118. Stallworth D. T., Roush, F. W.: An undecidable property of definite integrals. Proceedings of the American Mathematical Society, 125(7):2147-2148 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  119. Sun, Zh.-W.: Reduction of unknowns in Diophantine representations. Science in China (Scientia Sinica) Ser. A., 35(3):257-269 (1992)

    MATH  Google Scholar 

  120. Thue, A.: Problem über Veränderungen von Zeichenreihen nach gegebenen Regeln. Vid. Skr. I. Mat.-natur. Kl., 10:493-524 (1914). Reprinted in: Thue, A.: Selected Mathematical Papers, Oslo (1977)

    Google Scholar 

  121. Tiden, E., Arnborg, S.: Unification problems with one-sided distributivity, J. Symbolic Computation, 3:183-202 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  122. Tseitin, G.S.: A method of presenting the theory of algorithms and enumerable sets (in Russian). Trudy Matematicheskogo instituta im. V. A. Steklova 72 (1964) 69-99. English translation in: Am. Math. Soc. Translat., II. Ser. 99:1-39 (1972)

    Google Scholar 

  123. Tung, Sh. P. The bound of Skolem functions and their applications. Information and Computation, 120:149-154 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  124. Sivaramakrishnan Rajagopalan, S.: Average case intractability of matrix and Diophantine problems. Proceedings Twenty-Fourth Annual ACM Symposium Theory Comput., Victoria, British Columbia, Canada, 632-642 (1992)

    Google Scholar 

  125. Vinogradov, A. K., Kosovskiĭ, N. K.: A hierarchy of Diophantine representations of primitive recursive predicates (in Russian). Vychislitel’naya tekhnika i voprosy kiber-netiki, no. 12, 99-107. Lenigradskiĭ Gosudarstvennyĭ Universitet, Leningrad (1975)

    Google Scholar 

  126. Wolfson, O.: Parallel evaluation of Datalog programs by load sharing. J. Logic Program-ming, 12:369-393 (1992)

    Article  MathSciNet  Google Scholar 

  127. Yukna, S.: Arithmetical representations of classes of computational complexity (in Russian). Matematicheskaya logika i eë primeneniya, no. 2, 92-107, Institut Matematiki i Kibernetiki Akademii Nauk Litovskoĭ SSR, Vil’nyus (1982)

    Google Scholar 

  128. Yukna, S.:. On arithmetization of computations (in Russian). Matematicheskaya logika i eë primeneniya, no. 3, 117-125, Institut Matematiki i Kibernetiki Akademii Nauk Litovskoĭ SSR, Vil’nyus (1983)

    Google Scholar 

  129. URL: http://logic.pdmi.ras.ru/Hilbert10

Download references

Author information

Authors and Affiliations

  1. Steklov Institute of Mathematics, 191023, St. Petersburg, Russia

    Yuri Matiyasevich

Authors
  1. Yuri Matiyasevich
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. University of Leeds, LS2 9JT, Leeds, UK

    S. Barry Cooper

  2. University of Amsterdam, Plantage Muidergracht 24, 1018 TV, Amsterdam, Netherlands

    Benedikt Löwe

  3. Università di Siena, Pian dei Mantellini 44, 53100, Siena, Italy

    Andrea Sorbi

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer Science+Business Media, LLC

About this chapter

Cite this chapter

Matiyasevich, Y. (2008). Computation Paradigms in Light of Hilbert's Tenth Problem. In: Cooper, S.B., Löwe, B., Sorbi, A. (eds) New Computational Paradigms. Springer, New York, NY. https://doi.org/10.1007/978-0-387-68546-5_4

Download citation

  • DOI: https://doi.org/10.1007/978-0-387-68546-5_4

  • Publisher Name: Springer, New York, NY

  • Print ISBN: 978-0-387-36033-1

  • Online ISBN: 978-0-387-68546-5

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation