Hereditarily Sequential Funtionals: A Game-Theoretic Approach to Sequentiality.

Abstract

The aim of this thesis is to give a new understanding of sequential computations in higher types. We present a new computation model for higher types based on a game describing the interaction between a functional and its arguments. The functionals which may be described in this way are called hereditarily sequential. We show that this computation model captures exactly the notion of computability in higher types introduced by Kleene in his pioneering work starting 1959. We study the order structure of the hereditarily sequential functionals and discuss the occurring difficulties. These functionals form a fully abstract model for PCF and we discuss which problems remain still open for a satisfactory solution to the full abstraction problem of PCF.

Zusammenfassung

Ziel dieser Arbeit ist es, eine neue Beschreibung sequentieller Berechnungen in höheren Typen zu geben. Wir stellen dazu ein neues Berechnungsmodell für höhere Typen vor, in dem die Interaktion zwischen einem Funktional und seinen Argumenten durch ein Spiel beschrieben wird. Die so beschreibbaren Funktionale werden vererbt sequentiell genannt. Wir zeigen, daß mit diesem Berechnungsmodell genau der Begriff von Berechenbarkeit in höheren Typen charakterisiert wird, der von Kleene in seinen Arbeiten ab 1959 untersucht wurde. Wir untersuchen die Ordnungsstruktur der vererbt sequentiellen Funktionale und diskutieren die auftretenden Probleme. Diese Funktionale bilden ein vollabstraktes Modell für PCF und wir diskutieren die Probleme die für eine zufriedenstellende Lösung des Vollabstraktheitsproblems für PCF noch bestehen bleiben.