不動点
fixed point
F(f) = f を満たす f を、 F の不動点と呼ぶその写像によって自分自身に写される点のこと
この
f は値のこともあれば、 f 自体が関数ということもある任意のラムダ抽象は1個以上の不動点を持つ
不動点を持たない写像もある
任意のラムダ式は1個以上の不動点を持つ
つまり、任意のラムダ式
M に対して、M =_\beta Mfとなる不動点 f が存在するなぜなら、
YM = M(YM) が成り立つので。この
f もラムダ式なので、不動点といえど、関数であることに注意つまり、以下のように言い換えられる
任意のラムダ式
M の不動点は、 YM であるつまり、
M の不動点が知りたければ、不動点コンビネータに適用すればいい不動点は値のこともあれば、関数のこともある
不動点と言えど、関数になっていることもあることに注意
不動点が値になっている例
以下の関数の不動点は、
0 や 1 や undefined hsf x = x^2不動点が関数になっている例
以下の関数の不動点は、通常の階乗関数
fact hsphi' f x = if x == 0 then 1 else x * f (x - 1)写像の不動点
xy座標なら、
f と y=x の交点とも言える関数f(x)=x^2-3x+4
f(x)=xを解いて、x=2が求まる
これが「f(x)の不動点」
関数
\x -> 42 不動点は42
恒等関数
\x -> x 任意の点が不動点になる
関数
\x -> x*2 不動点は0,1
参考
>#WIP
attractive fixed point