Hilbert's tenth problem

This book presents the full, self-contained negative solution of Hilbert's 10th problem. At the 1900 International Congress of Mathematicians, held that year in Paris, the German mathematician David Hilbert put forth a list of 23 unsolved problems that he saw as being the greatest challenges for twentieth-century mathematics. Hilbert's 10th problem, to find a method (what we now call an algorithm) for deciding whether a Diophantine equation has an integral solution, was solved by Yuri Matiyasevich in 1970. Proving the undecidability of Hilbert's 10th problem is clearly one of the great mathematical results of the century.This book presents the full, self-contained negative solution of Hilbert's 10th problem. In addition it contains a number of diverse, often striking applications of the technique developed for that solution (scattered previously in journals), describes the many improvements and modifications of the original proof - since the problem was "unsolved" 20 years ago, and adds several new, previously unpublished proofs. Included are numerous exercises that range in difficulty from the elementary to small research problems, open questions, and unsolved problems. Each chapter concludes with a commentary providing a historical view of its contents. And an extensive bibliography contains references to all of the main publications directed to the negative solution of Hilbert's 10th problem as well as the majority of the publications dealing with applications of the solution. Intended for young mathematicians, Hilbert's 10th Problem requires only a modest mathematical background. A few less well known number-theoretical results are presented in the appendixes. No knowledge of recursion theory is presupposed. All necessary notions are introduced and defined in the book, making it suitable for the first acquaintance with this fascinating subject. Cover......Page 1 Title......Page 4 Contents......Page 6 Series Foreword......Page 10 A Note on the Translation......Page 12 Foreword......Page 14 Preface to the English Edition......Page 19 Preface......Page 20 1.1 Diophantine equations as a decision problem......Page 27 1.2 Systems of Diophantine equations......Page 28 1.3 Solutions in natural numbers......Page 30 1.4 Families of Diophantine equations......Page 32 1.5 Logical terminology......Page 35 1.6 Some simple examples of Diophantine sets, properties, relations, and functions......Page 38 2.1 Special second-order recurrent sequences......Page 45 2.2 The special recurrent sequences are Diophantine (basic ideas)......Page 47 2.3 The special recurrent sequences are Diophantine (proof)......Page 52 2.4 Exponentiation is Diophantine......Page 57 2.5 Exponential Diophantine equations......Page 59 3.1 Cantor numbering......Page 67 3.2 Godel coding......Page 68 3.3 Positional coding......Page 70 3.4 Binomial coefficients, the factorial, and the prime numbers are Diophantine......Page 71 3.5 Comparison of tuples......Page 73 3.6 Extensions of functions to tuples......Page 75 4.1 Basic definitions......Page 83 4.2 Coding equations......Page 85 4.3 Coding possible solutions......Page 87 4.4 Computing the values of polynomials......Page 88 4.5 Universal Diophantine equations......Page 90 4.6 Diophantine sets with non-Diophantine complements......Page 91 5.1 Turing machines......Page 97 5.2 Composition of machines......Page 99 5.3 Basis machines......Page 101 5.4 Turing machines can recognize Diophantine sets......Page 109 5.5 Diophantine simulation of Turing machines......Page 111 5.6 Hilbert's Tenth Problem is undecidable by Turing machines......Page 118 5.7 Church's Thesis......Page 120 6.1 First construction: Turing machines......Page 129 6.2 Second construction: Godel coding......Page 130 6.3 Third construction: summation......Page 135 6.4 Connections between Hilbert's Eighth and Tenth Problems......Page 142 6.5 Yet another universal equation......Page 148 6.6 Yet another Diophantine set with non-Diophantine complement......Page 149 7.1 The number of solutions of Diophantine equations......Page 155 7.2 Non-effectivizable estimates in the theory of exponential Diophantine equations......Page 156 7.3 Gaussian integer counterpart of Hilbert's Tenth Problem......Page 164 7.4 Homogeneous equations and rational solutions......Page 172 8.1 Principal definitions......Page 179 8.2 A bound for the number of unknowns in exponential Diophantine representations......Page 182 9.1 Diophantine real numbers......Page 191 9.2 Equations, inequalities, and identities in real variables......Page 194 9.3 Systems of ordinary differential equations......Page 200 9.4 Integrability......Page 203 10.1 Diophantine games......Page 207 10.2 Generalized knights on a multidimensional chessboard......Page 210 1 The Four Squares Theorem......Page 225 2 Chinese Remainder Theorem......Page 226 3 Kummer's Theorem......Page 227 4 Summation of a generalized geometric progression......Page 228 Hints to the Exercises......Page 231 Bibliography......Page 247 List of Notation......Page 283 Name Index......Page 285 Subject Index......Page 289 Annotation. At the 1900 International Congress of Mathematicians, held that year in Paris, the German mathematician David Hilbert put forth a list of 23 unsolved problems that he saw as being the greatest challenges for twentieth-century mathematics. Hilbert's 10th problem, to find a method (what we now call an algorithm) for deciding whether a Diophantine equation has an integral solution, was solved by Yuri Matiyasevich in 1970. Proving the undecidability of Hilbert's 10th problem is clearly one of the great mathematical results of the century. This book presents the full, self-contained negative solution of Hilbert's 10th problem. In addition it contains a number of diverse, often striking applications of the technique developed for that solution (scattered previously in journals), describes the many improvements and modifications of the original proof - since the problem was "unsolved" 20 years ago, and adds several new, previously unpublished proofs. Included are numerous exercises that range in difficulty from the elementary to small research problems, open questions, and unsolved problems. Each chapter concludes with a commentary providing a historical view of its contents. And an extensive bibliography contains references to all of the main publications directed to the negative solution of Hilbert's 10th problem as well as the majority of the publications dealing with applications of the solution. Intended for young mathematicians, Hilbert's 10th Problem requires only a modest mathematical background. A few less well known number-theoretical results are presented in the appendixes. No knowledge of recursion theory is presupposed. All necessary notions are introduced and defined in the book, making it suitable for the first acquaintance with this fascinating subject. Yuri Matiyasevich is Head of the Laboratory of Mathematical Logic, Steklov Institute of Mathematics, Russian Academy of Sciences, Saint Petersburg

At the 1900 International Congress of Mathematicians, held that year in Paris, the German mathematician David Hilbert put forth a list of 23 unsolved problems that he saw as being the greatest challenges for twentieth-century mathematics. Hilbert's 10th problem, to find a method (what we now call an algorithm) for deciding whether a Diophantine equation has an integral solution, was solved by Yuri Matiyasevich in 1970. Proving the undecidability of Hilbert's 10th problem is clearly one of the great mathematical results of the century.This book presents the full,self-contained negative solution of Hilbert's 10th problem. In addition it contains a number of diverse, often striking applications of the technique developed for that solution (scattered previously in journals), describes the many improvements and modifications of the original proof -since the problem was "unsolved" 20 years ago, and adds several new, previously unpublished proofs.Included are numerous exercises that range in difficulty from the elementary to small research problems, open questions,and unsolved problems. Each chapter concludes with a commentary providing a historical view of its contents. And an extensive bibliography contains references to all of the main publications directed to the negative solution of Hilbert's 10th problem as well as the majority of the publications dealing with applications of the solution.Intended for young mathematicians, Hilbert's 10th Problem requires only a modest mathematical background. A few less well known number-theoretical results are presented in the appendixes. No knowledge of recursion theory is presupposed. All necessary notions are introduced and defined in the book, making it suitable for the first acquaintance with this fascinating subject.Yuri Matiyasevich is Head of the Laboratory of Mathematical Logic, Steklov Institute of Mathematics, Russian Academy of Sciences,Saint Petersburg.

Presents a solution to the 10th problem (to find a method for deciding if a Diophantine equation has an integral solution). The work contains applications of the technique developed for that solution and describes the improvements of the original proof since the problem was "unsolved" 20 years ago Let us recall that a Diophantine equation is an equation of the form D(x1, . . . , xm) = 0, (1.1.1) where D is a polynomial with integer coefficients.