We conclude the proof that *Matiyasevich sequences *are Diophantine. This involves a delicate analysis of congruences satisfied by terms of these sequences.

It follows that exponentiation is Diophantine. Using exponentiation, we can now proceed to code finite sequences, the key idea behind both the proof of undecidability of the tenth problem and of the incompleteness theorems.

### Like this:

Like Loading...

*Related*

This entry was posted on January 30, 2007 at 5:55 pm and is filed under 117b, Undecidability and incompleteness. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply