The sequentially realizable functionals

✍ Scribed by John Longley

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 598 KB
• Volume: 117
• Category: Article
• ISSN: 0168-0072
• DOI: 10.1016/s0168-0072(01)00110-5

✦ Synopsis

We consider a notion of sequential functional of ÿnite type, more generous than the familiar notion embodied in Plotkin's language PCF. We study both the "full" and "e ective" partial type structures arising from this notion of sequentiality. The full type structure coincides with that given by the strongly stable model of Bucciarelli and Ehrhard; it has also been characterized by van Oosten in terms of realizability over a certain combinatory algebra. We survey and relate several known characterizations of these type structures, and obtain some new ones. We show that (in both the full and e ective scenarios) every ÿnite type can be obtained as a retract of the pure type 2, and hence that all elements of the e ective type structure are deÿnable in PCF extended by a certain universal functional H . We also consider the relationship between our notion of sequentially computable functional and other known notions of higher-type computability.