1、傳統(tǒng)的可計算性理論以圖靈機(jī)為基礎(chǔ)模型。而當(dāng)代計算卻呈現(xiàn)出交互性、無限性、演化性的特點，從而超出了圖靈機(jī)的表達(dá)能力；由于交互性是其中最根本的特點，所以需要建立交互計算模式下的可計算性理論，即交互可計算性理論。 交互，就是系統(tǒng)在計算過程中的輸入和輸出操作。有交互操作的系統(tǒng)稱為交互式系統(tǒng)。多個交互式系統(tǒng)之間可以利用一定的交互機(jī)制組成復(fù)合系統(tǒng)。 交互可計算性理論的問題歸結(jié)為一點，就是研究交互式系統(tǒng)和交互機(jī)制的計算能力。該問題又可

2、以分解為以下四個小問題：什么是交互計算的形式模型?什么是交互式系統(tǒng)和交互機(jī)制的能力指標(biāo)?什么問題是交互可解的，什么不是?怎么評價交互計算的復(fù)雜度?本文對前兩個問題主要沿用現(xiàn)有的一些成果，而著重于以織女星網(wǎng)格項目為背景對后兩個問題丌展研究。主要內(nèi)容與創(chuàng)新點如下： 1．順序的Ⅱ型交互式系統(tǒng)的計算能力。在織女星網(wǎng)格項目的研究中，提出了Ⅱ型交互模式，即通過交互不僅可以改變系統(tǒng)的數(shù)據(jù)部分，還能修改其控制部分(即程序)。Ⅱ型交互在服務(wù)計算、

3、遠(yuǎn)程協(xié)作等方面都有應(yīng)用價值?；趯ASP模型的交互擴(kuò)展，我們建立了順序的Ⅱ型交互式系統(tǒng)的理論模型，并證明了它與持續(xù)圖靈機(jī)的等價性。對交互可計算性理論的貢獻(xiàn)在于：確定了順序的Ⅱ型交互式系統(tǒng)的計算能力，而相關(guān)工作主要集中于順序的Ⅰ型交互式系統(tǒng)的計算能力。 2．交互積的計算能力。為了盡可能簡化網(wǎng)格服務(wù)和應(yīng)用的開發(fā)以及基礎(chǔ)設(shè)施的搭建，我們設(shè)計了一種異步的、非交替的、基于共享R／W存儲器的交互機(jī)制——交互積，發(fā)現(xiàn)了一類等價于有限狀態(tài)機(jī)的

4、機(jī)器——廣義有限狀態(tài)機(jī)，證明了任何圖靈機(jī)可以被三個廣義有限狀態(tài)機(jī)的交互積模擬。該結(jié)論一定程度上分離出了計算的基本元素，有助于網(wǎng)格計算的低成本和易用性，還有可能導(dǎo)致一種降低對程序員的知識需求的編程模式。對交互可計算性理論的貢獻(xiàn)在于：給出了一種非交替交互機(jī)制的計算能力的非平凡下界，而相關(guān)工作主要集中于交替的交互機(jī)制及其計算能力。 3．交互復(fù)雜度?；诮换シe模型，提出了衡量算法問題在服務(wù)計算等分布式環(huán)境中求解所需要的交互代價的指標(biāo)——

5、交互復(fù)雜度IC。IC表明通過廣義有限狀態(tài)機(jī)的交互積解決一個算法問題需要交互的最少次數(shù)。與類似復(fù)雜度指標(biāo)的關(guān)鍵區(qū)別是：其它指標(biāo)都允許至少一個交互參與者是不可計算的，而IC要求所有參與者都是廣義有限狀態(tài)機(jī)，所以更適合于機(jī)一機(jī)交互的場景。論文還證明了IC至多是算法時間復(fù)雜度的指數(shù)，而算法時間復(fù)雜度至多是IC的線性多項式。 此外，在深入剖析交互計算、拓?fù)鋵W(xué)以及代數(shù)學(xué)的基礎(chǔ)上，本文探索了拓?fù)鋵W(xué)和交互計算的內(nèi)在聯(lián)系，并通過研究持續(xù)圖靈機(jī)和G