Re:Incompleteness ex Machina – proving Gödel's theorems in t...
by fnrslvr on Saturday February 16, 2019 @05:59AM
(#19178107)
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.
[ Parent
| on HN ]
There are no comments on this comment yet.