Practical Programming of Diophantine Equations

In this video, I complete the proof of the negative solution to Hilbert's Tenth Problem: By showing that Diophantine equations are Turing complete, determining if they have solutions becomes equivalent to the halting problem. Most of this video is based on "Proof of Recursive Unsolvability of Hilbert's Tenth Problem" (1991) by Jones and Matijasevič and Chapter 2 of "Gems of Theoretical Computer Science" (1998) by Schöning and Pruim, with some reference to Matiyasevich's book "Hilbert's Tenth Problem" (1993). 00:00 Diophantine Equations 09:16 Expanding our Vocabulary 23:33 Bitwise Logic 30:45 Cellular Automata and Turing Machines 39:52 Register Machines 46:12 Register Machines to Dioph Eqns 52:17 Encoding Registers 56:35 Encoding Conditional Jump 1:05:29 The Halting Problem Some additional notes: 1:14: Here I'm referring to Sturm's Theorem: (https://en.wikipedia.org/wiki/Sturm%2..., which I mention in RLMT 21:    • Regular Languages and Model Theory 21: Qua...   4:50: Wikipedia has some proofs of the four-squares theorem: https://en.wikipedia.org/wiki/Lagrang... 13:28: I go through an exercise of translating an arbitrary truth table to disjunctive normal form in RLMT 20:    • Regular Languages and Model Theory 20: Nor...   14:35: See my video on Lucas Sequences:    • Some Lucas Sequences   20:23: Note that Diophantine equations of degree 2 are solvable, and the question of whether Diophantine equations of degree 3 are solvable is open 25:07: This diagram was inspired by this diagram in Wolfram's "New Kind of Science": https://www.wolframscience.com/nks/p6... . Note that "New Kind of Science" doesn't cite its sources, so it's not clear if this presentation is originally from Wolfram. 27:33 See https://en.wikipedia.org/wiki/Lucas%2... 28:38: I found this characterization of the bitwise operations in "New Kind of Science": https://www.wolframscience.com/nks/no... Again, it's not clear who to credit this to. 36:03: See Cook's "Universality in Elementary Cellular Automata" (2004) 36:24: I used viewing Turing machines as 1-D cellular automata previously in RLMT 12:    • Regular Languages and Model Theory 12: Göd...   to prove Gödel's incompleteness theorem. 39:52: See my video on Counter Machines:    • Counter Machines   You may also be interested in my video series on FRACTRAN, my other favorite esoteric programming language    • Introduction to FRACTRAN with my #SoME3 entry   Or my video on some other undecidable logics:    • Regular Languages and Model Theory 13: Und...   A few years back I submitted a video game to a game jam having users actually program some Diophantine equations: https://trkern.itch.io/polynomials . I have yet to figure out a reasonable way of building an interactive like this that incorporates the ideas covered in this video.