3 ms·
It should be noted that the special sauce that makes arithmetic really difficult is induction. Induction isn't just reasoning about computation, (i.e simple eq
by rocqua 8y ago
It should be noted that the special sauce that makes arithmetic really difficult is induction.
Induction isn't just reasoning about computation, (i.e simple equations). Instead it is reasoning about reasoning about equations (i.e. reasoning about all equations).
Specifically we have: this formula https://wikimedia.org/api/rest_v1/media/math/render/svg/67e20a414c6f0eb6af309ddbe2bcee1391b3d0ea https://wikimedia.org/api/rest_v1/media/math/render/svg/67e2...
- salthound 8y agoBut it should be pointed out that induction is essentially unrelated to Gödel's theorem. For example, Robinson Arithmetic is a finitely axiomatized theory whose axioms contain only one existential quantifier, but just like full (Peano) arithmetic, it is subject to Gödel's incompleteness theorems.
- rocqua 8y agoWow, I thought it was required to have second order logic for godel to apply, but this seems to be a first order logic that is still undecidable.
- ratmice 8y agoFrom the other side of the fence, another thing to look at would be the decidability of presburger, and skolem arithmetic, the following paper then goes over the extensions of these, which render the result undecidable. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.2136 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.21...