传统的可计算性理论以图灵机为基础模型。而当代计算却呈现出交互性、无限性、演化性的特点,从而超出了图灵机的表达能力;由于交互性是其中最根本的特点,所以需要建立交互计算模式下的可计算性理论,即交互可计算性理论。交互,就是系统在计算过程中的输入和输出操作。有交互操作的系统称为交互式系统。多个交互式系统之间可以利用一定的交互机制组成复合系统。交互可计算性理论的问题归结为一点,就是研究交互式系统和交互机制的计算能力。该问题又可以分解为以下四个小问题:什么是交互计算的形式模型?什么是交互式系统和交互机制的能力指标?什么问题是交互可解的,什么不是?怎么评价交互计算的复杂度?本文对前两个问题主要沿用现有的一些成果,而着重于以织女星网格项目为背景对后两个问题开展研究。主要内容与创新点如下:1.顺序的Ⅱ型交互式系统的计算能力。在织女星网格项目的研究中,提出了Ⅱ型交互模式,即通过交互不仅可以改变系统的数据部分,还能修改其控制部分(即程序)。Ⅱ型交互在服务计算、远程协作等方面都有应用价值。基于对RASP模型的交互扩展,我们建立了顺序的Ⅱ型交互式系统的理论模型,并证明了它与持续图灵机的等价性。对交互可计算性理论的贡献在于:确定了顺序的Ⅱ型交互式系统的计算能力,而相关工作主要集中于顺序的Ⅰ型交互式系统的计算能力。2.交互积的计算能力。为了尽可能简化网格服务和应用的开发以及基础设施的搭建,我们设计了一种异步的、非交替的、基于共享R/W存储器的交互机制——交互积,发现了一类等价于有限状态机的机器——广义有限状态机,证明了任何图灵机可以被三个广义有限状态机的交互积模拟。该结论一定程度上分离出了计算的基本元素,有助于网格计算的低成本和易用性,还有可能导致一种降低对程序员的知识需求的编程模式。对交互可计算性理论的贡献在于:给出了一种非交替交互机制的计算能力的非平凡下界,而相关工作主要集中于交替的交互机制及其计算能力。3.交互复杂度。基于交互积模型,提出了衡量算法问题在服务计算等分布式环境中求解所需要的交互代价的指标——交互复杂度IC。IC表明通过广义有限状态机的交互积解决一个算法问题需要交互的最少次数。与类似复杂度指标的关键区别是:其它指标都允许至少一个交互参与者是不可计算的,而IC要求所有参与者都是广义有限状态机,所以更适合于机-机交互的场景。论文还证明了IC至多是算法时间复杂度的指数,而算法时间复杂度至多是IC的线性多项式。此外,在深入剖析交互计算、拓扑学以及代数学的基础上,本文探索了拓扑学和交互计算的内在联系,并通过研究持续图灵机和GSML语言初步探索了应用的途径。