117b – Homework 4

Due Thursday, February 1 at 1:00 pm.

The second pdf contains some hints for problem 3.

117b – Undecidability and Incompleteness – Lecture 2

The core of the proof of the undecidability of the tenth problem is the proof that exponentiation is Diophantine. We reduced this to proving that certain sequences given by second-order recurrence equations are Diophantine. These are the Matiyasevich sequences: For ,

,
, and
 for all .

We begin the proof that they are Diophantine by analyzing some of the algebraic identities their terms satisfy.

Additional reference:

• Unsolvable problems, by M. Davis. In Handbook of mathematical logic, J. Barwise, ed., North-Holland (1977), 567-594.