交互可計(jì)算性和拓?fù)浞椒ǖ难芯?pdf

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

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

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

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

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