不動点
fixed point
F(f) = fを満たすfを、Fの不動点と呼ぶ
その写像によって自分自身に写される点のこと
このfは値のこともあれば、f自体が関数ということもある
任意のラムダ抽象は1個以上の不動点を持つ
不動点を持たない写像もある
任意のラムダ式は1個以上の不動点を持つ
つまり、任意のラムダ式Mに対して、$ M =_\beta Mfとなる不動点fが存在する
なぜなら、YM = M(YM)が成り立つので。
このfもラムダ式なので、不動点といえど、関数であることに注意mrsekut.icon
つまり、以下のように言い換えられる
任意のラムダ式Mの不動点は、YMである
不動点は値のこともあれば、関数のこともある
不動点と言えど、関数になっていることもあることに注意
不動点が値になっている例
以下の関数の不動点は、0や1やundefined
code:hs
f x = x^2
不動点が関数になっている例
以下の関数の不動点は、通常の階乗関数fact
code:hs
phi' 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)の不動点」
https://gyazo.com/c8df7ba42e492a68704ad181a45dbe0b
関数\x -> 42
不動点は42
恒等関数\x -> x
任意の点が不動点になる
関数\x -> x*2
不動点は0,1
参考
attractive fixed point