Diophantine representations of recursive enumerable sets

Abstract

In this thesis we will discuss various results found by other mathematicians about the connection between recursively enumerable sets and diophantine representation. As a starting point, we will use the Martin Davis theorem that uses results from Godel and Rosser. We will then review the proofs of the DPR-theorem, the DPRM-theorem and the single-fold DPR-theorem. After that, we will discuss the conjecture that all recursively enumerable sets are single-fold diophantine. A main result discussed in this thesis is the diophantine representation of the exponential relation found by the mathematician Matiyasevich. A single-fold diophantine representation of this same relation would prove the conjecture, but this has not been found yet. There is a result that a non-effective estimate of the solutions of the equation 9(u^2 +7 v^2)^2 - (r^2+7 s^2)^2 = 2 would theoretically give us a single-fold diophantine representation of exponentiation. We will look at the proof of this statement and we will study some solutions of other equations like the one in the statement.