Interactive observability in Ludics: The geometry of tests

摘要

Ludics [J.-Y. Girard, Locus solum, Math. Structures in Comput. Sci, 11 (2001) 301-506] is a recent proposal of analysis of interaction, developed by abstracting away from proof-theory. It provides an elegant, abstract setting in which interaction between agents (proofs/programs/processes) can be studied at a foundational level, together with a notion of equivalence from the point of view of the observer. An agent should be seen as some kind of black box. An interactive observation on an agent is obtained by testing it against other agents. In this paper we explore what can be observed interactively in this setting. In particular, we characterize the objects that can be observed in a single test: the primitive observables of the theory. Our approach builds on an analysis of the geometrical properties of the agents, and highlights a deep interleaving between two partial orders underlying the combinatorial structures: the spatial one and the temporal one.