Archive for Mathematical Logic 39 (7):515-539 (2000)

Two simply typed term systems $\sf {PR}_1$ and $\sf {PR}_2$ are considered, both for representing algorithms computing primitive recursive functions. $\sf {PR}_1$ is based on primitive recursion, $\sf {PR}_2$ on recursion on notation. A purely syntactical method of determining the computational complexity of algorithms in $\sf {PR}_i$ , called $\mu$ -measure, is employed to uniformly integrate traditional results in subrecursion theory with resource-free characterisations of sub-elementary complexity classes. Extending the Schwichtenberg and Müller characterisation of the Grzegorczyk classes ${\mathcal{E}}_n$ for $n\ge 3$ , it is shown $\mathcal{E}_{n+1} = \mathcal{R}^n_1 $ for $ n\ge 1 $, where $ \mathcal{R}^n_i$ denotes the \emph{ $n$ th modified Heinermann class} based on $\mu$ . The proof does not refer to any machine-based computation model, unlike the Schwichtenberg and Müller proofs. This is due to the notion of modified recursion lying on top of each other provided by $\mu$ . By Ritchie's result, $\mathcal{R}^1_1$ characterises the linear-space computable functions. Using the same method, a short and straightforward proof is presented, showing that $\mathcal{R}^1_2$ characterises the polynomial time computable functions. Furthermore, the classes $\mathcal{R}^n_2$ and $\mathcal{R}^n_1$ coincide at and above level 2
Keywords Legacy
Categories (categorize this paper)
DOI 10.1007/s001530050163
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 58,398
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Mω Considered as a Programming Language.Karl-Heinz Niggl - 1999 - Annals of Pure and Applied Logic 99 (1-3):73-92.
Control Structures in Programs and Computational Complexity.Karl-Heinz Niggl - 2005 - Annals of Pure and Applied Logic 133 (1-3):247-273.

Add more citations

Similar books and articles

Partitions of Large Rado Graphs.M. Džamonja, J. A. Larson & W. J. Mitchell - 2009 - Archive for Mathematical Logic 48 (6):579-606.
An Example Related to Gregory’s Theorem.J. Johnson, J. F. Knight, V. Ocasio & S. VanDenDriessche - 2013 - Archive for Mathematical Logic 52 (3-4):419-434.
Degrees of Difficulty of Generalized R.E. Separating Classes.Douglas Cenzer & Peter G. Hinman - 2008 - Archive for Mathematical Logic 46 (7-8):629-647.
Subrecursive Functions on Partial Sequences.Karl-Heinz Niggl - 1999 - Archive for Mathematical Logic 38 (3):163-193.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
Embedding FD(Ω) Into {Mathcal{P}_s} Densely.Joshua A. Cole - 2008 - Archive for Mathematical Logic 46 (7-8):649-664.
Observables and Statistical Maps.Stan Gudder - 1999 - Foundations of Physics 29 (6):877-897.
Why is $$\Mathcal{CPT}$$ Fundamental?O. W. Greenberg - 2006 - Foundations of Physics 36 (10):1535-1553.
A Fixed Point for the Jump Operator on Structures.Antonio Montalbán - 2013 - Journal of Symbolic Logic 78 (2):425-438.
Classical Modal De Morgan Algebras.Sergio A. Celani - 2011 - Studia Logica 98 (1-2):251-266.


Added to PP index

Total views
11 ( #803,337 of 2,420,690 )

Recent downloads (6 months)
1 ( #543,246 of 2,420,690 )

How can I increase my downloads?


My notes