No, the key point is that these systems are still polynomial. You cannot ask a question that would require a non-polynomial computation to provide an answer an

No, the key point is that these systems are still polynomial. You cannot ask a question that would require a non-polynomial computation to provide an answer and expect it to be answered correctly. Most importantly, recursive enumerable already means semidecidable. (Because it consists of primitive recursive functions, which are bounded.) Which means by Godel's theorems it is stronger than Peano arithmetics. (See Tennenbaum's theorem, Presburger arithmetics is fine.)