Archive for February, 2007

117b – Undecidability and incompleteness – Lecture 5

February 8, 2007

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.

Advertisements

117b – Homework 5

February 3, 2007

We will skip a week so this does not interfere with midterms. Homework 5 is due Thursday, February 15 at 1pm.

Homework 5

Important update:  The statement of problem 4 may seem a bit ambiguous. That is “a partial function in C” simply means that it is a partial recursive function.

117b – Undecidability and Incompleteness – Lecture 4

February 1, 2007

We 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 S01 formula in the structure (N,+,´,<) coincides with the class of S1 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.