Coalgebra 返代數

距離上次嚷嚷著要寫新文章,結果又擱置了。還是回歸本業寫些跟數學有關的,原本較常用英文寫,但我想英文的參考資料很多,列出參考資料應該就很夠了。

廢話結束,先講講何謂 coalgebra ,或者用中文說:返代數。

電腦科學裡頭,我們常用自動機這個數學模型來描述機器的運算,用自動門來說,有關上跟開啓兩種「內部」狀態,當內部變成關閉的狀態時,我們也能觀察到門漸漸關閉或已經關閉,或者根本機械故障關不了。但這時候還是假設自動門的「內部」狀態會是關閉的。從外面紅外線感應器收到訊息輸入後,內部的狀態會改變成開啟的狀態,可以觀察到門漸漸開啟,同樣也有可能關不起來。但我們仍然假設內部的狀態是開啟,而感應器感應不到物體後,內部收到訊號變成關閉。

撇除外部觀察上的問題,只考慮內部狀態的改變的話,自動門的狀態是 S = \{ open, closed \} ,輸入只有兩種可能 Z = \{ Y, N \} 分別代指有人跟沒人。根據上面的描述,例如當狀態為 closed 接受到 Y 的訊號,會變成 open,可以定義一個函數 f : S \times Z \rightarrow S 滿足 f(closed, Y) = open, f(closed, N) = closed, … 等等。

更一般來說,考慮像是 f : S \times Z \rightarrow S 這樣的函數,當 S 是有限的時候,被稱為有限狀態機。

我們還可以加上一些計算功能,多了一個子集合 A \subseteq Z 代表這個機器覺得輸入的指令——一個Z 中元素組成的序列——可以被機器接受以及這個機器原本的狀態 s_0 \in S,通常教科書稱為有限狀態機,為了跟前述的有限狀態機區別,我們說這是有限狀態接受器(acceptor finite state machine)。

我們還可以增加更多的功能,例如這個機器吐出一些訊息,變成一個函數從 S \times ZO \times S,後者多出來的 O 就變成輸出的資料。還可以繼續列舉出來各種不同的數學模型,甚至一個指令對應不止一個狀態,寫成函數 f : S \times Z \rightarrow \mathcal{P}(S) 其中 \mathcal{P}(S) 代表 S 所有的子集合,所以每個結果 f(s, z) 代表的是 S 的子集合。

看到這裡可能會覺得很囉唆,我寫得也

很煩,這些函數之間有沒有什麼共通性呢?

我們可以這樣寫,每個機器的每個狀態,其實對應著一個函數從 ZS,也就是給定一個輸入,會得到接下來的狀態;而同時要知道是不是可以接受的狀態,每個狀態就對應到一個函數跟 YesNo 兩種答案。所以,有限狀態接受機的函數一般可以寫成 \xi : S \rightarrow 2 \times S^Z,其中 2 代表兩個元素的集合,S^Z 代表所有從 SZ 的函數。

同樣地,如果機器每個狀態對應著可能不止一個的狀態,可以寫成 \gamma : S \rightarrow 2 \times \mathcal{P}(S)^Z。而一個會吐出資料的機器,則可以寫成 \zeta : S \rightarrow (O \times S)^Z

大體來說,我們總是可以把函數寫成從一個狀態集合 S 到跟 S 有關的集合,如 \mathcal{P}(S)^ZS^Z2 \times S^Z 等等。像這樣跟 S 有關的集合,我們用 T(S)TS 代表,T 將任意集合 S 對應到另一個集合 TS。所以以上的機器模型,我們總是可以寫成以下的函數:

\displaystyle{ \xi : S \rightarrow TS }

像這類的函數,我們稱之為 T-coalgebra 或是 T-上代數。關於 T 之後會賦予它一些規則,目前來說就只是將某個集合對應到另一個集合。

後記:跟 Josh 討論一陣子,原本採用「上」代數取自同調代數中用的上同調(cohomology),但其實 co- 字首沒有明顯「上」的意思,而是對偶的意思。中文相近的「反」跟「逆」又比較常用在 inverse 跟 converse 這個字上,反函數,逆e關係或逆運算等,跟原本的運算結合會不變。最後改取「返」有倒反的意思,常做動詞如往返,因為 coalgebra 其實是把原本 algebra \alpha : FA \rightarrow A 的箭頭轉過來,所以「返代數」指(方向)被轉過來的 algebra 。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s