HILBERT'S 10TH PROBLEM

Le Monde En Tique

Commandez cet ouvrage

Ouvrage 0-262-13295-8 : HILBERT'S 10TH PROBLEM
In 1900, 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 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, 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.
Yuri Matiyasevich is Head of the Laboratory of Mathematical Logic, Steklov Institute of Mathematics, Russian Academy of Sciences, Saint Petersburg.
Table of Contents Series Foreword ..... ix
A Note on the Translation ..... xi
Foreword ..... xiii
Preface to the Second Edition ..... xviii
Preface ..... xix
1 Principal Definitions ..... 1
1.1 Diophantine equations as a decision problem ..... 1
1.2 Systems of Diophantine equations ..... 2 1.3 Solutions in natural numbers ..... 4 1.4 Families of Diophantine equations ..... 6 1.5 Logical terminology ..... 9 1.6 Some simple examples of Diophantine sets, properties, relations, and functions ..... 12
2 Exponentation Is Diophantine ..... 19
2.1 Special second-order recurrent sequences ..... 19
2.2 The special recurrent sequences are Diophantine (basic ideas) ..... 21 2.3 The special recurrent sequences are Diophantine (proof) ..... 26 2.4 Exponentiation is Diophantine ..... 31 2.5 Exponential Diophantine equations ..... 33
3 Diophantine Coding ..... 41
3.1 Cantor numbering ..... 41 3.2 Godel coding ..... 42 3.3 Positional coding ..... 44 3.4 Binomial coefficients, the factorial, and the prime numbers are Diophantine ..... 45 3.5 Comparison of tuples ..... 47 3.6 Extensions of functions to tuples ..... 49
4 Universal Diophantine Equations ..... 57
4.1 Basic definitions ..... 57 4.2 Coding equations ..... 59 4.3 Coding possible solutions ..... 61 4.4 Computing the values of polynomials ..... 62
4.5 Universal Diophantine equations ..... 64 4.6 Diophantine sets with non-Diophantine complements ..... 65
5 Hilbert's Tenth Problem Is Unsolvable ..... 71
5.1 Turing machines ..... 71 5.2 Composition of machines ..... 73 5.3 Basis machines ..... 75 5.4 Turing machines can recognize Diophantine sets ..... 83
5.5 Diophantine simulation of Turing machines ..... 85
5.6 Hilbert's Tenth Problem is undecidable by Turing machines ..... 92 5.7 Church's Thesis ..... 94
6 Bounded Universal Quantifiers ..... 103
6.1 First construction: Turing machines ..... 103
6.2 Second construction: Godel coding ..... 104
6.3 Third construction: summation ..... 109 6.4 Connections between Hilbert's Eighth and Tenth Problems ..... 116 6.5 Yet another universal equation ..... 122 6.6 Yet another Diophantine set with non-Diophantine complement ..... 123
7 Decision Problems in Number Theory ..... 129
7.1 The number of solutions of Diophantine equations ..... 129 7.2 Non-effectivizable estimates in the theory of exponential Diophantine equations ..... 130
7.3 Gaussian integer counterpart of Hilbert's Tenth Problem ..... 138 7.4 Homogeneous equations and rational solutions ..... 146
8 Diophantine Complexity ..... 153
8.1 Principal definitions ..... 153 8.2 A bound for the number of unknowns in exponential Diophantine representations ..... 156
9 Decision Problems in Calculus ..... 165
9.1 Diophantine real numbers ..... 165 9.2 Equations, inequalities, and identities in real variables ..... 168 9.3 Systems of ordinary differential equations ..... 174
9.4 Integrability ..... 177
10 Other Applications of Diophantine Representations ..... 181
10.1 Diophantine games ..... 181 10.2 Generalized knights on a multidimensional chessboard ..... 184
Appendix ..... 199
1 The Four Squares Theorem ..... 199 2 Chinese Remainder Theorem ..... 200 3 Kummer's Theorem ..... 201 4 Summation of a generalized geometric progression ..... 202
Hints to the Exercises ..... 205
Bibliography ..... 221 List of Notation ..... 257 Name Index ..... 259 Subject Index ..... 263

Auteur : MATIYASEVICH
Editeur : M.I.T. PRESS
Nombre de pages : 288
Date de publication : 05 1993

Commandez cet ouvrage