交互可計算性和拓撲方法的研究.pdf

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

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

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

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

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