3 ms·
Why do you consider it surprising that Peano Arithmetic is Turing complete?
by eindiran 7y ago
Why do you consider it surprising that Peano Arithmetic is Turing complete?
- gwern 7y agoBecause they're supposed to just be the integers. If it is obvious to you that 'the integers' means undecidability/Turing-completeness, and that integers without multiplication (Presburger) does not, then all I can say is that your mathematical logic intuition is vastly superior to mine and everyone before Turing/Godel.