A restricted computation model on Scott domains and its partial primitive recursive functionals

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

Abstract

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$

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,593

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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.

Analytics

Added to PP
2013-11-23

Downloads
11 (#975,863)

6 months
2 (#668,348)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

References found in this work

No references found.

Add more references