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 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 . Earlier results of D. Leivant [Intrinsic theories and computational complexity, in: D. Leivant , 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 of complexity classes between Grzegorczyk’s E2 and E3. (shrink)

Subrecursive hierarchy classifications are used to compare the complexities of recursive functions according to their derivations in a version of Kleene's equation calculus, and their computations by term-rewriting. In each case ordinal bounds are assigned, and it turns out that the respective complexity measures are given by a version of the Fast Growing Hierarchy, and the Slow Growing Hierarchy. Known comparisons between the two hierarchies then provide ordinal trade-offs between derivation and computation. Characteristics of some well-known subrecursive classes are also (...) read off. (shrink)

The class of all recursive functions fails to possess a natural hierarchical structure, generated predicatively from "within". On the other hand, many (proof-theoretically significant) sub-recursive classes do. This paper attempts to measure the limit of predicative generation in this context, by classifying and characterizing those (predictably terminating) recursive functions which can be successively defined according to an autonomy condition of the form: allow recursions only over well-orderings which have already been "coded" at previous levels. The question is: how can a (...) recursion code a well-ordering? The answer lies in Girard's theory of dilators, but is reworked here in a quite different and simplified framework specific to our purpose. The "accessible" recursive functions thus generated turn out to be those provably recursive in $(\prod_{1}^{1}-CA)_{0}$. (shrink)

This work is derived from the SERC "Logic for IT" Summer School Conference on Proof Theory held at Leeds University. The contributions come from acknowledged experts and comprise expository and research articles which form an invaluable introduction to proof theory aimed at both mathematicians and computer scientists.

Following our [6], though with somewhat different methods here, further variants of Goodstein sequences are introduced in terms of parameterized Ackermann–Péter functions. Each of the sequences is shown to terminate, and the proof-theoretic strengths of these facts are calibrated by means of ordinal assignments, yielding independence results for a range of theories: PRA, PA,$\Sigma ^1_1$-DC$_0$, ATR$_0$, up to ID$_1$. The key is the so-called “Hardy hierarchy” of proof-theoretic bounding finctions, providing a uniform method for associating Goodstein-type sequences with parameterized normal (...) form representations of positive integers. (shrink)

The fundamental ideas concerning computation and recursion naturally find their place at the interface between logic and theoretical computer science. The contributions in this book, by leaders in the field, provide a picture of current ideas and methods in the ongoing investigations into the pure mathematical foundations of computability theory. The topics range over computable functions, enumerable sets, degree structures, complexity, subrecursiveness, domains and inductive inference. A number of the articles contain introductory and background material which it is hoped will (...) make this volume an invaluable resource for specialists and non-specialists alike. (shrink)

Wilfred Sieg and Stanley S. Wainer. Program Transformation and Proof Transformation.

Girard’s maxim, that Peano Arithmetic is a theory of one inductive definition, is re-examined in the light of a weak theory EA formalising basic principles of Nelson’s predicative Arithmetic.