Provably Total Functions of Arithmetic with Basic Terms

Evgeny Makarov
(INRIA)

A new characterization of provably recursive functions of first-order arithmetic is described. Its main feature is using only terms consisting of 0, the successor S and variables in the quantifier rules, namely, universal elimination and existential introduction.

In Jean-Yves Marion: Proceedings Second Workshop on Developments in Implicit Computational Complexity (DICE 2011), Saarbrücken, Germany, April 2nd and 3rd, 2011, Electronic Proceedings in Theoretical Computer Science 75, pp. 28–32.
Published: 1st January 2012.
ArXived at: https://dx.doi.org/10.4204/EPTCS.75.3 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org