講全函數、部分函數與計算理論

[dannypsnl]

可以參考我今年在學校講的 https://dannypsnl.me/hami2023

[dannypsnl]

前置

1. 對任意 a -> b 的函數有 (a -> b) -> (a -> b) 的高階函數 F
2. 高階函數本身絕對是非遞迴的，所以 well defined
3. 吐出來的函數只要有定義的部分，目標遞迴函數肯定也是給出一樣的輸出
4. F 回傳的函數都比輸入的那個更貼近目標遞迴函數 f

定理

1. 目標遞迴函數 f 必定是不動點，也就是滿足 F f = f。證明很容易，因為不可能改善 f 而更貼近 f，所以輸出必定是 f 本身

結論

1. 故從 $\bot$ 什麼都沒有定義的函數出發就會得到函數 series $(F^n(\bot))_{n \in \omega}$
2. 取極限可以發現也是個不動點，所以必然跟目標 f 一樣好，我們直接定義這就是我們能找到的遞迴函數

[dannypsnl]

https://dannypsnl.me/math-003Z.xml 這個也是，但已經比較複雜了

[dannypsnl]

現代的一個方向之一應該是 Fiore 的博士論文，繼承 Plotkin 的工作那邊