Hilbert's tenth problem and some generalizations

Abstract

Hilbert's tenth problem asks for an algorithm to determine the solvability in integers of diophantine equations over Z. We prove that such an algorithm does not exist, and prove analogous statements for equations over polynomial rings, for equations over rings of integers of quadratic extensions of Q and for equations over rational function fields defined over either formally real fields or finite fields. This requires a proof that the positive existential theories of several languages with divisibility relations are undecidable. We also try to prove that the diophantine theory of rational function fields over infinite fields of positive characteristic is undecidable, i.e. that no analogous algorithm exists. However, we are only able to show that the first order theory is undecidable.