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

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

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

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