학기가 시작된 후에 왜 멈 춥니 까? 람다 미적분

Question

나는 람다 기간의 정상적인 형태를 계산 중입니다. 나는 또한 해결책을 가지고 있으므로 "끝"까지 나의 단계가 옳았다는 것을 안다. 주어진 기간은

(\a.\b.(\x.a b x)(\y. b y x) a) (\f. f f)g 

이며 그의 normalform는

g g (\y. g y x)(\f. f f) 

나는 또한이있어하지만 내가 계속이 마지막 용어입니다 왜 이해가 안됩니다. 나는

g g g (\f. f f) x 

다음

g g g x x 

을 계속하지만 분명히 난 당신이 이전에 중지 해야하는 이유를 알고, 너무 멀리 갔다?

Answer 1

이전에 중지 할 문제가 아닙니다. 당신은 람다 미적분의 구문을 잘못 해석하고 있습니다.

약식으로, A B C을 쓸 때, (A B) C이 아니라 A (B C)이 아니라; 즉, function application is left associative입니다. (\y. g y x)는 (\f. f f)가 적용되지 반면

따라서

g g (\y. g y x)(\f. f f) 

는 (g g)(\y. g y x)이인가된다 특히

((g g) (\y. (g y) x)) (\f. f f) 

로 파싱한다.