======================================================================== @TEXT-file{ author = "David M. Jones", version = "1.00", date = "27 October 1993", time = "15:22:04 EDT", filename = "contents.txt", address = "MIT Laboratory for Computer Science Room NE43-316 545 Technology Square Cambridge, MA 02139 USA", telephone = "(617) 253-5936", FAX = "(617) 253-3480", checksum = "56564 140 533 5030", email = "dmjones@theory.lcs.mit.edu", codetable = "ISO/ASCII", keywords = "", supported = "yes", docstring = "This is the table of contents for {\em Hilbert's Tenth Problem} by Yuri Matijasevich (MIT Press, 1993). This and related files are available via anonymous ftp from theory.lcs.mit.edu in the directory pub/hilbert10. See the file ``README'' in that directory for a list and description of what is available. The checksum field above contains a CRC-16 checksum as the first value, followed by the equivalent of the standard UNIX wc (word count) utility output of lines, words, and characters. This is produced by Robert Solovay's checksum utility.", } ======================================================================== HILBERT'S TENTH PROBLEM Yuri V. Matiyasevich The MIT Press Cambridge, Massachusetts London, England CONTENTS Series Foreword A Note on the Translation (by Martin Davis) Foreword (by Martin Davis) Preface to the English Edition Preface 1 PRINCIPAL DEFINITIONS 1.1 Diophantine equations as a decision problem 1.2 Systems of Diophantine equations 1.3 Solutions in natural numbers 1.4 Families of Diophantine equations 1.5 Logical terminology 1.6 Some simple examples of Diophantine sets, properties, relations, and functions 2 EXPONENTIATION IS DIOPHANTINE 2.1 Special second-order recurrent sequences 2.2 The special recurrent sequences are Diophantine (basic ideas) 2.3 The special recurrent sequences are Diophantine (proof) 2.4 Exponentiation is Diophantine 2.5 Exponential Diophantine equations 3 DIOPHANTINE CODING 3.1 Cantor numbering 3.2 G\"odel coding 3.3 Positional coding 3.4 Binomial coefficients, the factorial, and the prime numbers are Diophantine 3.5 Comparison of tuples 3.6 Extensions of functions to tuples 4 UNIVERSAL DIOPHANTINE EQUATIONS 4.1 Basic definitions 4.2 Coding equations 4.3 Coding possible solutions 4.4 Computing the values of polynomials 4.5 Universal Diophantine equations 4.6 Diophantine sets with non-Diophantine complements 5 HILBERT'S TENTH PROBLEM IS UNSOLVABLE 5.1 Turing machines 5.2 Composition of machines 5.3 Basis machines 5.4 Turing machines can recognize Diophantine sets 5.5 Diophantine simulation of Turing machines 5.6 Hilbert's Tenth Problem is undecidable by Turing machines 5.7 Church's Thesis 6 BOUNDED UNIVERSAL QUANTIFIERS 6.1 First construction: Turing machines 6.2 Second construction: G\"odel coding 6.3 Third construction: summation 6.4 Connections between Hilbert's Eighth and Tenth Problems 6.5 Yet another universal equation 6.6 Yet another Diophantine set with non-Diophantine complement 7 DECISION PROBLEMS IN NUMBER THEORY 7.1 The number of solutions of Diophantine equations 7.2 Non-effectivizable estimates in the theory of exponential Diophantine equations 7.3 Gaussian integer counterpart of Hilbert's Tenth Problem 7.4 Homogeneous equations and rational solutions 8 DIOPHANTINE COMPLEXITY 8.1 Principal definitions 8.2 A bound for the number of unknowns in exponential Diophantine representations 9 DECISION PROBLEMS IN CALCULUS 9.1 Diophantine real numbers 9.2 Equations, inequalities, and identities in real variables 9.3 Systems of ordinary differential equations 9.4 Integrability 10 OTHER APPLICATIONS OF DIOPHANTINE REPRESENTATIONS 10.1 Diophantine games 10.2 Generalized knights on a multidimensional chessboard APPENDIX 1 The Four Squares Theorem 2 Chinese Remainder Theorem 3 Kummer's Theorem 4 Summation of a generalized geometric progression Hints to the Exercises Bibliography List of Notation Name Index Subject Index