Hilbert's tenth problem

✍ Scribed by Jurij V MatijasevicМЊ

• Publisher: MIT Press
• Year: 1993
• Tongue: English
• Leaves: 291
• Series: Foundations of computing
• Edition: 3. print
• Category: Library

✦ Table of Contents

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