Timeline for Why is this new result such a big deal?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2021 at 16:52 | comment | added | François G. Dorais | @pyrulez using standard rules of inference. For example, PRA proves $\forall x \exists y (y = x^2)$ because squaring is primitive recursive. | |
| Jun 9, 2021 at 15:28 | comment | added | Christopher King | PRA is quantifier free, right? How can it prove Pi_2 statements? | |
| May 27, 2016 at 8:51 | comment | added | François G. Dorais | No, what I wrote is correct. PRA does not prove that the Ackermann function is total. | |
| May 27, 2016 at 2:51 | comment | added | none | Btw, regarding above comment about primitive recursive algorithms: I'm not sure whether the question was a minor point of terminology, or whether the issue is actually significant. | |
| May 27, 2016 at 2:44 | comment | added | none | Thanks! The explanation of RT$^2_2$ being useful in termination proofs adds helpful context. But do you really mean to say that (PRA proves termination) means the algorithm itself is primitive recursive? For example I thought PRA proves that the (partial recursive) algorithm for the Ackermann function terminates. | |
| May 27, 2016 at 0:44 | history | edited | François G. Dorais | CC BY-SA 3.0 |
added 40 characters in body
|
| May 27, 2016 at 0:12 | history | edited | François G. Dorais | CC BY-SA 3.0 |
added 71 characters in body
|
| May 27, 2016 at 0:06 | history | answered | François G. Dorais | CC BY-SA 3.0 |