lambda calculus

juicy의 이미지

lambda calculus를 공부하다가
의문이 들었습니다.
왜 Church는 여러 그리스 문자 중 하필 lambda를 써서
lambda calculus라고 했을까요..
alpha, beta 따위를 쓰지 않고..
이 분야에서 몇년을 공부해온 선배한테 물어봐도
잘 모르겠다네요..
혹시 아시는분 계세요?

jachin의 이미지

-_- 정말 그거 궁금하네요.

람다라는 기호가 그리스어로는 새끼양을 잡는 덫이라고

설명이 되어 있네요. -_-a

초심자들을 모두 머리아프게 쥐어뜯게 하는

덫이라는 말일지도 모르겠습니다. >_<

skjk의 이미지

Paradigms of Artificial Intelligence Programming에 자세히 나와있더군요..

원래 Russell과 Whitehead의 Principia Mathematica에서 bound variable을 x위에 ^를 붙여쓰는 형식으로 나타냈었대요. Church는 이걸 ^x형식으로 쓰다가 비슷한 모양의 그리스문자인 Λ로 썻고, 덜햇갈리도록 소문자인 λ를 쓰게 되었다고 합니다.

John McCarthy는 Church의 제자였기 때문에 LISP언어에도 lambda를 쓰죠..

jj의 이미지

람다칼큘라스...

0 = ㅅs. ㅅz. z
1 = ㅅs. ㅅz. s z
2 = ㅅs. ㅅz. s (s z)
...

신기하죠?

plus = ㅅm. ㅅn. ㅅs. ㅅz. m s (n s z)
...

헤깔리죠?

fact = (ㅅf. ㅅy. (ㅅx. f (ㅅy. x x y)) (ㅅx. f (ㅅy. x x y)) y) (ㅅfct. ㅅn. if n = 0 then 1 else n * (fct (pred n))) <- if then else 도 원래는 람다칼큘러스로 써야함 ㅡㅡ;;

이쯤 되면, 장난이 아니죠...

--
Life is short. damn short...

netj의 이미지

jj wrote:

fact = (ㅅf. ㅅy. (ㅅx. f (ㅅy. x x y)) (ㅅx. f (ㅅy. x x y)) y) (ㅅfct. ㅅn. if n = 0 then 1 else n * (fct (pred n))) <- if then else 도 원래는 람다칼큘러스로 써야함 ㅡㅡ;;

if then else는 다음과 같이:
true = ㅅx. ㅅy. x
false = ㅅx. ㅅy. y
if a then b else c = a b c

숫자를,
0 = ㅅs. ㅅz. z
1 = ㅅs. ㅅz. s z
2 = ㅅs. ㅅz. s (s z)
... 처럼 만들면 plus나 succ은,
plus = ㅅm. ㅅn. ㅅs. ㅅz. m s (n s z)
succ = ㅅn. ㅅs. ㅅz. s (n s z)
처럼 쉽게 정의되지만 pred가 쉽지 않죠. :(

힌트는 Church식 표현 써서 숫자를 나타내야 한다는 것.
Church식 숫자 인코딩이나 "=", "pred"는 excercise.. -_-;;

juicy의 이미지

책을 보다가 발견했습니다.
책 제목은 'Programming Language: Concepts & Constructs' 2nd ed.
(저자: Ravi Sethi, 1996년)

Quote:

Church was struck by certain similarities between his new concept and that used in Whitehead and Russel [1925] for the class of all x's such that f(x); to wit, x^f(x) (여기서 x^는 x hat). Because the new concept differed quite appreciably from class membership, Church moved the caret down from over the x to the line just to the left of x; specifically, ^xf(x). Later, for reasons of typography, an appendage was added to the caret to produce a lambda; the result was λxf(x).

ps. 이런 데서 이렇게 lambda calculus를 공부해보신 분들을 보니,
반갑네요..

vacancy의 이미지

우리나라에서 만들었다면,

시옷(ㅅ) caculus가 될수도 있었겠네요. ;;