CONTENTS
Series Foreword = ⅸ
A Note on the Translation = xi
Foreword = xiii
Preface to the English 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 Exponentiation 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 G$$\ddot o$$del 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 : G$$\ddot o$$del 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
