We investigate a simply typed term system ℘R ω aimed at defining partial primitive recursive functionals over arbitrary Scott domains . A hierarchy of complexity classes R n ω for functionals definable in ℘R ω is given based on a hierarchy of term classes ℘R n ωpn denoting the n th class of so-called prenormal terms . They come into play by the key observation that every term t can be transformed by what we call higher type modularization as a (...) kind of inversion of normalization into an αβη equal term t ′ having almost no structural complexity. However, it turns out that normalization of a prenormal term may increase its structural complexity with respect to the classes ℘R n ωpn , and conversely, ground type modularization being still possible may reduce it. Thus the structural complexity of a prenormal term t defined as the least n with t ϵ ℘R n ωpn depends strongly on the representation of t . We present a measure denoted μ = n rel v , ϱ for prenormal terms t to be read as t is of complexity n with valued free variables v and valued type π . It is shown that μ is stable on αβη equal terms and furthermore, μ ⩽ min {n |∃t′ ϵ ℘R n ω pn .t′ = αβη t} . Moreover, if t is in a certain μ- normal form 2, the estimate above is even true with equality, that is μ yields the structural complexity of the maximal modularization of t , clearly the best a purely structural measure can do. μ-normal forms 2 do not always exist. The counterexample we give, however, clearly shows that μ does not only take into account the structural complexity of a prenormal term but also the nature and computationl complexity of the algorithm it represents. (shrink)

We investigate a simply typed term system ℘R ω aimed at defining partial primitive recursive functionals over arbitrary Scott domains . A hierarchy of complexity classes R n ω for functionals definable in ℘R ω is given based on a hierarchy of term classes ℘R n ωpn denoting the n th class of so-called prenormal terms . They come into play by the key observation that every term t can be transformed by what we call higher type modularization as a (...) kind of inversion of normalization into an αβη equal term t ′ having almost no structural complexity. However, it turns out that normalization of a prenormal term may increase its structural complexity with respect to the classes ℘R n ωpn , and conversely, ground type modularization being still possible may reduce it. Thus the structural complexity of a prenormal term t defined as the least n with t ϵ ℘R n ωpn depends strongly on the representation of t . We present a measure denoted μ = n rel v , ϱ for prenormal terms t to be read as t is of complexity n with valued free variables v and valued type π . It is shown that μ is stable on αβη equal terms and furthermore, μ ⩽ min {n |∃t′ ϵ ℘R n ω pn .t′ = αβη t} . Moreover, if t is in a certain μ- normal form 2, the estimate above is even true with equality, that is μ yields the structural complexity of the maximal modularization of t , clearly the best a purely structural measure can do. μ-normal forms 2 do not always exist. The counterexample we give, however, clearly shows that μ does not only take into account the structural complexity of a prenormal term but also the nature and computationl complexity of the algorithm it represents. (shrink)

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. (shrink)

The paper builds on both a simply typed term system ${\cal PR}^\omega$ and a computation model on Scott domains via so-called parallel typed while programs (PTWP). The former provides a notion of partial primitive recursive functional on Scott domains $D_\rho$ supporting a suitable concept of parallelism. Computability on Scott domains seems to entail that Kleene's schema of higher type simultaneous course-of-values recursion (scvr) is not reducible to partial primitive recursion. So extensions ${\cal PR}^{\omega e}$ and PTWP $^e$ are studied that (...) are closed under scvr. The twist are certain type 1 Gödel recursors ${\cal R}_k$ for simultaneous partial primitive recursion. Formally, ${\cal R}_k\vec{g}\vec{H}xi$ denotes a function $f_i \in D_{\iota\to\iota}$ , however, ${\cal R}_k$ is modelled such that $f_i$ is finite, or in other words, a partial sequence. As for PTWP $^e$ , the concept of type $\iota\to\iota$ writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP $^e$ -computable functionals coincide with those definable in ${\cal PR}^{\omega e}$ plus a constant for sequential minimisation. In particular, the functionals definable in ${\cal PR}^{\omega e}$ denoted ${\cal R}^{\omega e}$ can be characterised by a subclass of PTWP $^e$ -computable functionals denoted ${\rm PPR}^{\omega e}$ . Moreover, hierarchies of strictly increasing classes ${\cal R}^{\omega e}_n$ in the style of Heinermann and complexity classes ${\rm PPR}^{\omega e}_n$ are introduced such that $\forall n\ge 0. {\cal R}^{\omega e}_n ={\rm PPR}^{\omega e}_n$ . These results extend those for ${\cal PR}^\omega$ and PTWP [Nig94]. Finally, scvr is employed to define for each type $\sigma$ the enumeration functional $E^\sigma$ of all finite elements of $D_\sigma$. (shrink)