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)

We study a notion ofpartial primitive recursion (p.p.r.) including the concept ofparallelism in the context of partial continuous functions of type level one in the sense of [Krei], [Sco82], [Ers]. A variety of subrecursive hierarchies with respect top.p.r. is introduced and it turns out that they all coincide.

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)