Inversion

這週複習到 Stoy 那段經典的「為何 computable functions 必須是 continuous lattices 上的 continuous functions」論證。我一直覺得這一段實在美不勝收，「計算」的精髓（或許可以引聰明的話「有涯飛躍無涯」？）從這種角度來看顯得清晰許多。我在 Trek Begins 裡面提到我原本對 Turing machines 的 finiteness 感到不舒服，但後來發現我們處理的 infinity 都是 finitely representable，Stoy 的論證對這個轉念應該有不小的幫助。

其實我要講的是 continuity 定義裡面的主客關係。第一次看到這種「主客對調」現象當然是在大一微積分裡極限的 epsilon-delta 定式。直覺上，若一個函數 f(x) 在 a 點連續，我們會講「當 x 趨近 a 時 f(x) 趨近於 f(a)」，此時自變數 x 是主，應變數 f(x) 是客。但現代微積分告訴我們主客關係不該這麼定，我們應當讓 |f(x) - f(a)| 取得主動，從這個差值回頭去找合適的 x。這種看法在拓樸上泛化成 open sets 的語言，我們說 f : X -> Y 是連續函數的意思是：Y 裡面任意的 open set V 經由 f^{-1} 拉回 X 裡面，f^{-1}(V) 仍然是 open set。主客關係完整地保留下來了。最後回到 Stoy，p.117 說

[T]he characteristic property of continuous functions [is] that every finite piece of information in the result is produced from some finite piece of information in the argument.

單純從數學來看，同樣的主客關係出現在這裡並不意外，因為 Stoy 提到 complete lattices 上的 continuous functions 只是 topological spaces 的特例。但如果從計算的觀點來看就滿有意思了，主客關係的對調似乎比極限的情況更順理成章一些。寫到這裡又覺得，可能是我已經習慣這種主客關係，所以很順理成章地認為順理成章吧 XD。

發現主客關係應該對調的那群人真是太厲害了…

--
拖稿好幾天，累積好幾個主題，現在得慢慢還債啦 XD。