新型计算模型和顺序交互的数学 计算机科学导论第九讲 计算机科学技术学院 陈意云 0551-63607043, yiyun@ustc.edu.cn http://staff.ustc.edu.cn/~yiyun/

课 程 内 容 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何比较模型的表达能力 2. 程序理论关心的问题 给定模型M，如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计、形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源 本讲座概要介绍交互计算的特点及相关的一些数学知识 2

讲 座 提 纲 基本知识 交互计算 从归纳到余归纳 从代数到余代数 人机物三元世界、云计算、未来网、物联网、泛在网、图灵机计算模型、网域计算模型 交互计算 经典计算与交互计算、交互的特点、交互的机器模型、能描述交互的演算 从归纳到余归纳 良基集、非良基集、余归纳、互模拟 从代数到余代数 笛卡尔积, 可区分并, 余代数, 代数和余代数的区别 3

基 本 知 识 人机物三元世界 由计算机网络世界(也称计算世界, cyber world)、物理世界和人类社会组成的人机物协同社会，是多人、多机和多物组成的动态开放并协同工作的网络社会 计算机科学是研究人机物三元世界中计算现象这个共同主线的科学 站在三元世界的高度，有助于理解云计算、未来网、物联网、泛在网(ubiquitous network)的新技术趋势

基 本 知 识 云计算 把资源集中于互联网上的数据中心，由这种云中心提供应用层、平台层和基础设施层的集中服务 强调信息资源的聚集、优化、动态分配和回收，通过提高数据中心的效率，解决传统IT系统的零散性带来的低效率，降低信息化成本、降低能耗 向公众提供一种新的高效计算模式，兼有互联网服务的便利与廉价和大型计算机的能力 云计算可为物联网和泛在网提供后端处理能力与应用平台

基 本 知 识 未来网（未来互联网，post-IP network） 基于TCP/IP协议的互联网随着其广泛应用，在可扩展性、移动性、安全性、服务质量和可靠性等方面都暴露出本质缺陷 近十多年来渐进式的改进未能从根本上解决问题 美国和欧盟等已开展“从零开始”的革命方式研究未来互联网 未来网可为云计算、物联网和泛在网提供更加高效安全的网络基础技术

基 本 知 识 物联网 实现物物互联的网络 与互联网的区别：物物互联，物机互联，而不是局限于机机互联 实现对物理世界（包括自然界和人造物）的精准感知，感知信息的实时或及时传输，针对物理世界限制的处理与决策，以及对物理世界的控制，提供高效智能的应用服务 更高层次：通过独立个体之间的局部的即时交互和分布式智能，使物体具有自组织、自计算和自反馈功能，实现物物之间的智能交互

基 本 知 识 泛在网 是指基于个人和社会的需求，实现人与人、人与物、物与物之间按需进行的信息获取、传递、存储、认知、决策和使用等服务 具有超强的环境感知、内容感知及智能性 环境感知(environment perception)：指系统具有周围环境 参数的采集、语义表达、语义查询解析和语义推理的能力 内容感知(content aware)的网络服务：意在更细致地感知  终端（PC、手机、平板电脑等）  网络（3G，Wifi等移动网络）  业务类型（游戏、视频、电子商务、微博等） 的不同需求, 提供更有针对性的解决方案和更有价值的服务

基 本 知 识 泛在网 是指基于个人和社会的需求，实现人与人、人与物、物与物之间按需进行的信息获取、传递、存储、认知、决策和使用等服务 具有超强的环境感知、内容感知及智能性 通过多种联网的智能人机交互设备，为个人和社会提供无所不在的信息服务和应用

基 本 知 识 区分性概括 未来网：强调对当今互联网的变革，是未来信息化的网络基础 云计算：一种新的应用模式，强调应用层信息的综合处理，可作为物联网后端处理和应用平台 物联网：强调对物感知和物物互联, 方便人类对物理世界的感知和控制，是走向泛在网的重要一步 泛在网：对未来信息社会的综合预见，是上述这些概念的集成

基 本 知 识 图灵机计算模型 把物理世界数字化，建立数学模型，通过计算和数据处理方法，对自然界存在的规律进行模拟仿真；计算类应用和数据处理应用都是遵循这样的计算模型 按照“输入计算输出”的过程，产生的所有结果都是可以预知的 它是一个计算世界（computation world），是对人类认知的一种数字化。这个数字世界与人类社会、物理世界是正交的

基 本 知 识 网域计算模型 把信息化扩大到人类社会的一种计算模型 通过移动数据的方式，把人类社会中真实的工作与生活搬到计算机网络空间（cyberspace, 简称网域），即网域可以看成是对人类社会的一个映射 Cyberspace is the national environment in which communication over computer networks occurs. 其基础是通过互联网、上网本(netbook)、智能手机和网络设备等手段实现的人与人之间的通信 例如，社会计算和舆情分析等都是通过对网域空间的计算来发现人类社会的规律

基 本 知 识 网域计算模型 网域空间的计算与图灵机计算有本质不同 不存在“停机”问题 算法不是独立的, 而是交互算法的网络(a network of interacting algorithms) 存在涌现现象(emergent phenomena)，即在混沌的网上世界中能产生新的知识与智能

计算与交互 经典计算（简称计算） 交互计算（简称交互） 计算主体和它的环境之间是一种简单的接口，即按照“输入计算输出”的过程完成所规定任务 计算体现出从输入到输出的函数性 交互计算（简称交互） 交互计算是在完成任务的过程中包括了与外部世界通信的计算 计算主体具有与不受它控制的外部环境交互输入 和输出的动作

计算与交互 交互的特点 基于交互的模型和基于图灵机的算法模型的区别 交互任务并非都能简化为函数，例如永远运行的操作系统不能由算法模拟的 在交互模型中，计算环境是模型的一部分，并且通过动态地向计算系统或计算主体提供输入并消费其输出值而体现为交互计算中活跃的一部分 在交互模型中，其中的计算可以是并行的，一个计算主体可以和它的环境以及其他计算主体并行工作

计算与交互 交互的影响 交互为计算现象提供一种新的概念模型, 它强调交互而不是算法。并行、分布、反应式(reactive)、嵌入式、面向部件、面向主体和面向服务的系统都是奠定此概念模型的重要范例 所有新型计算的本质特点是交互，交互是现代计算的问题和复杂性的根源 交互与计算的统一理论是计算机科学的基础，以支撑计算机科学的整套理论体系 如何为经典计算和现代计算建立统一的理论框架?这是近几十年来计算机科学面临的重大挑战

计算与交互 交互的机器模型 图灵机TM或冯·诺依曼计算机体系结构不适合作 为交互的机器模型 1. 顺序交互机SIM(sequential interactive machine) SIM: M = (S, I, f ) S: 可枚举的状态集，I: 可枚举的输入串集 f : SI  SO的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), …刻画

计算与交互 交互的机器模型 能描述交互的演算 2. 持久图灵机PTM：…，表达能力等价于SIM 3. 多带交互机MIM：…，表达能力大于SIM 但都不足以作为先前提到的多种交互计算重要范 例的统一机器模型 能描述交互的演算 演算是对前述挑战的最成功回应 演算的两个重要特色：行为（或观察）等价的概 念，以及对交互行为模式分类的新的类型理论 演算已经被应用到编程语言设计、分布式系统的 分析和验证等领域，产生了广泛的影响

从归纳到余归纳 顺序交互的数学模型 在计算表达力上从算法到顺序交互的延伸在数学 上表现为一系列的延伸 在集合表达力上：从良基集到非良基集的延伸 非良基集作为无限流的顺序行为的形式模型 在数学对象定义的表达力上：从归纳到余归纳的 延伸 例如，表达了从字符串到无限字符流的转变， 这是算法到交互转变的基础 在代数表达力上：从代数到余代数的延伸 余代数为无限流的演算提供工具

从归纳到余归纳 非良基集 良基关系 集合A上的一个关系是良基的，若不存在A上元 素的无穷递减序列a0  a1  a2 …（a  b iff b  a） 良基集 直观解释：不存在无穷递减序列的集合 非良基关系 集合A上的一个关系是非良基的，若存在A上元 素的无穷递减序列 直观解释：不遵守上述对良基集的限制的集合

从归纳到余归纳 解释两个记号：笛卡尔积 对两个集合X和Y，其笛卡儿积是如下的序对集合 X  Y  {x, y | xX , yY } 射影函数Proj1: X  Y  X和Proj2: X  Y  Y满足 等式 (1) Proj1( x, y) = x (2) Proj2( x, y) = y

从归纳到余归纳 解释两个记号：可区分并（又称和、余积） 对两个集合X和Y，其可区分并是如下的序对集合 X +Y  {0, x | xX }  {1, y | yY } 内射函数(又称余射影函数)InLeft : X  X +Y和 InRight : Y  X +Y 满足等式  InLeft(x) = 0, x  InRight(y) = 1, y

从归纳到余归纳 集合方程的最小解与最大解 下面集合方程的最小解是A上的字符串集 t  unit + (A  t)  t, A和unit分别是集合变量, 字符集和某个特殊 元素的集合；unit的元素代表空集  “”表示两边同构而不是相等 下面集合方程的最大解是A上的无限字符流集 t  (A  t) (与上面方程比较, 没有unit ) 体现出延伸出来的概念与原来概念的对偶性 对偶性在代数和余代数上体现得最清楚

从归纳到余归纳 归纳与余归纳的比较 1. 归纳 是构造主义的方法，用它定义数据时，可分解成 三个基本步骤：基本情况、迭代规则和最小化条件 例如，数据集A上的有限表集可归纳地定义如下 (1) 基础情况：nil(空表)是有限表 (2) 迭代规则：若aA且是有限表，则cons(a, )是有限表 (3) 最小化条件：此外, 有限表集中不含其它元素 最小化规则指所定义的集合是满足(1)和(2)两条 约束的最小集合，无任何垃圾在其中

从归纳到余归纳 归纳与余归纳的比较 1. 归纳 可计算函数 f :X Y 在两个层次上是归纳的 例：字符串集的定义: t  unit + (A  t)的最小解 (2) 归纳定义的动态计算： f 的计算过程是归纳 定义的 图灵机也是类似地通过归纳定义的状态转换步骤, 对归纳定义的串进行变换，图灵机的局限也是源于 其基于归纳

从归纳到余归纳 归纳与余归纳的比较 2. 余归纳 用余归纳定义数据时，可分解成两个基本步骤：迭代规则和最大化条件。与归纳相比，它删去基 础情况，修改迭代规则，用最大化取代最小化 例如, 数据集A上的无限表集可余归纳地定义如下 (1) 迭代规则：若aA且是无限表，则cons(a, )是无限表 (2) 最大化条件：数据集A上的无限表集是满足迭代规则的最大集合

从归纳到余归纳 归纳与余归纳的比较 2. 余归纳 最大化条件表示所有未被迭代规则(1)排除的元素 都被包含在所定义的集合中，即该集合中任何无限 表都可以通过应用规则(1)若干次而得到 交互计算在两个层次上是余归纳的 (1) 余归纳定义的静态值域 例，无限字符流集的定义：t  (A t)的最大解 (2) 余归纳定义的动态下一步动作(后面有例子)

从归纳到余归纳 归纳与余归纳的比较 3. 例： 有限表的构造算子(constructor)有nil和cons 无限表的构造算子仅有cons 两种表都有观察算子head和运算算子tail，合称为 解构算子(destructor) 并且都有性质 head(cons(a, )) = a tail(cons(a, )) =  两者分别对应  集合方程t  unit + (A  t)的最小解  集合方程t  (A  t)的最大解

从归纳到余归纳 归纳和余归纳定义的函数的比较 1. 归纳定义的函数 在计算有限表表长的函数length的归纳定义中， length(nil) = 0 length(cons(a, )) = 1 + length() 怎样给出一个函数在余归纳定义集合上的余归纳 定义？

从归纳到余归纳 归纳和余归纳定义的函数的比较 2. 余归纳定义的函数 考虑字符集A上的无限表，现在有函数f : A  A 定义f 的拓展函数ext(f )，它把f 应用到无限表的 每个元素，得到新的无限表ext(f )() 余归纳定义即定义解构算子在每个ext(f )()上的值 head(ext(f )()) = f (head()) tail(ext(f )()) = ext(f )(tail()) 在这些等式的左边，f 出现在解构算子的“里面” 在归纳定义中，length出现在构造算子的“外面”： length(nil) = 0, length(cons(a, )) = 1 + length()

从归纳到余归纳 互模拟 例：无限表上的odd运算 odd：忽略所有偶数位置的元素后构成的无限表 head(odd()) = head() tail(odd()) = odd(tail(tail())) 用等式演算可得 head(tail(odd())) = head(odd(tail(tail()))) = head(tail(tail())) 不难证明，对所有的自然数n head(tail(n) (odd())) = head(tail(2n) ())

从归纳到余归纳 互模拟 例：无限表上的odd运算 odd：忽略所有偶数位置的元素后构成的无限表 head(odd()) = head() tail(odd()) = odd(tail(tail())) 顺便说一句：  从计算的角度，欲求head(odd()) 的结果，不能等odd()的结果算出后，再交给head函数 (不终止)  须用惰性计算的方法：在head函数需要下一个数据时，odd才计算下一个数据并提供给head

从归纳到余归纳 互模拟 怎样证明余归纳定义的数据和函数的性质 1、某些性质可以用归纳法来证明，例如证明 head(tail(n) (odd())) = head(tail(2n) ()) 2、互模拟——余归纳证明专用方法 从数学上刻画系统（如对象、进程等）行为等价 这个直观概念 指两个系统从观测者角度看，可以互相模拟对方 的行为

从归纳到余归纳 互模拟 通过无限表上的例子来解释 先前已定义odd head(odd()) = head() tail(odd()) = odd(tail(tail())) 定义even even = odd  tail 定义merge head(merge(, )) = head() tail(merge(, )) = merge(, (tail())

从归纳到余归纳 互模拟 基于互模拟证明merge(odd(), even()) =  互模拟是满足下面条件的关系R： 若,  R，则 head() = head() 并且 tail(), tail() R 基于互模拟的余归纳证明原理是： 对互模拟关系R，若,  R，则 =  按上述原理，先定义关系 R ={ merge(odd(), even()),  | 是无限表 } 只要证明R是互模拟关系即可

从归纳到余归纳 互模拟 根据tail(merge(, )) = merge(, (tail()) 第一个条件的证明 head(merge(odd(), even())) = head(odd()) = head() 第二个条件的证明 需证tail(merge(odd(), even())), tail()也在R中 1. tail(merge(odd(), even())) = merge(even(), tail(odd())

从归纳到余归纳 互模拟 根据even = odd  tail 和 tail(odd()) = odd(tail(tail())) 第一个条件的证明 head(merge(odd(), even())) = head(odd()) = head() 第二个条件的证明 需证tail(merge(odd(), even())), tail()也在R中 1. tail(merge(odd(), even())) = merge(even(), tail(odd()) = merge(odd(tail()), odd(tail(tail())))

从归纳到余归纳 互模拟 根据even = odd  tail 第一个条件的证明 head(merge(odd(), even())) = head(odd()) = head() 第二个条件的证明 需证tail(merge(odd(), even())), tail()也在R中 1. tail(merge(odd(), even())) = merge(even(), tail(odd()) = merge(odd(tail()), odd(tail(tail()))) = merge(odd(tail()), even(tail()))

从归纳到余归纳 互模拟 因为merge(odd(), even()), 在R中, 把代换成tail()可得 第一个条件的证明 head(merge(odd(), even())) = head(odd()) = head() 第二个条件的证明 需证tail(merge(odd(), even())), tail()也在R中 1. tail(merge(odd(), even())) = merge(even(), tail(odd()) = merge(odd(tail()), odd(tail(tail()))) = merge(odd(tail()), even(tail())) 2. merge(odd(tail()), even(tail())), tail()在R中, 故tail(merge(odd(), even())), tail()也在R中

从归纳到余归纳 互模拟 利用归纳和等式演算，也可以证明 merge(odd(), even()) =  但没有这么简洁 需用归纳法先证明下面几个等式： head(tail(n)(odd())) = head(tail(2n)()) head(tail(2n)(merge(, ))) = head(tail(n)()) head(tail(2n+1)(merge(, ))) = head(tail(n)()) 然后利用等式演算证明 head(tail(n)(merge(odd(), even()))) = head(tail(n)())

从代数到余代数 笛卡尔积（先前已给出） 对两个集合X和Y，其笛卡儿积是如下的序对集合 X  Y  {x, y | xX , yY } 射影函数Proj1: X  Y  X和Proj2: X  Y  Y满足 等式  Proj1(x, y) = x  Proj2(x, y) = y

从代数到余代数 笛卡尔积 对任意函数f : Z  X和g : Z  Y, 存在唯一的“配 对”函数f, g: Z  X  Y 使得 Proj1 f, g = f 且Proj2 f, g = g 即对zZ，f, g(z) = f (z), g(z)  X  Y 注：f, g看成函数名 二元积的这些性质在范畴论中 可以用交换图表(右图)表示 可推广到n元积的情况 Y Z f, g X  Y X Proj1 g f Proj2

从代数到余代数 可区分并（又称和、余积） （先前已给出） 对两个集合X和Y，其可区分并是如下的序对集合 X +Y  {0, x | xX }  {1, y | yY } 内射函数(又称余射影函数)InLeft : X  X +Y和 InRight : Y  X +Y 满足等式  InLeft(x) = 0, x  InRight(y) = 1, y

从代数到余代数 可区分并（又称和、余积） 对任意函数f : X  Z和g : Y  Z, 存在唯一的余配 对函数[f, g]: X +Y  Z使得 [f, g]  InLeft = f 且[f, g]  InRight = g 即对wX +Y, [f, g](w) = 二元和的这些性质在范畴论中 可以用交换图表(右图)表示 可推广到n元和的情况 注: [f, g]看成函数名 f (x), w = 0, x g(y), w = 1, y Y Z [f, g] X + Y X InLeft g f InRight

从代数到余代数 笛卡尔积和可区分并 它们交换图表的区别是：箭头正好相反 可区分并用于描述代数, 笛卡尔积用来描述余代数 从它们交换图表的对偶性来体会代数和余代数的关系 这是介绍这部分的目的 Y Z f, g X  Y X Proj1 g f Proj2 Y Z [f, g] X + Y X InLeft g f InRight

从代数到余代数 自然数代数 自然数N 上的零和后继函数 0 : unit  N （0是归纳定义的基础情况） S : N  N （S是构造算子） 构成函子F的代数N , [0, S] : F(N ) N , 其中N 称为载体，F(N ) = unit+N 。函数[0, S]称为该代数的代数结构 函子是范畴之间保结构的 的映射，深入了解需要 范畴论的知识 N [0, S] unit+N unit InLeft S InRight

从代数到余代数 一个简单的余代数 两个集合U (状态集)和 A(可观察数据集) 和函数 value : U  A （value是观察算子） next : U  U （next是运算算子） 构成函子G的余代数 U , value, next: U  G(U) , 其中U称为该余代数的载体， G(U) = A  U。函数 value, next称为该余代数的 余代数结构 由于余代数经常描述 动态系统，载体也叫做 状态空间 U value, next A  U A Proj1 next value Proj2

从代数到余代数 例：有两个按键value和next的机器 按value键时不影响机器内部状态，并产生数据集A的某个元素(可见属性)，连续按value键产生同样的结果 按next键时机器转移到另一个状态，该状态的性质可通过按value键来观察 该机器可以用状态空间U上的下述余代数来描述 value, next : U  A  U 其中value, next由两个函数 value : U  A和next : U  U组成 48

从代数到余代数 例：有两个按键value和next的机器 该机器可以用状态空间U上的下述余代数来描述 value, next : U  A  U 其中value, next由 value: U  A和next: U  U组成 连续地交替按next键和value键，可以产生无限序列(a1, a2, …) 它可以看成N  A上的一个函数，其中 ai = value(next(i)(u)) A 若u1, u2U给出同样的可观察序列，则u1和u2从观察角度不可区分 49

从代数到余代数 余代数和代数的区别 本质上这是构造和观察之间的区别 代数由载体集合U和射入U的函数a : F(U)  U 组成，它告知怎样构造U的元素 余代数由载体集合U和逆向的函数c : U  F(U)组成，此时不知道怎样形成U的元素，仅有作用在U上的操作，它给出关于U的某些信息 50

小 结 本讲座小结 研究方向 从三元世界的高度概述地介绍云计算、未来网、物联网和泛在网及计算模型 小 结 本讲座小结 从三元世界的高度概述地介绍云计算、未来网、物联网和泛在网及计算模型 强调现代计算与经典计算最主要的区别之一是交互性 介绍顺序交互的数学模型 研究方向 如何为经典计算与新型计算建立统一的理论框架 各种交互计算的机器模型 各种交互计算的数学模型 51

小 结 参考文献 孙凝晖等，海计算：物联网的新型计算模型，中 国计算机学会通讯，6(7)，2010.7 小 结 参考文献 孙凝晖等，海计算：物联网的新型计算模型，中 国计算机学会通讯，6(7)，2010.7 曹爱文等译, 计算机数学, 清华大学出版社, 2010 林惠民等译，移动与通信系统：演算，清华大学 出版社，2009 Goldin, D; Smolka, S. A; Wegner, P.(Eds.), Interactive Computation: The New Paradigm, 2006 Bart Jacobs and Jan Rutten. A Tutorial on Coalgebras and Coinduction. The Hyper bulletin of the European Association for Theoretical Computer Science, 62: 222-259 （本讲座的理论部分源于此） 52

小 结 相关课程 网络计算与高效算法（研）、高级计算机体系结构（研）、程序设计语言理论（研） 53