The equivalence of Diophantine equations and Turing machines is established by the MRDP theorem: https://en.wikipedia.org/wiki/Diophantine_set#Matiyasevich's_th

The equivalence of Diophantine equations and Turing machines is established by the MRDP theorem: https://en.wikipedia.org/wiki/Diophantine_set#Matiyasevich's_theorem https://en.wikipedia.org/wiki/Diophantine_set#Matiyasevich's... For every Diophantine equation P(x, y) = 0, where x is a tuple of integer parameters and y is a tuple of unknowns, there is a Turing machine that takes the parameters x as input and halts iff there is an integer solution y satisfying the equation (this direction is easy, just have the Turing machine test all tuples of integers in some order and halt iff it found a solution) and for every Turing machine, there is a Diophantine equation so that if x is an encoding of the Turing machine input, there is an integer solution y to the equation iff the the Turing machine halts for input x. (This direction is hard, you need to have y encode the execution history of the Turing machine somehow, and enforce the transition rules with the structure of the equation.)