関数の等価性 - mrsekut-p

関数の等価性

外延的等価性

ラムダ式同士の等価性

https://weblogs.asp.net/dixin/lambda-calculus-via-c-sharp-24-undecidability-of-equivalence

関数の等価性が決定不能だという話

『C言語による計算の理論』にも書いているが、ライスの定理を考えればわかる

計算不可能のequalQ

https://twitter.com/kinaba/status/1005299252573102081

関数に==定義するの、RTした記事のように入力が有限(Bounded)の時に限定して全検査するしかないかと思いきや、位相空間に思いを馳せることで、たとえ無限でも (Integer→Bool)→Integer 同士の等価判定とかできるみたいな話があって面白いです

https://www.cs.bham.ac.uk/~mhe/.talks/EWSCS2012/

https://twitter.com/kinaba/status/1005299252573102081/retweets/with_comments

http://www.kmonos.net/wlog/93.html#_0901090117

https://qiita.com/nwtgck/items/8371855594e6e1b2aca6