The Journal of Symbolic Logic

Research Article

The hereditary partial effective functionals and recursion theory in higher types   1

G. Longoa1 and E. Moggia1

a1 Università di Pisa, Pisa, Italy

Abstract

A type-structure of partial effective functionals over the natural numbers, based on a canonical enumeration of the partial recursive functions, is developed. These partial functionals, defined by a direct elementary technique, turn out to be the computable elements of the hereditary continuous partial objects; moreover, there is a commutative system of enumerations of any given type by any type below (relative numberings).

By this and by results in [1] and [2], the Kleene-Kreisel countable functionals and the hereditary effective operations (HEO) are easily characterized.

(Received July 19 1983)

Footnotes

1   Research partially supported by Min. P.I. (fondi 60%) and, in part, by Consiglio Nazionale delle Ricerche (Comitato per la Matematica).