So is PA the weakest system capable of encapsulating Turing logic?
No. You don’t need induction to do so. You can just use arithmetic to slowly, slowly evaluate the TM until you find something that halts or don’t. The oracle holds all the power.
So is PA the weakest system capable of encapsulating Turing logic?
No. You don’t need induction to do so. You can just use arithmetic to slowly, slowly evaluate the TM until you find something that halts or don’t. The oracle holds all the power.