[박상일]

변수 이름을 관리하는 것은 임의로 하는 것인가요? 즉, 기존에 있던 변수를 포함한 모든 변수의 이름들을 제 마음대로 바꿔도 되는 건가요?

예를 들어서 (a ((Lambda x (x x)) y))의 결과가 꼭 (a (y y')) 로 되는 게 아니라, (a (y' y)) 이렇게 해도 되고, 심지어 (a (b c))나 (c (a b)) 이렇게 돼도 괜찮은 것인지요?

[윤용호]

저기 써있는 네가지 모두 틀렸습니다.

결과로 가능한 것은 (a (y y)) 혹은 (a (x x)) 혹은 (a (b b)) 등등. 반드시 저 괄호 안에 두개는 이름이 같아야합니다.

'이름이 중복되면 안된다'는 의미를 잘못 이해하신 것 같은데,

'중복되면 안되는 이름'은 Lam 으로 새롭게 binding 되는 이름들 뿐입니다.

식 내부에서 Var로 쓰이는 이름들은 당연히 중복 가능하지요.

보물섬 문제에서 '안내판에 등장하는 이름들은 중복되지 않는다'와 같은 의미입니다. 잘 생각해보세요.
_________________
TA

[박상일]

앗 제가 예시를 급하게 만들다 보니까 엉뚱한 식을 썼네요...

(a ((Lambda x (x x)) (Lambda y (y)))) 이렇게 하면 적절한 예시가 되나요?

(a ((lambda y (y)) (lambda y' (y'))) , (a ((lambda y' (y')) (lambda y (y))), (a ((lambda b (b)) (lambda c (c))), (c ((lambda a (a)) (lambda b (b))) 등이 모두 답으로 가능할까요?;;

[윤용호]

네 그것들은 모두 괜찮습니다.

하지만 역시 '전체 식'에서 저.. a나 b등이 등장하지 않고 있다는

보장이 있어야 합니다.

자신의 운을 믿으신다면 랜덤으로 string 하나 만들어내서 집어넣어도

돌아가긴 할거같구요..............

어쨌든 생성되는 식이

1. 모든 variable의 이름이 다르며
2. Debruijn으로 바꾸었을 때 같은 결과가 나오는 식

이기만 하면 어떻게 하시든 상관 없습니다.
_________________
TA