國中生就會 y-combinator

國中的時候大家都做過一個題目：

$$\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}=?$$

這題目的做法是令$\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}} = x$  ，接下來都會做了，兩邊都平方，就變成 $2+x=x^2$。其實也可以左邊加2再取根號，意思一樣。這裏當然有一個假設沒跟國中生講，就是$\sqrt{2+\sqrt{2+\sqrt{2+\cdots}}}$會收斂到一個數。

 

於是引出了一個概念，叫做函數的不動點。如果 $f(x) = x$，$x$ 就叫 $f$ 的不動點。很多時候，代一個不等於 $x$，但是跟 $x$ 相近的數，例如 $y$，也可以求出 $f$ 的不動點，方法就是 $f( f( f( ...f(y))))$，這會收斂到 $x$ 。看起來很熟悉！不論你是在做國中題目，還是實用上在計算最大值，都是在做這件事而已。

 

不動點應用到計算理論上(以現代觀點來講，可以直接當成就是在講程式語言了)，就是假設 f 對任意數的任意次迭代 (例如$f( f( f(3)))$就是 $f$ 對 3 的3次迭代) 都有定義。那麼我們就認為 $f( f( f(\cdots)))$也代表一個函數，稱之為 $g$，是 $f$ 的「不動函數」，也簡稱不動點。計算理論上因為函數的回傳值常常也是函數，所以用前置式寫法比較方便。例如前面的 $f(3)$ 用前置式寫法就是 $(f\ 3)$。

 

於是有了 $f$，我們要求 $g$ 到底怎麼表示。所以跟國中的算法一樣
$$(f (f (f ... ))) = g$$

兩邊再取 $f$ 可以得到

$$(f\ g) =g \tag{1}$$

 

實際上我們沒辦法直接得到 $g$，要藉由另一個函數 $R$，以 $f$ 當成輸入，回傳值就是 $g$，所以
$$(R\ f) = g$$

代入式$(1)$得到

$$(R\ f) = (f\ (R\ f))$$

這就是 $R$ 的定義，$R$ 就是大名鼎鼎的 y-combinator。

什麼！居然這麼簡單？用的只是國中的技法！

有的時候巧妙的計算只是想法轉個彎而已，內涵並不複雜。不過就這個彎可能要想幾十年。原始的y-combinator是數學家Haskell提出的，他的版本看起來比 $R$ 複雜很多，可是可以簡化成 $R$。