论文部分内容阅读
人类发展的历史,就是解决问题的历史。计算机的出现,加快了人类解决问题的速度,也带来了与之相对应的问题。在一些反复出现的问题上,人们试图找出最优的解决方案,以期可以达到最快解决问题的目的。在寻找解决方案的过程中,数学模型成为了其中的关键。人们把问题的求解分为两个阶段:先将问题建模成数学模型,再对数学模型进行求解。在这种情况下,许许多多优秀的数学模型被提了出来,其中包括图灵机和λ-演算。事实上,两者的表达能力是等价的。随着计算机科学的发展,并行逐渐代替串行成为了主流的研究对象。串行计算有图灵机和λ-演算作为完备的模型可以进行科学研究,而并行计算却没有与之相对应的计算模型。为了解决这一问题,Milner提出了CCS,同时Hoare提出了CSP,两者都是优秀的并行计算模型。然而,这两个模型都不能完美的刻画并行计算的性质,原因在于静态的结构和不支持通信。在十九世纪八十年代末,Milner在CCS的基础上提出了一个表达能力更强的完备的并行计算模型—π-演算。但随之而来的问题是串行计算的模型和并行计算的模型之间的表达能力的关系。很容易知道,并行计算的模型可以对串行计算的模型进行编码,从而找出表达能力之间的关系。Milner在提出π-演算的同时,就给出了一种可以刻画简单的λ-演算的解决方案。但是这一方案存在着非常大的局限性,体现在不能刻画所有的四种归约策略。蔡小娟和傅育熙则另辟蹊径,利用更为强大的带匹配和失配算符的π-演算变种,以编程的方式实现了从λ-演算到π-演算的编码。这一方案虽然给出了一个完全抽象,但是由于目标语言太强,因此表达能力的问题还没有被完全解决。本文提出了一种在π-演算中消去匹配和失配算符的技术,结合蔡小娟和傅育熙的编码体系,证明了不包含匹配和失配算符的π-演算存在保持弱互模拟等价关系的编码。