"HILBERT's TENTH PROBLEM"

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

Exercises

Commentary

 

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

Exercises

Commentary

 

3 Diophantine Coding

3.1 Cantor numbering

3.2 Gödel 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

Exercises

Commentary

 

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

Exercises

Commentary

 

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

Exercises

Commentary

 

6 Bounded Universal Quantifiers

6.1 First construction: Turing machines

6.2 Second construction: Gödel 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

Exercises

Commentary

 

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

Exercises

Commentary

 

8 Diophantine Complexity

8.1 Principal definitions

8.2 A bound for the number of unknowns in exponential Diophantine representations

Exercises

Commentary

 

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

Exercises

Commentary

 

10 Other Applications of Diophantine Representations

10.1 Diophantine games

10.2 Generalized knights on a multidimensional chessboard

Exercises

Commentary

 

Appendix

1 The Four Square 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