4 ms·

> Godel was programming the integers. That is that. And he didn’t even know it at the time; truly impressive. It seems strange to say that Godel didn't know it

> Godel was programming the integers. That is that. And he didn’t even know it at the time; truly impressive. It seems strange to say that Godel didn't know it at the time -- Godel's work was part of the effort to mechanize logic, Hilbert's program, and the axiomatization effort started in response to contradictory calculus theorems, and followed Frege, Russel, Whitehead, et al. Or rather, Godel's work showed that Russel's efforts to create a consistent and complete foundation for mathematics was fundamentally insufficient. Turing extended this work, by providing an explicit model of a calculating machine, to show that no algorithm could effectively determine the truth -- even without providing a proof -- locking the door on Hilbert's program that Godel had slammed shut. Regardless, the entire point of Godel's work was exploring the relationship between our ability to "reason" and our ability "calculate" or "perform rote tasks". (Missing details of the narrative aside -- it was a really good read.)

martinlaz 8y ago
Any chance OP is referring to "integer programming" (aka discrete optimization), which came about 20 years later?
- atq2119 8y ago
  No. Integer programming in the operations research sense is "just" solving linear optimization problems with the constraint that the solution variables need to be integer. In particular, IP doesn't really involve the multiplicative structure of the integers, which is crucial for how Gödel proved his results. Also, I'd point out that while there's significant overlap between integer programming and discrete optimization, they're not the same thing. Integer programming is one tool used in discrete optimization among many.
- fnrslvr 8y ago
  Adding to atq2119's answer, integer programming is merely NP-complete. You really need full Turing computability to get the incompleteness results. The set of provable consequences of Peano arithmetic is RE-complete, and we know that NP != RE, so you definitely can't give an integer program that verifies that a formula is provable from PA, which is a necessary ingredient.
soberhoff 8y ago
Perhaps Gödel had a vague notion of what he was up to. Nonetheless, the whole concept of universal computation was still half a decade away and higher level languages several decades. So I think the remark is still essentially accurate. He had to work without all the modern cognitive conveniences such as for-loops and if/else branching.

martinlaz 8y ago

Any chance OP is referring to "integer programming" (aka discrete optimization), which came about 20 years later?

atq2119 8y ago
No. Integer programming in the operations research sense is "just" solving linear optimization problems with the constraint that the solution variables need to be integer. In particular, IP doesn't really involve the multiplicative structure of the integers, which is crucial for how Gödel proved his results. Also, I'd point out that while there's significant overlap between integer programming and discrete optimization, they're not the same thing. Integer programming is one tool used in discrete optimization among many.
fnrslvr 8y ago
Adding to atq2119's answer, integer programming is merely NP-complete. You really need full Turing computability to get the incompleteness results. The set of provable consequences of Peano arithmetic is RE-complete, and we know that NP != RE, so you definitely can't give an integer program that verifies that a formula is provable from PA, which is a necessary ingredient.

soberhoff 8y ago

Perhaps Gödel had a vague notion of what he was up to. Nonetheless, the whole concept of universal computation was still half a decade away and higher level languages several decades. So I think the remark is still essentially accurate. He had to work without all the modern cognitive conveniences such as for-loops and if/else branching.