Y g = (λf . (λx . f (x x)) (λx . f (x x))) g (Yの定義より) = (λx . g (x x)) (λx . g (x x)) (λfのβ簡約、主関数をgに適用) = (λy . g (y y)) (λx . g (x x)) (α変換、束縛変数の名前を変える) = g ((λx . g (x x)) (λx . g (x x))) (λyのβ簡約、左の関数を右の関数に適用) = g (Y g) (第2式より)
SKIコンビネータ計算では次のようになる。 Y = S (K (S I I)) (S (S (K S) K) (K (S I I))) 0006132人目の素数さん2019/03/24(日) 07:19:23.05ID:N4FNRVCO>>4 計算機科学はチューリングマシンをハードウェア、機械として捉える、が正解 0007132人目の素数さん2019/03/24(日) 21:34:57.51ID:FOTRZJL+>>5 > Yコンビネータ ・・・ > Y = (λf . (λx . f (x x)) (λx . f (x x))) > 評価戦略が名前渡しの場合はこのまま使える。 ・・・
これは間違い。評価戦略が名前渡しであっても Y は使えない。それを示すために 君が書き下してくれたY gの式変形をどちら向きにも進める変換 “=” による等式でなく 簡約 “→” による評価として→で向き付けられた形に書き直してみよう。
Y g ≡ (λf . (λx . f (x x)) (λx . f (x x))) g (Yの定義より) → (λx . g (x x)) (λx . g (x x)) (λfのβ簡約、主関数をgに適用) ≡ (λy . g (y y)) (λx . g (x x)) (α変換、束縛変数の名前を変える) → g ((λx . g (x x)) (λx . g (x x))) (λyのβ簡約、左の関数を右の関数に適用) ← g (Y g) (第2式より)
最後のステップが逆向きの簡約 “←” であることに注意。 このステップは絶対に本来の簡約 “→” の向きには書き直せないので Y コンビネータは名前呼びでも使えないことが分かる。
Θ g ≡ ((λx y, y(x x y))(λx y, y(x x y))) g ≡ ((λz w, w(z z w))(λx y, y(x x y))) g ・・・・・・・・・・・・ α変換 → (λw. w((λx y, y(x x y))(λx y, y(x x y)) w)) g ・・・ β簡約 ≡ (λw. w(Θ w)) g ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ Θの定義で置き換え → g(Θ g)
なお、値呼びの簡約戦略で正しく動く不動点コンビネータも勿論ある。 具体的な定義は、例えば次にある: Daniel P. Friedman & Matthias Felleisen “The Little Schemer” 4th ed., p. 172 (The MIT Press, 1996). 0008132人目の素数さん2019/03/25(月) 18:38:51.28ID:ZEwsypVC>>7訂正
ついでに言えば、自然言語の文法を型理論的に分析するLambek Calculusだと 上の→と←との各々に対応する型構成子がある “Lambek Calculus”とか“Categorial Grammar”とかで色々と調べてみてごらん 0085132人目の素数さん2019/11/20(水) 11:54:20.91ID:JRZAHV8l>>84 >P←Q def= Q→P 読み方は 「なんとなれば」 でいいかな?チョット長い 「なしか」 でどうかな 0086132人目の素数さん2019/11/20(水) 12:02:45.35ID:s2bhFDG0 英語ではすでにifとonly ifでわけてるんじゃないですか? 0087132人目の素数さん2019/11/20(水) 12:15:54.84ID:JRZAHV8l P if QはP←Q P only if Qは?if and only ifで成語となると思うんだけどP only if Q単独で¬P←¬Qの意味になる? 0088132人目の素数さん2019/11/20(水) 12:23:33.43ID:s2bhFDG0 P only if Q Pが成り立つのはQが成り立つ時に限る
P→Qてことですよね 0089132人目の素数さん2019/11/20(水) 13:23:26.20ID:JRZAHV8l 自分はif and only if (iff)以外の単独でonly ifが使われたのみたときないけど それはそれとして P only if QがP→Qであるとしたら only if=ならば if=? 0090132人目の素数さん2019/11/20(水) 13:28:47.76ID:s2bhFDG0 屁理屈こねる前に素直に英語の意味考えてみればああそうだなってなりますよね
if← and only if→=⇆
これだけですよね 0091132人目の素数さん2019/11/20(水) 15:03:54.46ID:JRZAHV8l>>90 屁理屈って・・・ if and only ifが⇔の意味であることは良いんだって only ifが単独で使われたのみたときないのと それはそれとして only if=ならば となるから if=? と聞いてみただけ 0092132人目の素数さん2019/11/20(水) 15:44:28.18ID:BZyGNV5o The logical relation is, as before, expressed as "if P, then Q" or "P ⇒ Q". This can also be expressed as "P only if Q", "P implies Q" or several other variants.