λ-演算到π-演算的一種編碼.pdf

1、人類發(fā)展的歷史，就是解決問題的歷史。計算機的出現(xiàn)，加快了人類解決問題的速度，也帶來了與之相對應(yīng)的問題。在一些反復(fù)出現(xiàn)的問題上，人們試圖找出最優(yōu)的解決方案，以期可以達(dá)到最快解決問題的目的。在尋找解決方案的過程中，數(shù)學(xué)模型成為了其中的關(guān)鍵。人們把問題的求解分為兩個階段：先將問題建模成數(shù)學(xué)模型，再對數(shù)學(xué)模型進(jìn)行求解。在這種情況下，許許多多優(yōu)秀的數(shù)學(xué)模型被提了出來，其中包括圖靈機和λ-演算。事實上，兩者的表達(dá)能力是等價的。
　　隨著計算機

2、科學(xué)的發(fā)展，并行逐漸代替串行成為了主流的研究對象。串行計算有圖靈機和λ-演算作為完備的模型可以進(jìn)行科學(xué)研究，而并行計算卻沒有與之相對應(yīng)的計算模型。為了解決這一問題，Milner提出了CCS，同時Hoare提出了CSP，兩者都是優(yōu)秀的并行計算模型。然而，這兩個模型都不能完美的刻畫并行計算的性質(zhì)，原因在于靜態(tài)的結(jié)構(gòu)和不支持通信。在十九世紀(jì)八十年代末，Milner在CCS的基礎(chǔ)上提出了一個表達(dá)能力更強的完備的并行計算模型—π-演算。
　

3、　但隨之而來的問題是串行計算的模型和并行計算的模型之間的表達(dá)能力的關(guān)系。很容易知道，并行計算的模型可以對串行計算的模型進(jìn)行編碼，從而找出表達(dá)能力之間的關(guān)系。Milner在提出π-演算的同時，就給出了一種可以刻畫簡單的λ-演算的解決方案。但是這一方案存在著非常大的局限性，體現(xiàn)在不能刻畫所有的四種歸約策略。蔡小娟和傅育熙則另辟蹊徑，利用更為強大的帶匹配和失配算符的π-演算變種，以編程的方式實現(xiàn)了從λ-演算到π-演算的編碼。這一方案雖然給出了