We complete the proof of the undecidability of Hilbert’s tenth problem, and discuss some of its consequences, tying up with the general theory of the degrees and leading directly into the second part of this topic: The incompleteness theorems.

## Archive for February, 2007

### 117b – Undecidability and incompleteness – Lecture 5

February 8, 2007### 117b – Homework 5

February 3, 2007### 117b – Undecidability and Incompleteness – Lecture 4

February 1, 2007We show that *a=n!* is Diophantine*.* This implies that the prime numbers are Diophantine. Therefore, there is a polynomial in several variables with integer coefficients whose *range,* when intersected with the natural numbers, coincides with the set of primes. Amusingly, no nonconstant polynomial with integer coefficients can only take prime values.

We prove the *bounded quantifier lemma, *the last technical component of the proof. It implies that the class of relations definable by a S^{0}_{1} formula in the structure (**N**,+,´,<) coincides with the class of S_{1 }relations (i.e., the Diophantine ones).

To complete the proof of the undecidability of the tenth problem, we will show that any c.e. relation is Diophantine. For this, we recall that a set is c.e. iff it is the domain of a Turing machine and proceed to code the behavior of Turing machines by means of a Diophantic representation. This involves coding configurations of Turing machines and it remains to show how to code the way a configuration changes into another one.