Logic of Interaction and Information Flow

我们目前对计算的理解已经大大超出了原来孤立于环境的数值计算的“封闭世界”图景。在Internet和Web的时代，以及现在的普适性和无处不在的计算，很明显，多个代理之间的交互和信息流是计算的基本特征。描述或设计的标准单元，无论是在过程调用-返回接口或硬件组件的微观尺度上，还是在Web上的软件代理的宏观尺度上，都成为一个过程或代理，其行为的本质表明它通过某些定义的接口与环境进行交互。这些发展需要引入新的交互计算数学模型。传统的观点认为，一个程序被看作是计算一个函数或从输入到输出的关系，这种观点已经不再充分：互联网计算的是什么功能？其中一个引人注目的想法是将系统和环境之间的互动概念化为两人游戏。指定系统在面对环境的所有可能行动时应该如何行动的程序便是玩家对应于系统的策略。这些想法导致了游戏语义的发展，它既为分析许多不同形式的计算提供了强大的工具，又为逻辑本身带来了新的视角。例如，考虑“模仿猫策略”，我们可以通过逻辑的力量击败国际象棋大师。其理念是我们在两个棋盘上与两位大师对抗，一个是白棋，一个是黑棋（对应于“A或非A”）。通过简单地来回复制动作，我们最终会让一个大师对抗另一个大师——因此我们的对手也会做得很好！这是一种“动态同义重复”：我们通过简单的复制过程来达到强烈的逻辑效果。注意，只有从这个和相关的思想中产生的考虑才会导致在计算和逻辑方面的强大应用，惊人的联系也出现在几何思想中，与结和辫子有关，以及纠缠量子系统中的信息流。因此，该建议的目的之一是建立一个涵盖所有这些例子和更多的交互和信息流的统一理论。另一种方法是将这种“动态”或“内在”方法与更传统的交互逻辑方法联系起来，并找到结合它们的有效方法。

Our current understanding of computation has widened enormously beyond the original ``closed world'' picture of numerical calculation in isolation from the environment. In the age of the Internet and the Web, and now of pervasive and ubiquitous computing, it has become clear that interaction and information flow between multiple agents are essential features of computation. The standard unit of description or design, whether at a micro-scale of procedure call-return interfaces or hardware components, or a macro-scale of software agents on the Web, becomes a process or agent, the essence of whose behaviour ishow it interacts with its environment across some defined interface.These developments have required the introduction of novel mathematical models of interactive computation. The traditional view whereby a program is seen as computing a function or relation from inputs to outputs is no longer sufficient: what function does the Internet compute?One of the compelling ideas which has taken root is toconceptualize the interaction between the System and the Environment as a two-person game. A program specifying how the System should behave in the face of all possible actions by the Environment is then a strategy for the player corresponding to the System.These ideas have led to the development of Game semantics, which both provides powerful tools for analyzing many different forms of computation, and leads to new perspectives on logic itself.For example, consider the ``copy-cat strategy'', whereby we can beat a Grand-Master at chess, by the power of logic. The idea is that we play against two Grand-Masters on two boards, one as White and one as Black (corresponding to ``A or not A''). By simply copying moves back and forth, we end up playing one grand-master off against the other --- and hence do as well as our opponents! This is a kind of ``dynamic tautology'': we achieve a strong logical effect by a simple copying process. Note only do the considerations arising from this and related ideas lead to powerful applications in computation and logic, striking connections are also emerging to geometric ideas, related to knots and braids, and to information flow in entangled quantum systems.Thus one aim of the proposal is build a unified theory of interaction and information flow covering all these examples and more. Another to is to connect this ``dynamic'' or ``intrinsic'' approach to more traditional approaches to logics of interaction, and indeed to find useful ways of combining them.