Informatics Report Series



Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Title:The sequentially realizable functionals
Authors: John Longley
Date: 2002
Publication Title:Annals of Pure and Applied Logic
Publication Type:Journal Article Publication Status:Published
Volume No:117 Page Nos:1-93
We consider a notion of sequential functional of finite type, more generous than the familiar notion embodied in Plotkin's language PCF. We study both the ``full'' and ``effective'' 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 effective scenarios) every finite type can be obtained as a retract of the pure type 2, and hence that all elements of the effective type structure are definable 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.
Links To Paper
1st Link
Bibtex format
author = { John Longley },
title = {The sequentially realizable functionals},
journal = {Annals of Pure and Applied Logic},
publisher = {Elsevier},
year = 2002,
volume = {117},
pages = {1-93},
doi = {10.1016/S0168-0072(01)00110-5},
url = {},

Home : Publications : Report 

Please mail <> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh