浅谈交互可计算性和拓扑方法的研究

《浅谈交互可计算性和拓扑方法的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中国科学院计算技术研究所博士学位论文交互可计算性和拓扑方法的研究姓名：刘兴武申请学位级别：博士专业：计算机系统结构指导教师：徐志伟20050601巾Ⅲl：}擘硫竹I中扣廿Z～，c『1吖计博竹和拓扑方法的埘究摘要传统的可计算性理论以图必机为壤础模型。而当代计算却呈现出交互性、正限性、演化性的特点，从呵超出了图灵机的表达能力；由于交互性是其中最根本的特点．所以需要建立交互计算模式下的可计算性理论，即交互可计算性理论。交互，就是系统在计算过程中的输入和输出操作。有交互操作的系统称为交互式系统。多个交互式系统之问可以利川一定的交互机制组成复合系统。交互可计算性理论的

2、问题归结为一点，就是研究交互式系统和交互机制的计算能力。该问题又可以分解为以下四个小『口】题；什么是交互计算的形式模型?什么是交互式系统和交互机制的能力指标?什么问题是交互可解的，什么不是?怎么评价交互计算的复杂度?本文对耵两个问题主要沿用现有的一些成果，而着重于以织女星网格项目为背景对后两个问题开展研究。主要内容与创新点如下：1．顺序的II型交互式系统的计算能力。在织女星网格项目的研究中，提出了II型交互模式，即通过交互不仅可以改变系统的数据部分，还能修改其控制部分(即程序)．II型交互在服务计算、远程协作等方面都有应用价值。基于对RASP模型的交互扩展，

3、我们建立了顺序的II型交互式系统的理论模型，并证明了它与持续图灵机的等价性。对交互可计算性理论的贡献在于：确定了顺序的II型交互式系统的计算能力，而相关工作主要集中于顺序的I型交互式系统的计算能力。2．交互积的计算能力。为了尽可能简化明格服务和应用的开发以及基础设施的搭建，我们设计了一种异步的、非交替的、基于共享R／W存储器的交互机制——交互积，发现了一类等价于有限状态机的机器——广义有隈状态机，证明了任何图灵机可以被三个广义有限状悫机的交互积模拟。後结论一定程度上分离出了计算的基本元素，有助于网格计算的低成本和易用性，还有町能导致一种降低对程序员的知识需求

4、的编程模式。对交互可计算性理论的贡献在于：给出了一种非交替交互机制的计算能力的非平凡下界，而相关工作主要集中于交替的交互机制及其计算能力．3．交互复杂度．基于交互积模型，提出了衡量算法问题在服务计算等分布式环境中求解所需要的交互代价的指标——交互复杂度Ic。Ic表明通过广义有限状态机的交互积解决一个算法问题需要交互的最少次数。与类似复杂度指标的关键区别是：其它指标都允许至少一个交互参与者是不可计算的，而Ic要求所有参与者都是广义有限状态机，所以更适合于机·机交互的场景。论文还证明了Ic至多是算法时『日】复杂度的指数，而算法时恻复杂度至多是Ic的线性多项式。此

5、外。在深入剖析交互计算、拓扑学以及代数学的基础上，本文探索了拓扑学和交互计算的内在联系，并通过研究持续圈灵机和GSML语言初步探索了应用的途径。关键词：交互；可计算性；复杂度：轧扑：GSML中周科学院竹I擘忙诊乏—一空且Ⅱ』计算{4=即拓扑方法的研究Research09InteractiveComputabilityandItsTopologicalApproachesLiuXingwu(ComputerArchitecture)7：DirectedByXuZhiweiThetraditionaltheoryofcomputabilityisbasedonT

6、l埘ngmachines．However,contemporarycomputinggoesbeyondthecapabilityofTuringmachinesbecauseofitspropertiesofinteraction,infinity,andevolution,amongwhichinteractionisfundamental，SOit’Snecessarytoestablishinteractivecomputabilitytheory,i．e。atheoryofcomputabilitydedicatedtointeractivecom

7、puting．Interactionisdefinedtobetheinputandoutputoperationsofasystemduringitscomputation,andsuchasystemiscalledallinteractiveone．Multipleinteractivesystemsconstituteacomposedsystemifsomeinteractionmechanismisprovided．Inoneword，thetaskofinteractivecomputabilitytheoryistodeterminethec

8、omputingcapabilityofintera