没有合适的资源?快使用搜索试试~ 我知道了~
理论计算机科学电子笔记162(2006)37-41www.elsevier.com/locate/entcs并发的基本结构是什么?我们还是Samson Abramsky萨姆森·阿布拉姆斯基1,2牛津大学计算机实验室,英国牛津摘要进程代数在许多方面都取得了成功,但我们还没有看到一个基本理论的轮廓。从Petri网,物理学和几何学中寻找一些令人愉快的一瞥保留字:并发、进程代数、Petri网、几何、量子信息和计算。第1章作为一般理论的什么是计算机科学中成功的理论?考虑一些明显的例子,例如• 进程演算• 类型系统• 模型检测在上述任何领域都没有单一的商定模式、符号、形式、工具或语言。事实上,所有这些都有很多,尽管有些特别重要。(在这里插入你最喜欢的例子。)。)下一个70 0· · ·综合这是我们的主题的“丑闻”吗?我曾经这样认为--而且我罗宾·米尔纳(RobinMilner)对现在我1 这项研究得到了英国的支持。EPSRC2 电子邮件地址:samson@comlab.ox.ac.uk1571-0661 © 2006 Elsevier B.V. 在CC BY-NC-ND许可下开放访问。doi:10.1016/j.entcs.2005.12.07538S. Abramsky/Electronic Notes in Theoretical Computer Science 162(2006)37不太确定。是Paradigms!这些理论所提供的技术和概念上的范式和工具包已被研究界深深地吸收,并越来越多地应用于实践。示例如下:• 标号迁移系统与互模拟• 命名和范围限制与挤压• 模型检验的自动机理论范式• 类型系统范例,上下文中的术语的组合类型规则,以及主题缩减等关键结构属性。凭着他们的果子,就可以认出他们来。这些工具包是这些理论的真正成果。它们可以与物理学和工程学的传统工具箱相比较:微分方程,拉普拉斯和傅立叶变换,数值线性代数等。它们可以应用于各种各样的情况,远远超出了最初的设想,例如安全,计算生物学,量子计算等,那么,花园里的一切都是玫瑰色的吗?终极理论但我们能做得更好吗?毕竟,在物理学中,有一些伟大的理论超越了工具箱。我们在很大程度上缺乏这样的理论,在整个计算机科学中,特别是在并发和进程演算中。这是不可避免的,作为我们学科性质的一部分,还是会出现这样的理论有些人可能觉得这些问题无趣,甚至毫无意义;他们可以安全地停止阅读。2进程演算与并发理论1980年标志着并发理论新时代的开始,但不是它的开始。一个有意义的并发性理论,结合了一些深刻的见解,在20世纪60年代由Petri发起毫无疑问,代数过程演算的出现标志着并发理论的决定性进步,特别是在使用组合代数方法描述复杂系统方面。然而,通常情况下,当取得进展时,一些有价值的东西也会丢失,或者至少暂时被遗忘。让我们从规范性问题开始--“下700个进程代数”综合症。从某种意义上说,正如所描述的,S. Abramsky/Electronic Notes in Theoretical Computer Science 162(2006)3739这也是问题的根源。编造出另一个不同的进程演算或代数太容易了;约束太少了。这种定义的可塑性在我们的领域已经变得如此熟悉,以至于我们可能没有意识到它的存在。数学家和韦拉普发现,代数数论中的正确定义(就像雕刻金刚石)与均匀空间理论(他创立的)中的定义(就像用雪雕刻)是一个复杂的过程。在并发性理论中,我们非常接近于雪雕。我们缺乏那种外部实在,无论它来自基本的数学对象,如整数、流形或微分方程,还是来自由实验确定的物理实在,这是困难和顽固的,并且抵抗我们的定义。这是我们存在的必要特征,还是我们只是还没有找到真正的基石?Petri的并发概念的一个重要性质确定基本概念:因果关系、并发、过程等。以语法独立方式。另一个重要的观点,这可能最初似乎只是古怪的,但现在看起来相当超前,是在何种程度上佩特里[6]的文件。举个例子,注意K密度来自卡尔纳普在很大程度上,通过设计,网络理论可以被看作是一种离散物理学:线是时间类的因果关系,切割是空间类的区域,过程展开一个有标记的网的解的轨迹就像一个微分方程的解的轨迹这在今天获得了新的意义,当“信息是物理的”这一想法的后果此外,需要认识到分布式系统的空间结构已经变得明显,并明确在形式主义,如环境演算,和米尔纳一些道德• 过程演算的天才、成功和局限性在于它们的语言特征。这提供了一种研究过程、信息流等的巧妙方法,而不需要完全知道这些概念中的任何一个是什么,独立于特定的语言环境。人们可以说,他们含蓄地由微积分定义但是,有这么多的结石,潜在的和实际的,这一事实并没有给我们留下非常坚实的基础。我们缺乏对基本概念的语法独立的、内在的定义,并发理论网络理论和一些相关的方法(例如,事件结构)仍然是这些问题的现存最好的描述。但我们仍然远离家乡。因此,例如考虑表现力的问题。 有一些碎片-tary的结果,但没有一个令人信服的概念• 我们现在还必须承认,我们并不是信息、过程等概念的唯一所有者。物理学和生物学也感兴趣--它们就在我们的门口!这给我们提出了一个挑战,也许也是一个挑战。40S. Abramsky/Electronic Notes in Theoretical Computer Science 162(2006)37在这些问题上有一些新的思考。3新方向:生物学、物理学还是几何学?过程演算最近的一个主要发展是它们在生物建模中的应用.这也许代表了一种趋势的第一个实质性例子,在我看来,这种趋势将构成我们学科未来发展的一个主要部分:在计算机科学中发展的思想,我们在第一节中讨论的工具包,向其他科学学科传播。只要CS生物并发社区和生物学家之间有真正的参与,这种发展就有很大的希望。然而,尽管生物建模肯定会对过程演算提出新的要求我不认为这可能导致我们正在讨论的问题的基础性进展。生物学也许,从计算机科学和物理学之间快速发展的接口中找到过程、信息流等基本概念的指导前景更大,这些接口是围绕量子信息学发展起来的。我们已经讨论了Petri网理论的发展是如何(One在量子信息学中起着关键作用的纠缠态引起的非局域信息流的描述是一个明显缺乏的定域性对我们来说是如此合理--然而,在基本的物理层面上,显然是错误的!)。与此同时,在物理学方面也有了一些相应的发展,人们对离散模型的兴趣大大增加作为一个例子,因果集方法离散时空的Sorkin等人。[7]在精神上与事件结构非常接近我最近与Bob Coecke一起研究了量子力学的范畴公理学[2,3],足以对量子信息和计算进行建模和推理,在形式结构上与我早期在交互作用范畴[4]和交互作用几何[1]上的工作非常接近,前者代表了寻找并发理论的更内在的、无语法的公式的尝试,后者可以被视为以数学上相当健壮的形式捕捉交互行为的概念,可以用来对逻辑证明理论和函数计算的动态进行建模。这项工作承认一个惊人的(和非常有用的)图解介绍,这表明一个链接到几何-事实上有坚实的联系与一些中心思想有关的几何和物理已如此突出的数学在过去20年。3我们还注意到,在一个相当不同的[3]我们的范畴的拓扑学与琼斯多项式和其他拓扑不变量的范畴方法有关,而这些不变量又与量子群密切相关,S. Abramsky/Electronic Notes in Theoretical Computer Science 162(2006)3741风格,并发的几何结构已经由Eric Goubault [5]和其他人开发。因此,几何学可能在并发理论中扮演着重要的角色微积分过程在哪里?如果像这样的推测成为现实,我认为过程演算将被提升到一个新的水平。它也许会成为信息动力学基础科学的真正引用[1] Abramsky,S.,进程代数中的若干路径回溯。在[2] Abramsky,S.和B.科克量子协议的分类语义在arXiv:quant-ph/0402130[3] Abramsky,S.和B.Coecke,抽象物理痕迹。Theory and Applications of Categories14(2005),111[4] Abramsky,S.,和S. J. Gay和R.纳加拉詹类型化并发程序设计的交互分类和基础。“演绎程序设计:1994年马克托伯多夫国际暑期学校的会议记录”,页。35-113. NATO ASI Series F,Springer-Verlag,1995年。[5] Goubault , E.并发理论中的一些几何观点 出现在Homology ,HomotopyandAppli cati ons. Availableathttp://www.di.ens.fr/Egoubault/GOUBAULTpapers.html,2001.[6] 佩特里角一、物理学和计算中的状态转换结构。International Journal of Theoretical Physics,21(12),(1982)979[7] 索尔金河, 因果集的第一步 可查阅http://physics.syr.edu/www.example.com。拓扑量子场理论
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功