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 secondorder recurrence equations are Diophantine. These are the Matiyasevich sequences: For b³4,
a_{b}(0)=0,
a_{b}(1)=1, and
a_{b}(n+2)=ba_{b}(n+1)a_{b}(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., NorthHolland (1977), 567594.
Advertisements
January 5, 2012 at 1:32 am 
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!