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 b\ge 4,

\alpha_b(0)=0,
\alpha_b(1)=1, and
\alpha_b(n+2)=b\alpha_b(n+1)-\alpha_b(n) for all n.

We began 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.
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: