A restricted computation model on Scott domains and its partial primitive recursive functionals |
| |
Authors: | Karl-Heinz Niggl |
| |
Institution: | Mathematisches Institut der Ludwig–Maximilians–Universit?t München, Theresienstra{?}e 39, D-80333 München, Germany. niggl@rz.mathematik.uni-muenchen.de, DE
|
| |
Abstract: | The paper builds on both a simply typed term system 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 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 and PTWP are studied that are closed under scvr. The twist are certain type 1 G?del recursors
for simultaneous partial primitive recursion. Formally, denotes a function , however, is modelled such that is finite, or in other words, a partial sequence. As for PTWP, the concept of type
writable variables is introduced, providing the possibility of creating and manipulating partial sequences. It is shown that the PTWP-computable functionals coincide with those definable in plus a constant for sequential minimisation. In particular, the functionals definable in denoted can be characterised by a subclass of PTWP-computable functionals denoted . Moreover, hierarchies of strictly increasing classes in the style of Heinermann and complexity classes are introduced such that . These results extend those for and PTWP Nig94]. Finally, scvr is employed to define for each type the enumeration functional
of all finite elements of .
Received January 30, 1996 |
| |
Keywords: | Mathematics Subject Classification (1991):03D15 03D20 03D65 03D99 68Q05 68Q10 68Q15 68Q55 68Q99 |
本文献已被 SpringerLink 等数据库收录! |
|