计算与交互 交互的机器模型 图灵机TM或冯·诺依曼计算机体系结构不适合作 为交互的机器模型 l.顺序交互机SM(sequential interactive machine) SIM:M=(S,I,f) S:可枚举的状态集，：可枚举的输入串集 f:SxI→SxO的TM可计算函数，即(s,)-→(s',o 从S-1到S的状态转移：原子的/O序对(，O -} 输入的不确定性：动态输入i,不可预测（依赖于01） 输出的确定性：0由，确定（很容易扩展到0不确定） SIM的行为由IVO流(1,01)，(2,02)，(G3,03),…刻画
计算与交互 • 交互的机器模型 图灵机TM或冯·诺依曼计算机体系结构不适合作 为交互的机器模型 1. 顺序交互机SIM(sequential interactive machine) – SIM: M = (S, I, f ) S: 可枚举的状态集，I: 可枚举的输入串集 f : SI → SO的TM可计算函数，即(s, i)→ (s , o) – 从sk-1到sk的状态转移：原子的I/O序对(ik , ok ) – 输入的不确定性: 动态输入ik不可预测(依赖于ok-1 ) – 输出的确定性: ok由ik确定(很容易扩展到ok不确定) – SIM的行为由I/O流(i1 , o1 ), (i2 , o2 ), (i3 , o3 ), …刻画17
计算与交互 ·交互的机器模型 2.持久图灵机PTM:., 表达能力等价于SM 3.多带交互机MM: 表达能力大于SM 但都不足以作为先前提到的多种交互计算重要范 例的统一机器模型 能描述交互的演算 一π演算是对前述挑战的最成功回应 π演算的两个重要特色：行为（或观察)等价的概 念，以及对交互行为模式分类的新的类型理论 π演算已经被应用到编程语言设计、分布式系统的 分析和验证等领域，产生了广泛的影响
计算与交互 • 交互的机器模型 2. 持久图灵机PTM：…，表达能力等价于SIM 3. 多带交互机MIM：…，表达能力大于SIM 但都不足以作为先前提到的多种交互计算重要范 例的统一机器模型 • 能描述交互的演算 – 演算是对前述挑战的最成功回应 – 演算的两个重要特色：行为（或观察）等价的概 念，以及对交互行为模式分类的新的类型理论 – 演算已经被应用到编程语言设计、分布式系统的 分析和验证等领域，产生了广泛的影响 18
从归纳到余归纳 顺序交互的数学模型 在计算表达力上从算法到顺序交互的延伸在数学 上表现为一系列的延伸 在集合表达力上：从良基集到非良基集的延伸 非良基集作为无限流的顺序行为的形式模型 -在数学对象定义的表达力上：从归纳到余归纳的 延伸 例如，表达了从字符串到无限字符流的转变 这是算法到交互转变的基础 在代数表达力上：从代数到余代数的延伸 余代数为无限流的演算提供工具
• 顺序交互的数学模型 在计算表达力上从算法到顺序交互的延伸在数学 上表现为一系列的延伸 – 在集合表达力上：从良基集到非良基集的延伸 非良基集作为无限流的顺序行为的形式模型 – 在数学对象定义的表达力上：从归纳到余归纳的 延伸 例如，表达了从字符串到无限字符流的转变， 这是算法到交互转变的基础 – 在代数表达力上：从代数到余代数的延伸 余代数为无限流的演算提供工具 从归纳到余归纳 19