undefined

points

[-]

This is not bidirectional. The Davis-Putnam-Robinson-Matiyasevich theorem shows we can make a Diophantine equation that acts as a universal Turing machine, but there’s Diophantine equations that cannot be solved by Turing machines:

https://www.nlp-kyle.com/post/number_computability/

The smallest known Diophantine equation that cannot be solved by any Turing machine last I checked had ~8000 states as a Turing machine. This Turing machine cannot be decided to halt, and if it does halt in finite time then an (outer) Turing machine could execute it to predict that, so this lives beyond decidability:

https://scottaaronson.blog/?p=2725

I find it annoying that the response to this from the Chaitain perspective is to throw your hands in the air and say not all of math is predictable and let “equivalent to halting decidability” be the death of effort. There’s a richer field of ‘hypercomputation’ sitting beyond the pale, and I believe it will be topological applications that untwist this knot [pun intended]. I’m excited for the post Turing world but i dare say I won’t live to see it.

by gweinberg1 hours ago|

parent|

[-]

Wait, are you saying they can't be solved by a Turing machine, but they can be solved some other way? If so, how?

by ForOldHack6 minutes ago|

parent|

[-]

The Matiyasevich theorem (which settled Hilbert's 10th Problem) proved that Diophantine equations are fundamentally tied to the Halting Problem. Because a universal Turing machine cannot determine if any arbitrary program will halt, no computer program or mathematical algorithm can ever be written to determine if any arbitrary Diophantine equation has an integer solution.

by 1 hours ago|

parent|

prev|

[-]

deleted

by gregfjohnson2 hours ago|

prev|

[-]

It is a surprising and delightful consequence of this observation that there is a polynomial whose integer-valued roots are exactly the set of all prime numbers.