Content
of the book
written by
Yuri MATIYASEVICH

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 secondorder 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 nonDiophantine 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 nonDiophantine complement
 Exercises
 Commentary

 7 Decision Problems in Number Theory
 7.1 The number of solutions of Diophantine equations
 7.2 Noneffectivizable 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
URL of the original Home page of the book is
http://logic.pdmi.ras.ru/~yumat/H10Pbook.
It has a mirror at
http://www.informatik.unistuttgart.de/ifi/ti/personen/Matiyasevich/H10Pbook.
All comments can be
emailed
to the
author of the book.