full abstraction - keigoiの日記full abstraction ... λ計算とかπ計算とか表示的意味論のお話ではよく出てくる概念なんですが、未だによくわからないなーとつぶやいていたら id:sumii さんに教えていただいた。 もったいないのでここに残しておきます。 full abstraction の私的な説明 計算体系Aと計算体系(もしくはモデル)B があるとして、 その間の変換を C[・] : A -> B、 〜A と 〜B をそれぞれの計算体系(かモデル)における等価性とします。 すべてのAの項 ta1とta2について C[ta1] 〜B C[ta2] ならば ta1〜A ta2 ... adequacy(soundness) ta1 〜A ta2 ならば C[ta1] 〜B C[ta2] ... completeness この両方が成り立つとき、 変換は fully abstract であるといいます。 た
