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 reduce this to proving that certain sequences given by second-order recurrence equations are Diophantine. These are the Matiyasevich sequences: For b³4,

ab(0)=0,
ab(1)=1,
and
ab(n+2)=bab(n+1)-ab(n)  for all n.

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.

Advertisements

One Response to “117b – Undecidability and Incompleteness – Lecture 2”

  1. Custom NFL Jerseys Says:

    Interesting post! When i wasnt receptive to this. Its refreshing to find out because I have so disappointed when writers put no thought in their work. This is conclusive evidence now you understand what youre talking about. Ill definitely visit again!

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: