Ый способ

Базис K, S.

Кроме базисного набора K, S будем использовать еще плюс к ним I.

Любое λ-выражение Р, не содержащее свободных переменных представляется в базисе IKS индукцией по построению терма Р.

Р: FV(P) = Ø –свободные переменные.

λх.х = I

λx.P = KP, если хFV(P)

λx.PQ = S(λx.P)(λx.Q)

Примеры.

λxy.yx = S(K(SI))(S(KK)I)

Babc = a(bc) Представим комбинатор B в базисе I,K,S.

B: λxyz.x(yz)

λx.(λy.(λz.x(yz))) = λx.(λy.(S(λz.x)(λz.(yz))) = λx.λy.(S(Kx)(S(λz.y)(λz.z))) =

= λx.λy.((S(Kx)(S(Ky)I)) = λx.(S(λy.S(Kx))(λy.S(Ky))I)) = λx.(S(K(S(Kx)))

(S(λy.S(Ky))(λy.I))) = λx.(S(K(S(Kx)))(S(S(λy.S)(λy.Ky))(KI))) =

= λx.(S(K(S(Kx)))(S(S(KS)(S(KK)I))(KI))) = S(λx.(S(K(S(Kx))))(λx.[…])) =

нет свободных вхождений х

= S(S(λx.S)(λx.K(S(Kx)))(…) = S(S(KS)(S(λx.K)(λx.S(Kx)))(…) =

= (S(S(KS)(S(KK)(S(KS)(λx.Kx))))(…) = (S(S(KS)(S(KK)(S(KK)(I))(…).

Дата добавления: 2014-01-11; Просмотров: 295; Нарушение авторских прав?; Мы поможем в написании вашей работы!