日々の流転

λ. 第三十一回圏論勉強会

今日は圏論勉強会だった。写真

今回、面白かったのは、以下の練習問題。

For n≧2, not every n-ary function which is computable in each argument needs to be computable. (Hint: take g total nonrecursive and set f(x,y) = g(min{x,y}) ).

最初、「fは各成分についても計算可能ではないのでは?」*1と思ってしまったけど、ちゃんと計算可能だった。直観的には、f(n,-) では n 以下の自然数は有限個なので、それらに対するgの値をテーブルとして持てば良い。