可計算性邏輯中分支切換復用運算研究.pdf

1、可計算性邏輯(Computability Logic)簡稱CoL，是由Japaridze首先提出的，它將經典邏輯中的真值理論發(fā)展成為可計算性的正式理論，是對經典邏輯的發(fā)展。在CoL中，我們將可計算性的問題看成是由機器和環(huán)境兩種角色參加的博弈，問題的可計算性表示存在一個交互圖靈機總能在表示這個問題的博弈中取勝;邏輯運算符代表可計算性問題上的運算;邏輯公式的永真性表示是永遠可計算的問題。
　　在對博弈和博弈運算的研究中，博弈運算的靜態(tài)

2、屬性是可計算性邏輯中最基礎也是非常重要的內容。在CoL中，我們更多關注的是參加博弈的角色在博弈進行過程中會做出什么動作，采取什么策略實現在博弈中取勝，而不關注他們的博弈速度，這就是靜態(tài)博弈的含義。我們稱一個博弈A是靜態(tài)的，當且僅當對于博弈的角色（機器或者環(huán)境）(&)，博弈過程中產生的行程△和Γ，△是Γ的(&)-延遲，如果Γ是A中的一個使得(&)取勝的行程，那么△也是一個使得(&)取勝行程。因為在CoL中我們研究的博弈都是靜態(tài)博弈，所以，

3、每一個CoL中的運算都需要具有靜態(tài)屬性。
　　CoL是經典邏輯的擴展，其運算符的語義在CoL中與經典邏輯的語義是一致的。目前，隨著CoL的發(fā)展，研究者們已經提出了很多新的運算符，其中分支切換（補）復用運算((d)和(q))是目前最難也是最復雜的一種運算。Japaridze已經給出了關于該運算的定義描述，但是沒有給出其靜態(tài)屬性證明。這個問題也成為了CoL中的open問題之一。所以，本文主要研究了以下三個問題:切換分支復用運算的靜態(tài)屬

4、性證明、新的切換分支復用運算的靜態(tài)屬性證明、新舊版本的切換分支復用運算的等價性證明。
　　本文給出了正式的分支切換（補）復用運算的定義，在該定義中，我們采用靜態(tài)博弈的(Lr,Wn)偶對完成了該運算的定義;并且在定義的基礎上給出了該運算的靜態(tài)性證明。證明過程中，我們首先給出了已知結點、外層已知結點的定義。根據證明的需要，我們使用了CoL中的行程延遲的概念。行程延遲是指在整個博弈過程中，參加博弈的機器或者環(huán)境會由于各種原因而導致在某個

5、行程中出現一些運算步的延遲。本文給出了一個引理證明，證明了對于一個已知的靜態(tài)博弈A,如果在(d)A的某一個行程△中由機器或者環(huán)境做出了一個非法的步，而且△是Γ的一個延遲，那么Γ也是(d)A一個非法步。在(d)和(q)的靜態(tài)屬性證明中，我們使用該引理的結論，簡化了△和Γ在出現非法步時的分析，從而完成了分支切換復用運算的靜態(tài)屬性證明。
　　由于(d)和(q)運算定義的復雜性，使得基于(d)和(q)的推導演繹系統以及應用系統的研究非常遲

6、緩，這也影響了整個CoL研究的進程。所以，我們需要改進傳統的(d)和(q)定義，試圖尋找更簡單的定義。本文提出了一個新的簡單的(d)和(q)定義，為了區(qū)分之前的傳統定義，我們稱傳統的定義為緊湊版，新的定義稱為寬松版。采用(d)T，(q)T分別表示(d)和(q)的緊湊版，使用(d)L，(q)L分別表示(d)和(q)的寬松版。寬松版的分支切換復用運算定義采用位串表示方法，改變了緊湊版定義中對結點的依賴。本文根據定義也完成了寬松版的靜態(tài)屬性證

7、明。在證明中，我們發(fā)現使用寬松版定義的分支切換復用運算需要考慮的情況明顯減少，利于后續(xù)基于該運算的研究。
　　本文介紹了兩個版本的分支切換復用運算，為了在后續(xù)的基于分支切換復用運算推演系統和應用研究中使用寬松版的分支切換復用運算，我們需要給出兩種版本運算的等價性證明。論文中，我們設計了兩個交互算法證明了兩種版本運算的等價性。由于CoL是基于博弈的交互計算，所以，我們使用了基于交互計算的圖靈機模型-易交互計算模型(Easy-Play

8、Machine)。通過該交互計算模型，我們給出了在CoL中可計算性問題求解步驟、行程和步的產生過程。運算等價性證明的第一個算法是指存在一個EPMε1在博弈(d)TA→(d)LA即(q)T(→)A∨(d)LA中取勝。我們根據博弈設計了一個取勝策略，使得ε1存在并且能夠取勝。第二個算法中，我們設計了一個EPMε2，使得它能在博弈(q)L(→)A∨(d)TA中取勝。我們也設計了一個取勝策略，證明這樣的ε2存在。
　　本文的主要研究工作和

9、創(chuàng)新點:
　　一、正式的分支切換復用運算的定義和靜態(tài)屬性證明
　　1.我們給出了基于(Lr,Wn)偶對表示形式的分支切換（補）復用運算的定義。該定義主要是基于樹形結構的思想，重點針對分支切換復用運算的分支運算和切換運算進行描述。所以，我們將分支運算中已知結點的概念進行了重新的定義，細化給出了外層已知結點的定義。定義了完成分支運算的結點只能是外層已知結點;完成切換運算的可以是任何已知結點。本文在行程延遲概念的基礎上，給出了靜態(tài)

10、屬性證明。借助于引理的結果，我們只需要分析兩個具有延遲關系的行程。即一個靜態(tài)博弈A，如果一個行程Γ是(d)A中的一個(&)取勝行程，那么其(&)-延遲行程△也是(d)A中的(&)取勝行程。從而證明了(d)是靜態(tài)的。
　　二、新的分支切換復用運算的定義和靜態(tài)屬性證明
　　2.我們根據傳統的分支切換（補）復用運算定義，采用基于位串的表示方法，給出了一個新的簡單版本定義。該定義打破了已知結點的考慮和限制，定義中直接不需要考慮分支運

11、算，簡化了整個運算。完成運算定義之后，我們同樣給出了新的分支切換復用運算的靜態(tài)屬性證明。在整個證明過程中，我們發(fā)現需要考慮和處理的情況明顯減少，利于基于分支切換復用運算的一些演繹系統和應用系統的提出。
　　三、兩種版本運算等價性證明
　　3.博弈的交互計算特點需要提出新的交互計算模型的概念，根據應用場合不同，論文介紹了難交互計算模型和易交互計算模型，通過這兩種計算模型，我們可以理解博弈的進行過程、步和行程的產生過程。在論文中

12、，我們選用對于機器來說更簡單的易交互計算模型。事實上，兩種計算模型在計算能力上是等價的。
　　4.運算的等價性證明，是指在CoL中設計基于易交互計算模型的算法，使得機器在博弈運算中取勝。論文中設計了兩個算法。在第一個算法中，我們證明存在一個EPMε1在博弈(q)T(→)A∨(d)LA中取勝。第二個算法，我們證明了存在一個EPMε2，使得ε2在博弈(q)L(→)A∨(d)TA中存在取勝策略。從而實現了運算的等價性證明。
　　本

13、文的進一步工作主要包括以下幾個方面:1.我們計劃設計基于寬松版分支切換（補）復用運算的推理系統。包括給出推理系統的推導原則、新的系統的可靠性和完整性證明。我們計劃參考Japaridze提出的CL1-CL15的相關證明方法，設計新的CLx推理系統。2.實現基于分支切換（補）復用運算的應用系統。設計與實現CoL的應用系統，實現真正的人機交互運算。為CoL走向具體應用來設計平臺和界面。我們已經設計和實現完成了CL1的交互計算應用，這可以為我們