One context in which diophantine equations arise is hidden within the innards of loop optimizing compilers, where loop carried dependencies are considered, as they constrain parallelization.
I had (and donated to an engineering library in Urbana) a book about just this from the early 90s. I tried finding it on Amazon but no such luck.
Diophantine equations are as they say Turing complete. That is for any question about does this Turing machine with this tape halt with a certain value there is a corresponding Diophantine equation, which has solutions if the machine halts with the output corresponding to the values it is solved by. I think this paper covers it for register machines rather than Turing machines directly: https://carleton.ca/math/wp-content/uploads/Nick-Murphy-Hono...
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:
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:
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.
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.
The article doesn't really tell us much about the "why" unfortunately. Diophantine equations are introduced but all the interesting stuff is promised in future articles which haven't come yet. All the reader can take from this is that these equations lead to some "profound hidden structures" without a good idea what they are.
I get that it's hard to wrap one's head around the Langlands program but I'd love to see at least more exposition on the following statement:
>inventing the Euclidean algorithm is essentially equivalent to inventing unique prime factorization
Of course to measure out 42 litres from two jugs of 5 and 17 litres each on the day that the sun is in the exact same position among the constellations as today, and so is the Moon and in the same phase.
I thought this was obvious, like which is the better editor vi or whatever that other one was.
The purpose of this article was, secretly, to tell the reader about another class of Diophantine equations which leads to the Langlands program, which studies from incredibly intricate hidden structure inside of number theory. The Langlands program studies Diophantine equations of the form
One context in which diophantine equations arise is hidden within the innards of loop optimizing compilers, where loop carried dependencies are considered, as they constrain parallelization.
I had (and donated to an engineering library in Urbana) a book about just this from the early 90s. I tried finding it on Amazon but no such luck.
This was a recurrent tool at
https://en.wikipedia.org/wiki/University_of_Illinois_Center_...
Diophantine equations are as they say Turing complete. That is for any question about does this Turing machine with this tape halt with a certain value there is a corresponding Diophantine equation, which has solutions if the machine halts with the output corresponding to the values it is solved by. I think this paper covers it for register machines rather than Turing machines directly: https://carleton.ca/math/wp-content/uploads/Nick-Murphy-Hono...
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.
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.
The article doesn't really tell us much about the "why" unfortunately. Diophantine equations are introduced but all the interesting stuff is promised in future articles which haven't come yet. All the reader can take from this is that these equations lead to some "profound hidden structures" without a good idea what they are.
I get that it's hard to wrap one's head around the Langlands program but I'd love to see at least more exposition on the following statement:
>inventing the Euclidean algorithm is essentially equivalent to inventing unique prime factorization
Of course to measure out 42 litres from two jugs of 5 and 17 litres each on the day that the sun is in the exact same position among the constellations as today, and so is the Moon and in the same phase.
I thought this was obvious, like which is the better editor vi or whatever that other one was.
The purpose of this article was, secretly, to tell the reader about another class of Diophantine equations which leads to the Langlands program, which studies from incredibly intricate hidden structure inside of number theory. The Langlands program studies Diophantine equations of the form
This is not what the Langlands program is