论文题目: 交互可计算性和拓扑方法的研究
论文类型: 博士论文
论文专业: 计算机系统结构
作者: 刘兴武
导师: 徐志伟
关键词: 交互,可计算性,复杂度,拓扑
文献来源: 中国科学院研究生院（计算技术研究所）
发表年度: 2005
论文摘要: 传统的可计算性理论以图灵机为基础模型。而当代计算却呈现出交互性、无限性、演化性的特点,从而超出了图灵机的表达能力;由于交互性是其中最根本的特点,所以需要建立交互计算模式下的可计算性理论,即交互可计算性理论。交互,就是系统在计算过程中的输入和输出操作。有交互操作的系统称为交互式系统。多个交互式系统之间可以利用一定的交互机制组成复合系统。交互可计算性理论的问题归结为一点,就是研究交互式系统和交互机制的计算能力。该问题又可以分解为以下四个小问题:什么是交互计算的形式模型?什么是交互式系统和交互机制的能力指标?什么问题是交互可解的,什么不是?怎么评价交互计算的复杂度?本文对前两个问题主要沿用现有的一些成果,而着重于以织女星网格项目为背景对后两个问题开展研究。主要内容与创新点如下:1.顺序的Ⅱ型交互式系统的计算能力。在织女星网格项目的研究中,提出了Ⅱ型交互模式,即通过交互不仅可以改变系统的数据部分,还能修改其控制部分(即程序)。Ⅱ型交互在服务计算、远程协作等方面都有应用价值。基于对RASP模型的交互扩展,我们建立了顺序的Ⅱ型交互式系统的理论模型,并证明了它与持续图灵机的等价性。对交互可计算性理论的贡献在于:确定了顺序的Ⅱ型交互式系统的计算能力,而相关工作主要集中于顺序的Ⅰ型交互式系统的计算能力。2.交互积的计算能力。为了尽可能简化网格服务和应用的开发以及基础设施的搭建,我们设计了一种异步的、非交替的、基于共享R/W存储器的交互机制——交互积,发现了一类等价于有限状态机的机器——广义有限状态机,证明了任何图灵机可以被三个广义有限状态机的交互积模拟。该结论一定程度上分离出了计算的基本元素,有助于网格计算的低成本和易用性,还有可能导致一种降低对程序员的知识需求的编程模式。对交互可计算性理论的贡献在于:给出了一种非交替交互机制的计算能力的非平凡下界,而相关工作主要集中于交替的交互机制及其计算能力。3.交互复杂度。基于交互积模型,提出了衡量算法问题在服务计算等分布式环境中求解所需要的交互代价的指标——交互复杂度IC。IC表明通过广义有限状态机的交互积解决一个算法问题需要交互的最少次数。与类似复杂度指标的关键区别是:其它指标都允许至少一个交互参与者是不可计算的,而IC要求所有参与者都是广义有限状态机,所以更适合于机-机交互的场景。论文还证明了IC至多是算法时间复杂度的指数,而算法时间复杂度至多是IC的线性多项式。此外,在深入剖析交互计算、拓扑学以及代数学的基础上,本文探索了拓扑学和交互计算的内在联系,并通过研究持续图灵机和GSML语言初步探索了应用的途径。
论文目录:
摘要
Abstract
目录
图目
表目
第1章 绪论
1.1 研究背景与意义
1.2 问题陈述
1.2.1 问题的引出
1.2.2 交互概述
1.3 国内外相关工作
1.3.1 交互计算模型
1.3.2 交互系统能力指标
1.3.3 交互可解或不可解的问题
1.3.4 交互相关的复杂度指标
1.3.5 新的数学方法
1.4 论文的主要研究内容
1.5 主要创新点
1.6 文章的结构
第2章 Ⅱ型交互式系统
2.1 交互分类
2.1.1 交互式系统的分类
2.1.2 交互机制的分类
2.2 Ⅱ型交互的场景
2.3 Ⅱ型交互模型
2.3.1 RAM 和RASP
2.3.2 PRASP
2.3.3 PRASP 的表达能力
2.4 小结
第3章 交互积
3.1 CAM 回顾和问题分析
3.2 准备知识
3.3 交互积基本定理
3.3.1 图灵机的投影及其交互积
3.3.2 M_×的格局
3.3.3 格局的迁移
3.3.4 有效格局的基本性质
3.3.5 极大运行迹的唯一性
3.3.6 M_×的计算能力
3.4 广义有限状态机及其交互积
3.4.1 广义有限状态机的交互积定理
3.4.2 广义有限状态机基本性质
3.5 小结
第4章 交互复杂度
4.1 相关工作
4.2 交互复杂度的定义
4.2.1 模型选择
4.2.2 交互复杂度
4.3 交互复杂度的性质
4.3.1 零交互复杂度类
4.3.2 时间复杂度对交互复杂度的约束
4.3.3 交互复杂度对时间复杂度的约束
4.4 交互复杂度的例子
4.5 小结
第5章 交互与拓扑学
5.1 数学的发展和启示
5.2 交互与拓扑学的联系
5.2.1 拓扑学基本概念
5.2.2 代数和拓扑的比较
5.3 拓扑学的应用范例
5.4 我的探索
5.4.1 持续图灵机的表达能力
5.4.2 GSML 语义研究
5.5 小结
第6章 总结和下一步的工作
6.1 论文工作总结
6.2 下一步的工作
参考文献
致谢
作者简历
发布时间: 2006-12-27
相关论文
- [1].不可计算复杂性的机理与意义[D]. 张本祥.华南师范大学2006
- [2].蚁群算法理论、应用及其与其它算法的混合[D]. 高尚.南京理工大学2005
- [3].基于以太网的存储系统研究[D]. 胡风华.中国科学院研究生院（计算技术研究所）2005
- [4].基于视频的人体运动跟踪技术研究[D]. 刘国翌.中国科学院研究生院（计算技术研究所）2005
- [5].基于空间多点信息采集的虚拟现实人景合成关键技术研究[D]. 黄海明.中国科学院研究生院（计算技术研究所）2005
- [6].所有者为中心的网格资源共享研究[D]. 梁建民.中国科学院研究生院（计算技术研究所）2003
- [7].证明和测试分布式系统的功能正确性[D]. 吕毅.中国科学院研究生院（计算技术研究所）2004
- [8].织女星信息网格易用性关键问题研究[D]. 杨宁.中国科学院研究生院（计算技术研究所）2005
- [9].网格中文件管理若干关键问题的研究[D]. 曹立强.中国科学院研究生院（计算技术研究所）2005
- [10].可计算与可学习的实递归函数[D]. 李志敏.贵州大学2007