Elementary arithmetic

@article{citeulike:131996, abstract = {There is a very simple way in which the safe/normal variable discipline of Bellantoni-Cook recursion [S. Bellantoni, S. Cook, A new recursion theoretic characterization of the polytime functions, Computational Complexity 2 (1992) 97-110] can be imposed on arithmetical theories like PA: quantify over safes and induct on normals. This weakens the theory severely, so that the provably recursive functions become more realistically computable (slow growing rather than fast growing). Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant (Ed.), Logic and Computational Complexity, Lecture Notes in Computer Science, vol. 960, Springer-Verlag, 1995, pp. 177-194] are re-worked and extended in this new context, giving proof-theoretic characterizations (according to the levels of induction used) of complexity classes between Grzegorczyk's E2 and E3.}, author = {Ostrin, G. and Wainer, S. }, citeulike-article-id = {131996}, doi = {http://dx.doi.org/10.1016/j.apal.2004.10.012}, journal = {Annals of Pure and Applied Logic}, keywords = {bounded\_arithmetic, icc}, month = {May}, number = {1-3}, pages = {275--292}, posted-at = {2005-03-18 11:13:49}, priority = {3}, title = {Elementary arithmetic}, url = {http://dx.doi.org/10.1016/j.apal.2004.10.012}, volume = {133}, year = {2005} }

TY - JOUR ID - citeulike:131996 L3 - citeulike-article-id:131996 TI - Elementary arithmetic JF - Annals of Pure and Applied Logic VL - 133 IS - 1-3 SP - 275 EP - 292 N2 - There is a very simple way in which the safe/normal variable discipline of Bellantoni-Cook recursion [S. Bellantoni, S. Cook, A new recursion theoretic characterization of the polytime functions, Computational Complexity 2 (1992) 97-110] can be imposed on arithmetical theories like PA: quantify over safes and induct on normals. This weakens the theory severely, so that the provably recursive functions become more realistically computable (slow growing rather than fast growing). Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant (Ed.), Logic and Computational Complexity, Lecture Notes in Computer Science, vol. 960, Springer-Verlag, 1995, pp. 177-194] are re-worked and extended in this new context, giving proof-theoretic characterizations (according to the levels of induction used) of complexity classes between Grzegorczyk's E2 and E3. KW - bounded_arithmetic KW - icc AU - Ostrin, G AU - Wainer, S PY - 2005/05// UR - http://dx.doi.org/10.1016/j.apal.2004.10.012 ER -