3 ms·
"Peano arithmetic: addition & multiplication on natural numbers is enough to be TC;" My head swims when the situation is described with this level of vagueness
by joe_the_user 7y ago
"Peano arithmetic: addition & multiplication on natural numbers is enough to be TC;"
My head swims when the situation is described with this level of vagueness. I mean, sure the task of proving a theorem using the modern version of the Peano postulates is undeciable and so I'd assume a map from theorems in the Peano system to proofs of theorems would be Turing complete.
But a computation system based on calculating the values of simple arithmetic expressions isn't Turing complete. An express involving just adding and multiplying constant integer values will terminate.
- tgv 7y agoPerhaps he means that you could somehow abuse the induction axiom, although it seems to me that would be in a way that's not what the axiom was meant for.