3 ms·

This sounds very similar to the same process for Turing machines: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20

This sounds very similar to the same process for Turing machines: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20240702/ https://www.quantamagazine.org/amateur-mathematicians-find-f... Determining the halting behavior of each successive Turing machine generally becomes harder and harder until eventually we reach a machine with Collatz-like behavior. The two problems are equivalent in some sense, but I wonder if there's an easy way to "port" over the work between the two projects.

yorwba 2y ago
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.)
- Xen9 2y ago
  I believe there is no better kind of feeling in all of mathematics & all of science than that which one may get from the knowledge that an an intuitive, possibly shaky idea they themselves suggested already exists as rigorous and useful theorem.

3 ms·

This sounds very similar to the same process for Turing machines: https://www.quantamagazine.org/amateur-mathematicians-find-fifth-busy-beaver-turing-machine-20

by Xcelerate 2y ago

yorwba 2y ago
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.)
- Xen9 2y ago
  I believe there is no better kind of feeling in all of mathematics & all of science than that which one may get from the knowledge that an an intuitive, possibly shaky idea they themselves suggested already exists as rigorous and useful theorem.