4 ms·

A computer does more than store values: it also performs computation. And “they’re rich enough to simulate computers” refers to the celebrated (and surely surpr

by svat 8y ago

A computer does more than store values: it also performs computation. And “they’re rich enough to simulate computers” refers to the celebrated (and surely surprising!) theorem of Julia Robinson, Martin Davis, Hilary Putnam, and Yuri Matiyasevich, showing that (to state the result in a couple of ways): * given a computer program that prints integers, there is a Diophantine equation whose integer solutions are precisely the set of integers printed by that program, * given any computer program, one can represent it by a Diophantine problem: one can write down a polynomial equation such that it has integer solutions if and only if the program halts. For example, because we can write down a computer program to print the prime numbers, there exists a certain (explicitly known) polynomial whose integer values are precisely the prime numbers. And as we can write down a program which halts only if (say) the Riemann hypothesis is true, we can write down a Diophantine equation which has integer solutions only if the Riemann hypothesis is true. (What you're saying about being able to represent every value a computer can represent would be true for say linear or quadratic equations too, but those are not rich enough to simulate all of computation.) Essentially, you can build a computer out of diophantine equations. You can read more at https://en.wikipedia.org/w/index.php?title=Hilbert%27s_tenth_problem&oldid=886276765 https://en.wikipedia.org/w/index.php?title=Hilbert%27s_tenth... and good expositions by Poonen at http://www-math.mit.edu/~poonen/papers/sample_beamer.pdf http://www-math.mit.edu/~poonen/papers/sample_beamer.pdf (talk slides) or http://www.ams.org/notices/200803/tx080300344p.pdf http://www.ams.org/notices/200803/tx080300344p.pdf (article).

thaumasiotes 8y ago
> What you're saying about being able to represent every value a computer can represent would be true for say linear or quadratic equations too, but those are not rich enough to simulate all of computation. True, but this is a strange comparison to make. Calling an equation "linear" or "quadratic" is a statement about the kinds of computation involved in the equation. Calling an equation "Diophantine" is a statement about the kinds of solutions to that equation that you, the author/reader, consider acceptable. These are not comparable concepts. I understood the claim "Diophantine equations are sufficient to represent a computer" to contrast with e.g. "Real-valued equations are sufficient to represent a computer". It's true that real numbers have more power (vaguely defined) than integers do, so I can see why this comparison might be drawn in the first place. But since computers can't use real numbers, I still don't find it surprising that integers are sufficient. > A computer does more than store values: it also performs computation. Yes, but this is not a way in which computers differ from equations. And there are no restrictions on the types of computation you can invoke in an equation, whereas computers are e.g. restricted to computing computable numbers. > And “they’re rich enough to simulate computers” refers to the celebrated (and surely surprising!) theorem... The proof of the incompleteness theorem involves showing that integers, by themselves, are rich enough to represent any arbitrary mathematical statement. Why would it be surprising that adding structure on top of the integers lets you keep the expressive power you already had? "x = k", for some constant k that encodes your chosen meaning, is a perfectly valid Diophantine equation, and we already know that we can represent arbitrary mathematical statements using only equations of that form. The additional forms allowed by extending ourselves to arbitrary equations won't take anything away from that.
- svat 8y ago
  To clarify the comparison I made, consider the set of integer solutions to linear equations (or to be more precise, the Diophantine set of a linear polynomial). For example, for the equation x+y=k, the set of integer solutions k is merely the set of all integers. For the equation 10x+6y=k, you get the set of all even integers. For the equation 10x+6y+7z=k, again you get the set of all integers. So the sets of integers that you can obtain as the respective solutions to linear equations are all very simply structured. (If I'm not mistaken, they are always simply the multiples of the gcd of the coefficients of the variables, possibly translated by some constant offset e.g. if one is considering 6x+9y+15z+7=k, the set of obtainable k (by plugging in various values for (x, y, z)) is “all integers that are 1 mod 3” — so the set is always simply an arithmetic progression.) Similarly for quadratic equations — you still get sets that are easily parametrized. Something like this is what motivated Hilbert to ask the question in the first place. Nothing so far would have suggested that if you go up to higher-degree polynomials, you should eventually be able to obtain any computable (i.e. recursively enumerable) set as the set of integer solutions to some polynomial equation. Yet that's the case. The contrast was never with real numbers, so mentioning real numbers is neither here nor there. (Though I understand how one can get that impression, if one thinks that what is being highlighted is “Diophantine solutions” in the sense of “integer solutions” as opposed to “real solutions” or whatever.) The surprising fact being highlighted by the number-theorist in the quote (and one of the highlights of 20th-century mathematics) is that the structure “the set of integer solutions to a polynomial equation” is rich enough to encode all possible computation — i.e. polynomials are not as “simple” as one may think. (Please take a look at those links if you haven't; it's really beautiful and super surprising that a program can be encoded as the set of integer roots of an integer polynomial.)

by svat 8y ago

thaumasiotes 8y ago

> What you're saying about being able to represent every value a computer can represent would be true for say linear or quadratic equations too, but those are not rich enough to simulate all of computation. True, but this is a strange comparison to make. Calling an equation "linear" or "quadratic" is a statement about the kinds of computation involved in the equation. Calling an equation "Diophantine" is a statement about the kinds of solutions to that equation that you, the author/reader, consider acceptable. These are not comparable concepts. I understood the claim "Diophantine equations are sufficient to represent a computer" to contrast with e.g. "Real-valued equations are sufficient to represent a computer". It's true that real numbers have more power (vaguely defined) than integers do, so I can see why this comparison might be drawn in the first place. But since computers can't use real numbers, I still don't find it surprising that integers are sufficient. > A computer does more than store values: it also performs computation. Yes, but this is not a way in which computers differ from equations. And there are no restrictions on the types of computation you can invoke in an equation, whereas computers are e.g. restricted to computing computable numbers. > And “they’re rich enough to simulate computers” refers to the celebrated (and surely surprising!) theorem... The proof of the incompleteness theorem involves showing that integers, by themselves, are rich enough to represent any arbitrary mathematical statement. Why would it be surprising that adding structure on top of the integers lets you keep the expressive power you already had? "x = k", for some constant k that encodes your chosen meaning, is a perfectly valid Diophantine equation, and we already know that we can represent arbitrary mathematical statements using only equations of that form. The additional forms allowed by extending ourselves to arbitrary equations won't take anything away from that.

svat 8y ago
To clarify the comparison I made, consider the set of integer solutions to linear equations (or to be more precise, the Diophantine set of a linear polynomial). For example, for the equation x+y=k, the set of integer solutions k is merely the set of all integers. For the equation 10x+6y=k, you get the set of all even integers. For the equation 10x+6y+7z=k, again you get the set of all integers. So the sets of integers that you can obtain as the respective solutions to linear equations are all very simply structured. (If I'm not mistaken, they are always simply the multiples of the gcd of the coefficients of the variables, possibly translated by some constant offset e.g. if one is considering 6x+9y+15z+7=k, the set of obtainable k (by plugging in various values for (x, y, z)) is “all integers that are 1 mod 3” — so the set is always simply an arithmetic progression.) Similarly for quadratic equations — you still get sets that are easily parametrized. Something like this is what motivated Hilbert to ask the question in the first place. Nothing so far would have suggested that if you go up to higher-degree polynomials, you should eventually be able to obtain any computable (i.e. recursively enumerable) set as the set of integer solutions to some polynomial equation. Yet that's the case. The contrast was never with real numbers, so mentioning real numbers is neither here nor there. (Though I understand how one can get that impression, if one thinks that what is being highlighted is “Diophantine solutions” in the sense of “integer solutions” as opposed to “real solutions” or whatever.) The surprising fact being highlighted by the number-theorist in the quote (and one of the highlights of 20th-century mathematics) is that the structure “the set of integer solutions to a polynomial equation” is rich enough to encode all possible computation — i.e. polynomials are not as “simple” as one may think. (Please take a look at those links if you haven't; it's really beautiful and super surprising that a program can be encoded as the set of integer roots of an integer polynomial.)