Archive for Mathematical Logic 37 (7):443-481 (1998)

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$
Keywords Legacy
Categories (categorize this paper)
DOI 10.1007/s001530050108
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,256
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.
< I> M_< Sup> Ω Considered as a Programming Language.Karl-Heinz Niggl - 1999 - Annals of Pure and Applied Logic 99 (1):73-92.

Add more citations

Similar books and articles

Subrecursive Functions on Partial Sequences.Karl-Heinz Niggl - 1999 - Archive for Mathematical Logic 38 (3):163-193.
Subrecursive Hierarchies on Scott Domains.Karl-Heinz Niggl - 1993 - Archive for Mathematical Logic 32 (4):239-257.
Program Extraction for 2-Random Reals.Alexander P. Kreuzer - 2013 - Archive for Mathematical Logic 52 (5-6):659-666.
Models with the Ω-Property.Roman Kossak - 1989 - Journal of Symbolic Logic 54 (1):177-189.


Added to PP index

Total views
7 ( #1,011,543 of 2,419,604 )

Recent downloads (6 months)
1 ( #542,199 of 2,419,604 )

How can I increase my downloads?


My notes