λ-演算到π-演算的一种编码

发布时间：2021-04-08 05:59

　　人类发展的历史,就是解决问题的历史。计算机的出现,加快了人类解决问题的速度,也带来了与之相对应的问题。在一些反复出现的问题上,人们试图找出最优的解决方案,以期可以达到最快解决问题的目的。在寻找解决方案的过程中,数学模型成为了其中的关键。人们把问题的求解分为两个阶段:先将问题建模成数学模型,再对数学模型进行求解。在这种情况下,许许多多优秀的数学模型被提了出来,其中包括图灵机和λ-演算。事实上,两者的表达能力是等价的。随着计算机科学的发展,并行逐渐代替串行成为了主流的研究对象。串行计算有图灵机和λ-演算作为完备的模型可以进行科学研究,而并行计算却没有与之相对应的计算模型。为了解决这一问题,Milner提出了CCS,同时Hoare提出了CSP,两者都是优秀的并行计算模型。然而,这两个模型都不能完美的刻画并行计算的性质,原因在于静态的结构和不支持通信。在十九世纪八十年代末,Milner在CCS的基础上提出了一个表达能力更强的完备的并行计算模型—π-演算。但随之而来的问题是串行计算的模型和并行计算的模型之间的表达能力的关系。很容易知道,并行计算的模型可以对串行计算的模型进行编码,从而找出表达能力... 

【文章来源】：上海交通大学上海市 211工程院校 985工程院校 教育部直属院校

【文章页数】：53 页

【学位级别】：硕士

【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 研究背景和意义
    1.2 国内外研究现状
    1.3 研究内容和成果
    1.4 论文结构
第二章 λ-演算和π-演算
    2.1 λ-演算
    2.2 π-演算
    2.3 Milner的编码体系
    2.4 蔡小娟和傅育熙的编码体系
第三章 计算模拟匹配和失配
    3.1 灵感和基本原理
    3.2 用匹配模拟失配（第一次尝试）
    3.3 用通信模拟匹配（第二次尝试）
    3.4 消去常名的干扰（第三次尝试）
    3.5 用私有名进行通信（最终版本）
    3.6 编码生成
第四章 编码体系下相关性质
    4.1 同敛散性
    4.2 弱互模拟关系
    4.3 从λ-演算到π-演算的编码
第五章 总结和未来展望
    5.1 总结
    5.2 未来展望
参考文献
致谢
攻读学位论文期间发表的学术论文目录



本文编号：3124990