Thue 之改寫系統《三》

海盜船

忒修斯之船

希臘古羅馬時代的普魯塔克 Plutarch 引用古希臘傳說寫道︰

忒修斯與雅典的年輕人們自克里特島歸來時,所搭之三十槳的船為雅典人留下來當做紀念碑。隨著時間流逝;木材逐漸腐朽,那時雅典人便會更換新的木頭來替代。終於此船的每根木頭都已被替換過了;因此古希臘的哲學家們就開始問著:『這艘船還是原本的那艘忒修斯之船的嗎?假使是,但它已經沒有原本的任何一根木頭了;如果不是,那它又是從什麼時候不是的呢?』

這個『同一性』identity 問題,在邏輯學上叫做『同一律』,與真假不相容的『矛盾律』齊名︰

\forall x, \ x = x

大哲學家亞里士多德認為自然界有一種『原因』Cause 關係,它用著『因為 Because 』回答了『為什麼』Why 之問題。他列舉了四種原因,故簡稱之為『四因說』︰

任何『事物』是由它所構成的『原料』、『組件』和『元素』,按著一套完整的『架構』、『組裝』與『結合』方式才形成的,這個『材質』的部份,就是『物質因』Material Cause ;而那個架構規劃的『藍圖』就是『形式因』Formal Cause,形式因也定義了『□之所以是□』。其次任何『事物』之『存在』總是有理由的,它因著『目的因』Final Cause 而能在時空中『存有』,又可能將隨著時流因之而被改變,這就推動著『動力因』Efficient Cause 去『改變什麼』?又會『如何將之改變』!!

商後期亞醜方觚

觚爵一套

西周初的饮酒器

那麼亞里士多德的四因說,能不能解說這個『忒修斯之船』的同一性問題呢?也許先讓我們聽聽孔老夫子的『觚之抱怨』吧!

倫语‧雍也》:

子曰:觚不觚,觚哉!觚哉!

朱熹集注:觚,棱也;或曰酒器,或曰木簡皆器之有棱者也不觚者蓋當時失其制而不為棱也。觚哉:觚哉!言不得為觚也。

從造字來講,『』字也有『棱角』的啊,竟然將『』觚改為『』觚!無怪乎孔老夫子會喊著『這算是個觚嗎』?『這難到也算是個觚嗎』??

因此如果問他老先生這個『忒修斯之船』的問題,也許他會說︰依其『形制』並沒有什麼被『改變』,所以還一樣是『那個』。或許說『形式因』定義著『什麼是什麼』,所以相較之下比它是用『什麼所構成』的『物質因』還來的重要的吧!!

如果應用現今的『量子統計力學』又該如何看待這個『物體』之『同一性』的問題呢?在『巨觀的宇宙』── 日常世界 ──裡,各種一般大小的物體如同經典牛頓力學所描述的那樣運動著, 我們總可以講『此物』是如何如何的運動,又說『彼物』的軌跡是怎樣怎樣的。就算它小到了看不見,就像在理想氣體方程式的推導裡,我們還是可以『貼標籤』的說『k 個微粒』是如之何如之何,所以如此如此的『統計』,就得到了那個理想氣體的『方程式』。然而假使一切進到了『量子』的宇宙中,那個『量子氣體』裡的『量子』是不可能『貼標籤』的,也就是講沒有什麼『這個』或『那個』量子之分的可說,每個『量子』都是完全『同一』且根本就是『不可能區分』的,更不要說它們還有『費米子』與『玻色子』另外兩種不同的『統計方式』的呢?看似人類今天能用『原子』和『分子』工程打造一艘『相同之船』的吧!!只不過 H 原子失了『電子』就叫『 H^+ 氫離子』,但是氫的『原子核』不是只有一個『質子』的嗎?那它又是為什麼與質子是那麼『不同』的呢??

同樣的問題也發生在計算機科學中的『同等』之『可計算性』問題之上,如果有甲和乙兩台計算機,或者說假使有  A 與 B 兩個程式語言,你將如何區分它們彼此的『計算的功能』或者『表達之能力』的呢?有一個尚未被證明的著名『猜測』,一個由『 λ 運算』之創始人 Church 和『圖靈機』的發明者 Turing 共通設想的『論題』 thesis ︰

 In computability theory,  the Church–Turing thesis ( also known as the Turing–Church thesis,  the Church–Turing conjecture,  Church’s thesis,  Church’s conjecture,  and Turing’s thesis) is a combined hypothesis ( “thesis” ) about the nature of functions whose values are effectively calculable;  or,  in more modern terms,  functions whose values are algorithmically computable.  In simple terms,  the Church–Turing thesis states that a function is algorithmically computable if and only if it is computable by a Turing machine.

因此任何計算機或程式語言只要能夠『模擬』simulate 『圖靈機』,按造上述猜測,它們都具有一樣的『計算能力』,所以 Thue 之改寫系統也具有同等的計算能力。如果你試著去讀 John Colagioia 所寫的 Thue 語言的  python  原始碼,不知會不會驚訝於包含著註解,程式全長只有二百九十二行,但它和 python 語言的計算能力竟是一樣的。但是不要『誤解』這個計算能力的『相當性』,並不代表著『程式寫作』的『方便性』或『清晰性』,就像 Log 『計算尺』的發明,是因為在用紙筆計算的時代,大數的乘除有時甚至是不可能的。舉個例說計算 5^{2014} \times 2^{5702},假使真的一個一個的乘,然後再加不知要不要花上『千萬年』,但是如果使用 Log ,可能是『幾分鐘』的事。也許有人反對說,兩個結果不一樣,一個是『正確的』數,另一個只是『近似的』值,這也難怪有人不得不用 『奧秘的』語法寫一個『神奇的』程式︰『我愛你一世,唉!我氣你愛』,看看會不會發生不可判定之『當機』問題。

一九七二年布萊恩‧柯林漢 Brian Wilson Kernighan  於貝爾實驗室撰寫《Introduction to the Language B》的內部技術文件時,寫了一個『hello, world』的範例程式。其後他與 丹尼斯‧里奇 Dennis M. Ritchie 合著的《The C Programming Language》也保留了這個範例程式。不知怎的這成了一個『傳統』,成了初學者所編寫的第一個程式。現今流行的寫法是『Hello, World!』,不知柯林漢會不會抱怨這是是那個嗎?它的原典是︰

hello, world

,裡頭所有字母全是小寫,『 , 』之後有一『空白』。

Thue 1

 

Thue 2

現在就讓我們用著 Colagioia 之 Thue 語言寫我們第一支中文的『打招呼』程式︰

打招呼::=~別來無恙
::=
打招呼

那要怎麽『跑』run 這個程式呢?網路雲端上有一個『Thue interpreter in Javascript』的網頁,你可以將這支『哈囉』程式,如左圖般地打入或拷貝,先按 Update 鍵載入程式,然後按 Run 鍵執行。你將見證『打招呼』被改寫成了『別來無恙』!!

Colagioia 的 Thue 語言是 semi-Thue 的字串改寫系統 ── 包含子字串擴充之 \rightarrow_R^* 系統 ──,它的程式架構只有兩個部份 ── 字串改寫規則定義和初始字串構成 ──;其中『u \rightarrow v  字串改寫規則』的定義寫作︰

u ::= v

它提供了輸出入功能的『預設』符號 ,用『 ~ 』表示輸出和『 ::: 』表輸入,它們的規定是︰

標籤字串 ::= ~取代標籤之字串

意義是將『標籤字串』改寫成『空字串』,把接在『 ~ 』之後的『取代標籤之字串』輸出到『標準輸出』── 一般是顯示器 ──

標籤字串 ::=:::

意義是將『標籤字串』由『標準輸入』── 一般是鍵盤 ── 之輸入取代

改寫規則定義的『結束列』是一條『空白的規則』定義列︰

::=

,它結束了改寫規則之定義,開啟了『初始字串』的構成。Thue  語言方便讓你可以寫多列的字串,它的語言解譯器會自動將它們序連串成一整個『初始字串』。

一個程式語言的寫作規則只有『四條』,它真的『能寫程式』嗎?當然能,而且可以用『中文化』的『符號』或者說『概念』來寫程式,舉個例子『將一個使用者輸入的二進制之數加一』可以寫成︰

1後繼者::=1加一
0後繼者::=1
01加一::=10
11加一::=1加一0
後繼者0::=後繼者
後繼者1加一::=10
□::=:::
::=
後繼者□後繼者

,這裡的『後繼者』第一個意思是一種自然數的概念,是義大利數學家 Giuseppe Peano 提出的概念︰

自然數 n 的後繼者是 n + 1

,假使它用在『0』與『1』的符號之後,表示將『之前』的數『加一』;如果它用在『0』與『1』的符號之前,是對『之後』之數作最後的『進位』處理。假使你試著用 Step 按鍵,一步一步的觀察,你將能發現這個 Thue 程式的『奧秘』。事實上有許多的『概念』可以用『各種』之『表述』形式,只看用這個概念的人到底是如何設想的呢?更不要說『人類的語言』之本身當然是能『寫作程式』的啊!!

有許多的人以為『確定性』要比『隨機性』要困難的多,其實是『隨機性』真實要困難的多。試想你要怎麽『產生』它的呢?再想一想所謂的『亂數產生器』Random number generation 的方法,它的背後有個『公式』,『隨機』真是能有公式的嗎?所以通常會將之冠以『 pseudo 』一詞,表達著不是像《易經》說的那樣『陰陽不測謂之神』。Thue 之改寫系統的『不確定性』是否就能『心誠則靈』的呢?不如就『擲個筊』吧!

擲筊::=~聖杯
擲筊::=~無杯
誠心祈求::=誠心擲筊祈求
::=
誠心擲筊祈求

 

── 原來『道可道,非常道』一樣是『程式之道』的啊!! ──