Some Lucas Sequences

In this video, I discuss the Lucas sequences that appear in the paper "Proof of Recursive Unsolvability of Hilbert's Tenth Problem" (1991) by Jones and Matijasevich. These sequences are closely related to the Pell Equation, and by showing that they are Diophantine, the paper shows that exponentiation is Diophantine, a critical step in proving that Diophantine relations are Turing complete. I replicate these proofs in this video, focusing on trying to provide a strong intuition for their steps. One of the most exciting thing about this proof is just how accessible it is: all of the relevant mathematics is usually covered in an undergraduate math major. Sources: "Proof of Recursive Unsolvability of Hilbert's Tenth Problem" (1991) by Jones and Matijasevich "Hilbert's Tenth Problem" (1993) by Matijasevich The Online Encyclopedia of Integer Sequences, particularly Y(n) = https://oeis.org/A001353 Wikipedia for Lucas Sequences, Chebyshev Polynomials Please let me know if you have any questions! If you have questions about a specific part of the video, please include a time stamp! 00:00 Ladder Sequence 07:45 Bridge Sequence 16:56 First Step-Down Lemma 21:32 Second Step-Down Lemma 28:00 a-Ladder, a-Bridge sequences 34:14 Motivating the Proof 44:00 The Proof 53:24 Examples 59:28 Exponentiation is Diophantine