The recursion hierarchy for PCF is strict

Autor: John Longley

Publikováno v: Logical Methods in Computer Science, Vol Volume 14, Issue 3 (2018)

We consider the sublanguages of Plotkin's PCF obtained by imposing some bound k on the levels of types for which fixed point operators are admitted. We show that these languages form a strict hierarchy, in the sense that a fixed point operator for a

Externí odkaz: https://doaj.org/article/3e088bd17f6b4e7c8000fd529671af68

Bar recursion is not computable via iteration

Autor: John Longley

Publikováno v: Longley, J 2019, ' Bar recursion is not computable via iteration ', Computability, pp. 1-44 . https://doi.org/10.3233/COM-180200

We show that the bar recursion operators of Spector and Kohlenbach, considered as third-order functionals acting on total arguments, are not computable in Goedel's System T plus minimization, which we show to be equivalent to a programming language w

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::bb84dcecaf86c5c686715070fec6c9b1
http://arxiv.org/abs/1804.07277

Notions of computability at higher types I

Autor: Carol Wood, John Longley, Stevo Todorcevic, Alexander Razborov, Rene Cori

Publikováno v: Logic Colloquium 2000: Proceedings of the Annual European Summer Meeting of the Association for Symbolic Logic, held in Paris, France, July 23–31, 2000

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::2edb5ffa154fea35e4e37889376d490e
https://doi.org/10.1017/9781316755884.004

Some Programming Languages Suggested by Game Models (Extended Abstract)

Autor: John Longley

Publikováno v: MFPS
Longley, J 2009, ' Some Programming Languages Suggested by Game Models (Extended Abstract) ', Electronic Notes in Theoretical Computer Science, vol. 249, pp. 117-134 . https://doi.org/10.1016/j.entcs.2009.07.087

We consider a simple and well-known category of alternating games (also known as sequential data structures) and several categories derived from it. In each case, we present an extension of Plotkin's language FPC (or a suitable linearization thereof)

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::c56690f983e82dce23c0b725c8a3b911
https://doi.org/10.1016/j.entcs.2009.07.087

Theory of λ-Algebras

Autor: John Longley, Dag Normann

Publikováno v: Higher-Order Computability ISBN: 9783662479919

In the previous chapter, broadly speaking, we axiomatized and studied higher-order models as combinatory algebras—that is, as structures possessing elements k and s satisfying certain axioms. In the present chapter, we shall consider models from th

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ccb8394d9e9c982ef0450989f035d6fd
https://doi.org/10.1007/978-3-662-47992-6_4