람다의 룰리올로지

람다의 룰리올로지

도표를 클릭하면 해당 도표를 재현하는 Wolfram Language 코드를 볼 수 있습니다.

무엇이 람다인가?

이야기의 주인공은 순수하고 추상적인 계산입니다. 역사적으로도 가장 이른 사례 중 하나죠. 저 역시 거의 반세기 동안 실무에서 사용해 왔지만, 단순한 계산 시스템과 룰리올로지를 오랜 세월 탐구하면서도 람다 자체를 본격적으로 다룬 적은 없었습니다. 세세한 기술적 문제도 있긴 합니다. 하지만 결국 람다는—제가 탐구해 온 많은 시스템처럼—실용 계산과의 연결 덕분에 더욱 의미 있는 풍부한 룰리올로지를 지니고 있음이 드러납니다.

Wolfram Language에서는 Function 함수로 나타냅니다. 1930년대에 알론조 처치가 처음 논의했을 때 그는 이를 λ(람다)라고 불렀습니다. 핵심 아이디어는 “순수 함수”—인자를 적용하면 값을 내놓는 것—를 갖는 것입니다. 예를 들어 Wolfram Language에서는 다음과 같이 쓸 수 있습니다:

이 자체로는 자기 자신으로 평가되는 기호식입니다. 하지만 여기에 인자를 적용하면 그 인자가 본문(body)에 치환되고, 이어 본문이 평가됩니다:

Wolfram Language에서는 이렇게도 쓸 수 있고:

또는 λ = Function 으로 두면 다음처럼 쓸 수 있습니다:

이는 처치의 원래 표기(λ x .(1 + x)) 8에 가깝습니다.

그런데 만약 우리가 “더 순수하게” 가고 싶다면 어떨까요? 즉 Plus (+) 같은 사전 정의된 함수 없이 사실상 “모든 것을 λ로만” 하고 싶다면요? 람다를 세팅하려면 (f[x]가 “f를 x에 적용”한다는 의미의) 함수 적용 개념이 필요합니다. 예컨대 다음은 함수 적용 구조만으로 정의된 람다(“순수 함수”)입니다:

이런 설정으로 익숙한 연산을 할 수 있을까요? 0을 나타내는 기호 z, 후속자(successor)를 계산하는 연산 s를 나타내는 기호 s가 있다고 해봅시다. 그러면 0에서 5까지 정수의 표현은 다음과 같습니다:

예를 들어 s[s[s[s[z]]]]를 보죠. 이 표현에서 s와 z를 “팩터링”해 내면, “순수하게 구조적인” 부분을 람다만으로 다음처럼 쓸 수 있습니다:

사실 여기서 s와 z가 꼭 필요한 건 아닙니다. 정수를 람다만으로 완전히 잘 표현할 수 있습니다. 즉 (소위 “처치 수”로 알려진) 다음과 같이요:

매우 순수하고 추상적입니다. 처음에는 무척 깔끔해 보이죠. 하지만 곧바로 심각한 문제에 부딪힙니다. 만약 우리가 다음처럼 쓴다면:

이건 무슨 뜻일까요? x[x]의 x들은 안쪽 λ의 x와 관련이 있을까요, 바깥쪽 λ의 x와 관련이 있을까요? Wolfram Language에 이런 표현을 입력하면 x가 빨갛게 표시되며 문제가 있음을 알려줍니다:

이 수준에서는 문제를 풀 유일한 방법이 두 x에 서로 다른 이름을 주는 것입니다. 예를 들어:

하지만 궁극적으로 어떤 이름을 쓰든 상관없습니다. 예컨대 x와 y를 바꾸더라도

이전과 정확히 같은 함수를 나타냅니다.

이를 어떻게 다룰까요? 한 가지 접근—실은 람다보다 십수 년 먼저 고안된 것이고, 제가 몇 해 전에 한 권의 책을 쓰기도 했죠—은 소위 “콤비네이터”를 사용하는 것입니다. 이들은 이름을 붙이거나 변수를 도입하지 않고도 상징식을 어떻게 재배열할지 추상적으로 정의하는 구성물입니다. 예를 들어 λ[x, λ[y, y[x]]]는 다음처럼 쓸 수 있고

다음으로 확인할 수 있습니다:

어느 수준에서는 매우 우아합니다. 하지만 읽기 무척 어렵기도 하죠. 그렇다면 이름이 붙은 변수를 명시적으로 도입하지 않으면서도 람다의 비교적 가독성을 어느 정도 보존할 방법은 없을까요? 방법이 있습니다. 출발점은 명명된 변수(예: x)는 기본적으로 그 변수를 소개한 특정 람다(예: λ[x, …])를 가리키는 방식이라는 관찰입니다. 그리고 그 참조를 명명된 변수 대신, 참조하는 위치에 상대적인 람다의 “구조적” 위치로 하자는 생각입니다.

예를 들어

를 두고, 이를 “드브루인 지수”(de Bruijn index, “드 브로인” 발음) 형태로 쓰면

가 됩니다. 여기서 1은 그 위치의 변수가 표현에서 “한 단계 뒤의 λ”와 연관됨을, 2는 그 위치의 변수가 “두 단계 뒤의 λ”와 연관됨을 말합니다:

예컨대 앞서 본 정수의 람다 표현은 이제 다음처럼 쓸 수 있습니다:

좋습니다. 람다는 (정수처럼) 대상을 표현할 수 있습니다. 그렇다면 “람다로 계산”도 할 수 있을까요? 달리 말해 순수 람다가 할 수 있는 것은 무엇일까요?

근본적으로 연산은 하나뿐입니다. 보통 베타 축약(beta reduction)이라 부르며, 람다가 받은 인수를 람다의 본문에 명시적으로 “주입”해, 함수에 인수를 적용하는 “구조적” 부분을 수행합니다. 매우 간단한 베타 축약의 예는

인데, 이는 표준 Wolfram Language 평가와 동등합니다:

드브루인 지수로는 다음이 되고

역시 (베타 축약으로) “평가”하면 다음이 됩니다:

아주 간단한 연산처럼 보입니다. 하지만 반복 적용하면 온갖 복잡한 거동과 흥미로운 구조가 나타납니다. 핵심은 람다가 다른 람다의 인수로 등장해, 베타 축약을 통해 그 본문에 주입될 수 있다는 점입니다.

하지만 한 람다를 다른 람다에 주입하는 순간 까다로운 문제가 생깁니다. 모든 것을 변수로 명시적으로 쓰면 대개 변수 이름 바꾸기(renaming)가 필요합니다. 예를 들어

는 다음으로 평가됩니다:

드브루인 지수로는 이름 바꾸기 대신 재번호 매기기가 필요합니다. 따라서

는 다음으로 평가됩니다:

베타 축약이 무엇을 하는지 비공식적으로 설명하는 것은 쉽습니다. Wolfram Language 관점에서 기본 변환은 다음과 같습니다:

즉 λ[x, body][y]가 주어지면, 베타 축약은 body 안의 모든 _x_를 _y_로 바꾸고 결과를 반환합니다. 하지만 이게 그렇게 간단하지만은 않습니다. 예를 들어 _y_에 람다가 포함된다면—위의 예처럼—변수 이름 바꾸기(보통 “알파 변환”, alpha conversion)가 어느 정도 필요합니다. 경우에 따라 이름 바꾸기가 연쇄적으로 이어질 수도 있고, 이때 임의의 개수만큼 서로 다른 새 이름이 필요할 수도 있습니다.

그리고 λ[x, body][y]의 치환(“베타 축약”)을 하고 나면 또 다른 람다가 “드러나” 더 많은 치환을 해야 할 수 있고, 그 다음에도 계속될 수 있습니다. 사소해 보이지만 사실 매우 근본적인 부분입니다—이 덕분에 람다는 “계속 실행되는” 계산을 나타내며, 여기서 우리가 다룰 풍부한 룰리올로지가 생겨납니다.

드브루인 지수로 베타 축약을 하면 더 쉬울까요? 사실은 그렇지 않습니다. 변수 이름을 만들어 낼 필요는 없지만, 그 대신 람다를 삽입하거나 삭제할 때마다 인덱스를 꽤 성가시게 재귀적으로 재정렬해야 합니다.

또 다른 이슈도 있습니다. 뒤에서 자세히 보겠지만, 주어진 람다에는 종종 여러 개의 베타 축약 후보가 있습니다. 그리고 모든 가능성을 추적하면 멀티웨이 그래프 전체—즉 가능한 “람다 평가 경로”의 그래프—를 얻게 됩니다. 하지만 람다에 대한 근본적 사실(합류성 또는 Church–Rosser 성질로 알려져 있고, 인과 불변성과 관련됨)은, 주어진 람다에 대해 베타 축약을 거듭하다가 결국 고정점(항상 그런 건 아님; 곧 보게 됩니다)에 도달한다면 그 고정점은 유일하다는 것입니다. 즉 람다 평가 결과는 항상 확정적(“정규형”)입니다.

그렇다면 람다로 뭘 하는 행위를 뭐라고 부를까요? Wolfram Language에서는 Function[x, x[x]][a](즉 λ[x, x[x]][a])를 a[a]로 바꾸는 과정을 “평가”라고 합니다. 하지만 때로는 축약(reduction), 변환(conversion), 치환(substitution), 재작성(rewriting) 등으로도 부릅니다. Wolfram Language에서는 λ[…]를 “λ 표현식”이라 부를 수 있지만, “λ 항(λ term)”이라고도 합니다. 안에 들어 있는 것은 어떨까요? λ[x, body]에서 _x_는 보통 “결합 변수(bound variable)”라고 합니다. (_body_에 나타났지만 어떤 λ에도 “결합”(또는 “스코프”)되지 않은 변수—예: y—는 “자유 변수(free variable)”라고 합니다. 여기서 다룰 λ 표현식은 보통 자유 변수가 없습니다. 이런 λ 표현식을 “닫힌(closed) λ 항”이라 부릅니다.)

무언가를 λ로 감싸는—예: λ[x, thing]—행위는 보통 “λ 추상화(abstraction)”라고 부르고, λ 자체를 “추상자(abstractor)”라고도 합니다. 람다의 “본문”에서 x를 y에 적용해 x[y]를 만드는 것은 예상대로 보통 “적용(application)”이라고 합니다(뒤에서 논하겠지만 x@y 또는 x•y로도 나타낼 수 있습니다). 람다에 대한 연산은 어떨까요? 역사적으로 세 가지가 구분됩니다: α 축약(또는 α 변환), β 축약(또는 β 변환), η 축약(또는 η 변환). 위에서 논한 β 축약은 사실상 핵심 “평가형” 연산입니다(예: λ[x, f[x]][y]를 f[y]로 대체). α와 η 축약은 일종의 “상징적 정리 작업”입니다. α 축약은 변수 이름 바꾸기, η 축약은 λ[x, f[x]]를 f로 줄이는 것입니다. (원칙적으로 λ[][][_]에 대해 직접 정의된 다른 축약도 상상할 수 있지만, 람다에서 전통적이지는 않습니다.)

축약이 수행되는 람다의 실제 부분을 “리덱스(redex)”라고 부르고, 나머지 람다는 “컨텍스트(context)”—혹은 “구멍이 있는 표현식”—라고 부르기도 합니다. 여기서는 주로 람다를 점진적으로 평가/축약/변환/…해 나가는—근본적으로 계산적인—과정에 관심을 둘 것입니다. 하지만 과거의 많은 형식적 연구는 조금 다른 문제, 즉 “λ 변환의 미적분” 또는 “λ 미적분”에 집중했습니다—람다들 사이의 동치성을 식별하고, 즉 언제 한 λ 표현식이 다른 것으로 변환될 수 있는지, 혹은 같은 정규형을 갖는지 결정하는 일 말이죠.

그런데—앞서 언급했듯—람다와 몇 해 전 제가 자세히 다룬 콤비네이터는 밀접한 관련이 있습니다. 실제로 콤비네이터에서 논한 많은 현상이 여기 람다에서도 다양한 변형과 함께 나타납니다. 일반적으로 콤비네이터는 형식적·계산적 수준에서 람다보다 다루기 조금 쉽습니다. 하지만 람다는 적어도 개별 베타 축약 수준에서는 무엇을 하는지 해석하기 훨씬 쉽다는 확실한 장점이 있습니다. S 콤비네이터는 머리를 비트는 방식으로 작동합니다. 하지만 베타 축약은 사실상 “함수에 인수를 적용”하는 것입니다. 물론 베타 축약을 많이 하다 보면 결과가 매우 복잡해질 수 있는데—바로 그것이 여기서 이야기할 내용입니다.

람다로 하는 기초 계산

람다만으로 어떻게 익숙한 계산을 할 수 있을까요? 먼저 대상을 순수하게 람다만으로 표현하는 방법이 필요합니다. 앞서 논했듯 정수는 연속 중첩으로 표현할 수 있습니다. 이제 완전히 람다만으로 명시적 후속자(successor) 함수를 정의할 수도 있습니다. 방법은 여러 가지가 가능한데, 한 예는 다음과 같습니다:

이는 다음과 동등합니다:

0을 다음처럼 정의하거나

또는

이제 숫자 3의 표현을 구성할 수 있습니다:

이를 베타 축약으로 “평가”하면 다음처럼 줄어듭니다:

이는 위에서 사용한 3의 표현과 정확히 같았습니다.

같은 맥락에서 다음을 정의합니다:

(여기 함수들은 “커리된” 형식으로 인자를 받습니다. 예: times[3][2] 등.)

그러면 예를 들어 3×2는 다음이 되고

(베타 축약 37단계 후) 다음으로 평가됩니다:

이것을 “평가되지 않은” s와 z에 적용하면

베타 축약 하에서 다음을 얻습니다:

이는 우리가 6의 표현으로 알아보던 바로 그 표현입니다.

네, 더 나아갈 수도 있습니다. 예컨대 여기 순수 람다로 된 (아마도 최소는 아닌) 팩토리얼 함수 표현이 있습니다:

이 정의로

즉 4!는 결국 24로 평가됩니다:

이런 평가 과정을 나중에 논의하겠지만, 맞습니다, 복잡합니다. 우리가 기본 방식으로 평가를 수행하면, 이 경우에는 5067 단계가 필요합니다(연속 팩토리얼에서 필요한 단계 수는 41, 173, 864, 5067, 34470, …).

람다를 쓰는 여러 표기법

지금까지 본 바로는, 람다는—사소한 경우를 빼고—읽기 꽤 어렵다는 게 명백합니다. 꼭 그래야만 할까요? 표기하거나 렌더링하는 방법은 아주 많습니다. 뒤에서 보게 되겠지만 각 방식은 서로 다른 특징과 장점이 있으며(우리는 이를 활용할 것입니다), 그렇다고 람다를 우리 모두에게 보편적으로 쉽게 읽히게 해 주는 “해결책”은 아직 없습니다.

다음 람다를 표준 텍스트 방식으로 써 봅시다:

이는 등장하는 변수들이 어떻게 연관되는지 보여 줍니다:

각 λ는 그 결합 변수를 “스코프”하므로, z 대신 y를 “재사용”해도 됩니다:

이런 표현이 읽기 어렵게 만드는 분명한 이유 중 하나는 괄호가 너무 많다는 것입니다. 어떻게 줄일 수 있을까요? Wolfram Language에서는 언제나 f[x] 대신 f@x라 쓸 수 있습니다:

그리고 Wolfram Language에서 @ 연산자는 오른쪽 결합이므로 f@g@x는 f[g[x]]를 나타냅니다. 좋아요, @를 쓰면 꽤 많은 괄호를 없앨 수 있습니다. 하지만 대신 괄호()가 생깁니다. 이건 어떻게 할까요? 적용 연산자 •(Application)을 @ 대신 쓰는 방법이 있습니다. •는 왼쪽 결합으로 정의되어 f•g•x가 f[g][x]가 되고 f[g[x]]가 아닙니다. 그러면 우리 람다는 • 기준으로 다음과 같이 됩니다:

괄호가 이동했을 뿐 사라지지는 않았네요.

@나 •를 명시하지 않고 공백으로 표현을 약간 더 간결하게 보이게 할 수 있습니다. 하지만 표현의 의미를 알기 위해 공백이 @를 의미하는지 •를 의미하는지 정해야 합니다. Wolfram Language에서는 @가 •보다 훨씬 유용합니다(예: f@g@x는 한 함수를 적용한 다음 다른 함수를 적용하는 것을 편리하게 나타냅니다). 하지만 수리논리 초창기에는 공백을 사실상 •로 사용했습니다. 그리고 λ[x, body]는 λ x . _body_로 적었고, 우리 예제 람다는 다음처럼 됩니다:

우리는 람다를 선형(텍스트) 형태로 쓰려 했습니다. 하지만 어떤 의미에서 그것들은 항상 실제로는 트리입니다—Wolfram Language에서 표현식이 트리인 것처럼요. 예컨대 아래는

을 트리로 나타낸 것입니다:

이 트리의 잎은 변수입니다. 중간 노드는 λ…, …이거나 ……입니다. 람다에 관한 모든 것은 이 트리 표현으로 할 수 있습니다. 예컨대 베타 축약은 람다를 나타내는 트리의 일부에 대한 치환 작업으로 볼 수 있습니다:

그런데 앞서 논했듯 변수에 구체적으로 어떤 이름을 붙였는지는 중요하지 않습니다. 중요한 것은 그들이 어떤 람다와 연관되는가입니다. 이를 트리 위에 적절한 연결을 덧씌워 나타낼 수 있습니다:

이 연결들을 트리 가지를 따라 라우팅하면 어떨까요?

어떤 변수 잎에서 위로 걸어 올라가며 만나는 λ의 개수를 세어 그 변수가 어느 λ에 속하는지 알 수 있습니다. 따라서 트리의 각 잎에 숫자를 채워 람다를 나타낼 수 있습니다:

이 숫자들이 바로 앞서 논한 드브루인 지수입니다. 이제 명명 변수 람다 트리를 드브루인 지수 람다 트리로 바꿀 수 있음을 보았습니다.

이 트리를 표현식으로 쓰면 다음과 같습니다:

λ에는 더 이상 명시적 변수가 지정되어 있지 않습니다. 하지만 이 표현은 우리가 명시적으로 변수를 썼을 때와 같은 방식으로 “연결”되어 있습니다:

다시 “적용 괄호”를 •(Application) 연산자로 없앨 수 있습니다:

실은 여기서는 •도, 심지어 λ도 꼭 필요하지 않습니다. 괄호의 시퀀스만으로 모든 것을 유추할 수 있습니다. 결국 우리의 람다는 다음처럼 쓸 수 있습니다:

여기서 모든 “[” 앞에는 “암시적 λ”가 있고, 모든 숫자 쌍 사이에는 암시적 •가 있습니다. (네, 드브루인 지수가 10 미만인 경우만 다룹니다.)

이제 람다를 문자 시퀀스로 최소 표기할 수 있게 되었습니다. 간결하지만 해독이 어렵습니다. 더 나아질 수 있을까요?

가장 단순한 수준에서는 (여기서는 λ와 괄호를 명시) 모든 문자에 색 코딩을 할 수 있습니다:

이 표현은 나중에 유용할 것입니다.

하지만 어떤 “순수 문자열”도, 람다의 중첩 구조는 괄호 시퀀스에 다소 암묵적으로만 드러납니다. 더 명시적으로 만들 수 있을까요? 네, 각 중첩된 λ에 명시적으로 프레임을 씌울 수 있습니다:

또는 각 요소의 “깊이”를 표시할 수 있습니다—“타이포그래피적으로”

혹은 그래픽으로(TreeDepth의 깊이):

이것을 람다 트리 표현의 일종의 1차원으로 펼친 버전으로 생각할 수 있습니다. 또 다른 접근은 트리를 2D 그리드에 그려 Tromp 다이어그램을 만드는 것입니다:

무슨 일이 일어나는지 보기 위해 표준 트리를 Tromp 다이어그램에 겹쳐 보겠습니다:

각 수직선은 변수의 한 인스턴스를 나타냅니다. 그 선의 꼭대기는 그 변수와 연관된 λ를 나타내며, λ는 가로선으로 표현됩니다. 한 변수 인스턴스가 다른 하나에 적용될 때, 즉 u[v]일 때는 “u” 수직선에서 “v” 수직선으로 가로선이 연결됩니다.

이 설정으로 소수의 작은 람다에 대한 Tromp 다이어그램은 다음과 같습니다:

또 다른 그래픽 접근은 람다 요소들이 어떻게 “배선”되는지 직접 보여 주는 “문자열 다이어그램(string diagram)”을 사용하는 것입니다. 예를 들어 간단한 람다를 봅시다:

이는 문자열 다이어그램으로 다음처럼 나타낼 수 있습니다:

여기서의 연결성은 다음과 동일합니다:

문자열 다이어그램에서는 명시적 변수는 “납작하게” 없어졌지만, 선이 어느 λ로 되돌아가는지로 암시적으로 표시됩니다. 각 λ 노드에는 람다의 인자를 나타내는 하나의 나가는 간선과 본문에 연결되는 하나의 들어오는 간선이 있습니다. 람다를 트리로 표현할 때와 마찬가지로 람다의 “내용”은 다이어그램의 윗부분에서 “매달려” 있습니다.

몇 가지 작은 람다의 문자열 다이어그램 예는 다음과 같습니다:

이 다이어그램에서 하단으로 “나가는” 간선은 람다에서 사용되지 않는 변수를 나타냅니다. 다이어그램에 나타나는 “컵”은 λ[x, x]처럼 “즉시 사용되는” 변수를 나타냅니다. 그럼 예를 들어 λ[a, λ[b, b[b]]]에 있는 은 무엇일까요? 이는 변수를 복제(copy)하는 것을 나타내며, 여기서는 b가 두 번 사용되므로 필요합니다.

이전 예(이제 명시 변수로 표기)를 다시 보면

이 람다에 해당하는 (약간 복잡한) 문자열 다이어그램은 다음과 같습니다:

이런 문자열 다이어그램은 변수를 연관한 “파이프”를 통해 “상징적 내용의 흐름”을 정의한다고 볼 수 있습니다. 하지만 변수를 전혀 도입하지 않고 이런 흐름을 더 순수하게 표현할 방법은 없을까요? 있습니다. 콤비네이터를 쓰는 것입니다. 실제로 콤비네이터 표현과 람다 사이에는 즉각적 대응이 있습니다. 예를 들어

은 콤비네이터로 다음처럼 표현됩니다:

콤비네이터에서는 전형적으로 매우 순수하고 균일하지만 해석하기도 매우 어렵습니다. 그리고—뒤에서 논하겠지만—작은 람다 표현이 큰 콤비네이터 표현에 대응할 수 있습니다. 반대도 마찬가지여서, 예를 들어 는 람다 표현으로 다음이 됩니다:

혹은 컴팩트 형태로는:

좋습니다. 이 컴팩트한 형태는 어떤 의미에서 꽤 효율적인 표현입니다. 하지만 약간의 편법적 특징도 있습니다. 예컨대 드브루인 지수의 값이 두 자리 이상이면 어떤 “구두점”으로 구분해야 합니다.

그렇다면 람다 표현을 순수 0과 1의 시퀀스로만 표현하려면 어떨까요? 한 가지 방법은 위의 컴팩트 형태에서 “구두점 문자”를 고정 문자열로 표현하고, 드브루인 지수는 사실상 일진법(unary) 수로 표현하는 것입니다—우리 예제에서는 다음과 같습니다:

이 절차는 어떤 람다도 정수로 표현하는 방법을 제공한다고 볼 수 있습니다(그렇다고 모든 정수가 람다에 대응하는 것은 아닙니다).

람다 열거하기

람다와 그것들이 무엇을 하는지에 대한 룰리올로지 탐구를 시작하려면, 가능한 람다의 형태—즉 람다 표현식을 어떻게 열거할지—를 논의해야 합니다. 자명한 전략은 점점 더 큰 “크기”를 가진 람다 표현식을 모두 살펴보는 것입니다. 하지만 람다 표현식의 “크기”를 어떻게 정의할까요?

여기서는 주로 Wolfram Language의 LeafCount를 사용합니다. 예를 들어

은 가장 직접적인 Wolfram Language 트리 렌더링에서

“잎”이 10개이므로 “크기” 10으로 간주합니다. 람다는 보통 다음과 같은 형태로 렌더링하겠습니다:

이 경우 크기는 “드브루인 지수 잎” 또는 “변수 잎”의 개수와 λ의 개수를 합한 것입니다.

(다른 크기 측정도 고려할 수 있습니다. 예: 추상화(λ)와 적용에 서로 다른 가중치를 주거나, 드브루인 지수 잎 값에 따라 가중치를 다르게 주는 등.)

LeafCount를 측도로 쓰면, 예컨대 크기 4인 람다는 14개입니다:

트리로는 다음과 같고

Tromp 다이어그램으로는 다음과 같습니다:

람다의 개수는 크기와 함께 빠르게 증가합니다:

이 수열은 간단한 점화식으로 계산되는 c[n,0]에 해당합니다:

큰 _n_에서는 대략 n!처럼 성장하지만 약간 더 느린 듯합니다.

크기 _n_에서 표현식 트리의 최대 깊이는 이고, 평균은 대략 이며, 극한 분포는 다음과 같습니다:

람다의 실제 형태를 표시하면, 눈에 띄는 특징은 형태의 비교적 다양성입니다:

람다의 평가

람다를 “평가”한다는 것은 무엇일까요? 가장 자명한 해석은 더 이상 베타 축약을 할 수 없는 “고정점”에 도달할 때까지 베타 축약을 연속해서 수행하는 것입니다.

예를 들어 다음이 있을 수 있습니다:

드브루인 지수를 쓰면 베타 축약은 λ[][]에 대한 변환이 되며, 우리 예는 다음과 같습니다:

컴팩트 표기에서는 다음과 같고

트리로는 다음과 같습니다:

드브루인 지수 형식의 문자를 색 사각형으로 렌더링해 “시공간” 형태로 이 진화를 나타낼 수도 있습니다:

그렇다면 다른 람다는 어떨까요? 크기 3의 람다 중

어느 것도 λ[][] 패턴을 포함하지 않으며, 따라서 베타 축약이 불가능합니다. 크기 4에서도 14개 대부분이 그렇지만 예외가 하나 있어, 한 단계 베타 축약이 가능합니다:

크기 5에서는 35%의 람다가 비관성적(즉 즉시 정지하지 않음)이지만, “수명”은 여전히 짧습니다:

가장 긴 “평가 체인”은 다음입니다:

크기 6에서는 44%의 람다가 베타 축약을 허용하며, 즉시 관성 상태가 아닙니다:

길이 4의 평가 체인을 갖는 람다도 있습니다:

그리고 이제 새로운 것이 나타납니다—주기 1의 “루핑 람다”(또는 “퀸(quine)”)로, 베타 축약하에서 계속 자기 자신으로 변환되어 더 이상 베타 축약이 적용될 수 없는 고정점에 도달하지 않습니다:

크기 7에서는 절반 조금 넘는 람다가 비관성적입니다:

“자기 반복” 람다도 몇 가지 있습니다:

첫 번째는 크기 6의 자기 반복 람다의 간단한 확장입니다. 두 번째는 약간 다릅니다.

크기 7에서는 최종 반복 상태에 도달하기 전에 작은 “과도기”가 있는 경우도 있습니다(여기서는 컴팩트 표기):

이 경우 람다 트리에서 무슨 일이 일어나는지—각 베타 축약에 관여하는 트리 부분을 빨간색으로 표시해—보면 다음과 같습니다:

또한 새로운 것이 있습니다. 베타 축약이 영원히 커지는 람다로 이어지는 세 가지 경우입니다. 가장 단순한 경우는

이며, 매 단계마다 크기가 1씩 증가합니다:

다음은

인데, 한 단계 과도기를 거친 뒤 매 단계마다 크기가 4씩 증가합니다:

마지막으로는

으로, 약간 더 복잡한 방식으로 증가합니다:

연속 단계마다 4와 12씩 번갈아 증가합니다(따라서 단계 t > 1에서 크기는 8 t – 4 Mod[t + 1, 2]):

여기서 “밑바탕”에서 무슨 일이 일어나는지 보면, 매 단계마다 첫 번째 λ에 베타 축약이 반복 적용되고 있음을 알 수 있습니다:

그리고 람다 크기의 연속값을 플롯할 때 이를 편히 표시할 수 있습니다:

크기 8에서는 상황이 더 흥미로워집니다. 가능한 43,977개의 람다 중 55%가 비관성적입니다:

종결되는(terminate) 가장 긴 평가 체인은 다음에서 발생하며

길이는 12입니다:

모든 크기-8 람다 43,977개 중 성장 패턴은 단지 164가지입니다:

종결하지 않는 81개의 람다는 다양한 성장 패턴을 보입니다:

예컨대 다음은

매 단계마다 번갈아 변합니다:

다른 예로는

주기 3입니다:

때로는 다음처럼

성장과 주기성이 혼합되기도 합니다:

다음과 같은 단순 중첩 거동도 있습니다:

이 경우 외피(envelope)는 처럼 성장합니다.

좀 더 정교한 중첩 거동은 다음과 같습니다:

여기서는 외피가 _t_에 대해 선형으로 성장합니다.

마지막으로 다음은

매우 규칙적인 성장을 보입니다:

결론적으로 크기 8까지의 람다에서는 중첩 거동보다 복잡한 것은 나타나지 않습니다. 사실 이 모든 경우에 단계 _t_에서의 크기에 대한 정확한 공식을 도출할 수 있습니다.

이 공식들이 어떻게 작동하는지 대략 보려면, 다음 수열로 시작할 수 있습니다:

이 수열은 중첩적 재귀 점화식

으로 주어지며, 여기서 _t_번째 항은 다음과 같습니다:

위 첫 번째 중첩 수열에 대해서는 ( t > 1 ) 다음과 같습니다:

두 번째 것은 ( t > 3 ) 다음과 같습니다:

세 번째 것은 ( t > 1 ) 다음과 같습니다:

이런 공식들이 존재한다는 점은 놀랍고, 꽤 복잡하다는 점도 놀랍습니다. 전통 수학으로 포착 가능한 경계까지 어느 정도 데려다 주는 셈이며, 그 너머는 환원 불가능한 계산으로만 찾을 수 있습니다.

더 큰 람다의 세계

크기 8까지 람다를 체계적으로 살폈습니다. 그렇다면 더 큰 람다에서는 무슨 일이 벌어질까요?

크기 9

크기 9에서는 가능한 람다가 454,283개입니다. 수명 분포는 다음과 같습니다:

유한 수명 중 최장—55 단계—은 다음에서 발생하며

결국 다음으로 진화합니다:

각 단계에서 얻어진 람다의 크기는 다음과 같습니다:

그런데 왜 이 과정은 종결될까요? 보기 쉽지 않습니다. 생성된 트리 시퀀스를 보면, 가지가 재배열되고 사라지는 방법에 대한 어떤 암시가 보입니다:

배열 플롯도 그다지 계몽적이지 않습니다:

흔히 그렇듯, “식별 가능한 메커니즘”이 있는 것 같지 않습니다. 그냥 “그렇게 됩니다”.

수명 44로 2위인 크기-9 람다는

이며, 결국 다음으로 진화합니다:

(이는 위에서 논한 표현에서 정수 16에 해당합니다):

“배열” 형태로 보면 적어도 어떤 “메커니즘”의 힌트가 있습니다. 진화 과정에서 λ 없이 “구동 요소” 없이 순수 적용만이 점차(선형적으로) 증가합니다:

영원히 성장하는 크기-9 람다 748개 중 대부분은 궁극적으로 주기적 성장 패턴을 가집니다. 가장 긴 성장 주기(10 단계)를 가진 것은

이며, 성장 패턴은 다소 평범합니다:

더 복잡한 성장 패턴을 가진 람다는 35개뿐입니다:

크기 8에서 보았던 것과 유사한 거동이 많습니다. 외피가 선형인 중첩 성장 패턴이 있고:

궁극적으로 순수 지수적 성장이 있을 수 있으며:

더 느리지만 그래도 지수적인 성장도 있습니다(이 경우 ):

처음엔 복잡해 보이지만 결국 선형으로 귀결되는 성장도 있습니다:

그다음은 불규칙해 보이는 성장인데:

차분을 취하면 중첩 구조가 드러납니다

비록 이 경우 람다의 자세한 패턴에서 분명한 중첩 구조는 보이지 않지만요:

크기 9에서는 대략 이 정도입니다.

크기 10

좋습니다, 크기 10은 어떨까요? 이제 가능한 람다가 5,159,441개입니다. 이 중 38%는 관성이며, 0.15%는 종결하지 않습니다. 수명 분포는 다음과 같습니다:

긴 수명을 가진 람다의 예시는 다음과 같습니다:

이들 중 일부는 작은 람다로 종결하고; 수명 88인 것은 크기 342의 람다를, 두 번째 수명 56인 것은 크기 386의 람다를 산출합니다:

각각 작동 방식이 다소 다릅니다. 어떤 경우에는 거동이 꽤 체계적으로 보여 결국 정지할 것이 어느 정도 분명합니다. 다른 경우에는 전혀 분명하지 않습니다:

여러 경우에서, 그렇지만 전부는 아닌데, 이들 진화에는 선형적으로 증가하는 “죽은” 영역—실제 λ 없이 적용만으로 구성된 영역—이 보입니다. 예컨대 수명-123 사례의 최종 고정점은 다음과 같습니다:

다른 경우는 어떨까요? 놀라움이 있습니다. 예를 들어 다음을 보세요:

이를 2000 단계쯤 실행하면 균일하게 성장만 하는 것처럼 보입니다:

그런데 3779 단계 이후 갑자기 놀라운 일이 벌어집니다: 종결되며—크기 4950의 람다를 남깁니다:

연속 크기 차이를 봐도 종결의 “사전 경고”는 뚜렷하지 않습니다:

하지만 실제 생성된 람다 시퀀스(여기서는 200 단계만) 를 보면 “죽은” 적용이 축적되는 다소 상징적인 징후가 보입니다:

그리고 실제로 다음 절에서 더 오래 버티는 예를 보게 될 것입니다.

람다의 평가가 종결할지 말지 가늠하기 어렵긴 하지만, 분명한 경우도 많습니다. 예컨대 평가 체인이 궁극적으로 주기적이 되는 경우입니다. 크기 10에서는 이전보다 더 긴 주기가 있습니다. 여기 기간 27의 예가 있습니다:

그리고 크기 시퀀스에 분명한 중첩 구조가—선형으로 성장하는 외피와 함께—보이는 성장도 있습니다:

그다음은 중첩 구조에 성장이 중첩된 경우입니다:

크기 11

크기 11에서는 가능한 람다가 63,782,411개입니다. 대부분의 거동은 이전과 매우 비슷합니다. 하지만 놀라움이 있습니다. 그중 하나는 다음입니다:

또 다른 하나는 다음입니다:

여기에는 전체적인 규칙성이 보이지 않습니다. 그리고 생성된 람다의 자세한 시퀀스에서도 규칙성이 보이지 않습니다:

내가 보기엔 다른 많은 단순 계산 시스템—예: 규칙 30—처럼, 꽤 단순한 람다

가 영원히 예측 불가능한 거동을 만들어 내는 듯합니다.

결정불가능성의 문제

특정 람다의 평가 체인이 종결하는지 어떻게 알 수 있을까요? 일정 단계까지 실행해 보고 그때 종결하는지 보면 됩니다. 아마 그 시점까지 가면, 결코 종결하지 않음을 보여주는 분명한 주기적 또는 중첩 거동을 보게 될 수 있습니다. 하지만 일반적으로 종결 여부를 판단하기 위해 얼마나 오래 실행해야 하는지 알 수 없습니다.

이는 계산적 환원 불가능성이 단순 계산 시스템 세계 전반에서 발생하는 전형적인 사례입니다. 일반적으로 이는 주어진 람다 평가가 종결하는지 여부 문제는 결정불가능하다고 말하게 만듭니다—즉 그 질문에 답을 보장할 수 있는 유한 길이의 계산은 존재하지 않습니다.

하지만 실제로는 어떨까요? 적어도 충분히 작은 람다에서는 종결 여부를 가리는 게 그리 어렵지 않음을 위에서 보았습니다. 하지만 이미 크기 10에서 문제가 생깁니다. 예를 들어 다음을 보세요:

평가 첫 1000 단계는 거의 균일 증분인 크기 시퀀스를 내놓습니다:

10,000 단계 후에도 마찬가지입니다—크기는 대략 처럼 자랍니다:

하지만 실제 밑바탕의 람다 구조를—200 단계만이라도—보면 “죽은 영역”이 만들어지기 시작함을 볼 수 있습니다:

500 단계로 계속하면 죽은 영역은 거의 선형적으로 계속 자랍니다:

크기 시퀀스에서 을 빼 “디트렌딩”하면 다음과 같습니다:

분명한 규칙성이 보입니다. 이는 이 사례에서 실제 “계산적 환원 가능성의 주머니”를 식별할 수 있을지 모른다는 뜻이고—모든 단계를 명시적으로 실행하지 않고도 무슨 일이 일어날지 알아낼 수 있음을 시사합니다.

그리고 실제로 그렇습니다. 다루는 람다의 형태를 다시 보겠습니다:

두 번째 부분은 우리가 사용했던 숫자 2의 (“처치 수”) 표현임이 드러납니다. 이를 라 부르면 전체 람다는 다음에 따라 평가됩니다:

보통 정수에 대한 산술 연산을 떠올리게 됩니다. 하지만 여기서는 다른 것을 봅니다: 정수가 정수에 적용되는 모습을 보죠. 그렇다면 예를 들어

또는

는 무엇으로 평가될까요? 베타 축약을 반복하면 다음이 됩니다:

즉 은 을 줍니다. 다른 예들은 다음과 같습니다:

일반적으로는 다음과 같습니다:

이제 원래 람다를 “디코드”할 수 있습니다. 다음이

다음으로 평가되므로

이는 다음을 의미합니다:

즉 다음과 같습니다:

달리 말해, 처음에는 그렇게 보이지 않았더라도, 원래 람다의 평가는 결국 종결하며 크기 65539의 람다를 주고—약 200,000 단계가 소요될 것입니다. (흥미롭게도, 이 전체 설정은 약 30년 전에 내가 연구했던 것—형태가 e[x_][y_] x[x[y]]인 콤비네이터 유사 시스템—과 매우 비슷합니다.)

우리의 단순 람다가 종결하는 데 이토록 오래 걸린 것은 꽤 놀랍습니다. 그리고 사실 여기서 본 것을 바탕으로, 종결은 하지만 훨씬 더 오래 걸리게 할 람다를 구성하는 것은 어렵지 않습니다. 예를 들어

는 _n_회 “테트레이션(tetration)”

으로 평가되며, 대략 그만큼의 단계가 필요합니다.

다음 절에서는 테트레이션뿐 아니라 아커만 함수(Ackermann function)와 다음의 재귀 정의로 주어지는 어떤 수준의 초연산(hyperoperation)도 계산할 수 있는 람다를 구성하는 방법을 보겠습니다:

(여기서 h[1]은 Plus, h[2]는 Times, h[3]는 Power, h[4]는 테트레이션 등입니다.)

좋습니다. (사실 꽤 단순한) 람다 중에는 종결하긴 하지만 그 단계 수를 초연산으로 표현해야 할 정도로 많은 것이 있습니다. 그럼 전혀 종결하지 않는 람다는 어떨까요? 우리는 람다가 무한 단계에 걸쳐 무엇을 하는지 일일이 추적할 수 없습니다. 그렇다면 람다가 결코 종결하지 않음을 어떻게 확신할 수 있을까요?

증명을 구성해야 합니다. 때로는 람다 내부에서 근본적으로 단순한 무언가가 일어남을 쉽게 식별할 수 있어 꽤 간단합니다. 예를 들어 다음을 보세요:

이의 평가 연속 단계는 다음과 같습니다(각 베타 축약에 관여한 요소를 하이라이트):

여기서 무슨 일이 일어나는지는 매우 분명하며, 영원히 계속될 것입니다. 원한다면 수학적 귀납법을 사용해 한 단계와 다음 단계를 연관 지음으로써 무슨 일이 일어날지에 대한 형식적 증명을 구성할 수 있습니다.

그리고 언제든 반복되는 (줄기세포 같은) 핵심 “발생자(generator)”를 식별할 수 있다면, 귀납법으로 종결하지 않음을 증명할 수 있으리라 기대할 수 있습니다. 또한 우리가 보았듯 종종 연속 람다 패턴에 충분한 규칙성이 있어 (시각적으로) 종결하지 않음이 “분명”합니다. 이런 경우에는 많은 세부사항과 씨름해야 할 때가 많지만, 일반적으로 수학적 귀납법에 기반한 형식적 증명으로 가는 직선 경로를 기대할 수 있습니다.

실무에서 “시각적 분명성”을 식별하기 어려운 이유 중 하나는 람다가 너무 빨리 커져 안정적으로 시각화하기 어렵기 때문입니다. 이런 급속 성장의 기본 원천은 베타 축약이 점점 더 큰 부분식을 반복적으로 복제한다는 데 있습니다. 이런 복제가 어떤 의미에서 단순 트리를 이룬다면, (보통 여러 종류의 트리 순회를 바탕으로) 다시 귀납적 증명을 기대할 수 있습니다. 하지만 람다가 할 수 있음을 아는 대로, 초연산 계층을 올라가기 시작하면 더 복잡해질 수 있습니다. 예컨대 모든 트리의 모든 잎이 새 트리를 생성하는 상황이 생길 수 있습니다.

애초에, “무한에 관한 문장”(예: 특정 람다가 무한 단계 후에도 결코 종결하지 않음)을 증명하는 방식으로 귀납법이 타당할 것이라는 건 자명하지 않습니다. 하지만 수학에서 귀납법은 오랜 역사를 갖고 있고, 한 세기 넘게 피아노 산술(Peano arithmetic)—기초 수학에서 (원칙적으로) 사실상 보편적으로 사용되는 공리계—에 공리로 자리잡았습니다. 귀납법은 어떤 의미에서, 만약 어떤 수열(예: 정수의 수직선)에서 언제나 다음 단계로 갈 수 있다면, 그 수열에서 무한히 멀리도 갈 수 있다고 말합니다. 하지만 다루는 대상이 단순한 (정수 같은) 수열로 “펼칠 수” 없는 것이라면 어떨까요? 예컨대 어디서나 새 트리를 키우는 트리를 다룬다면? 이때는 보통의 귀납법으로는 “모든 잎에 도달”할 수 없습니다.

하지만 (현대 수학에서 궁극의 공리계로 쓰이는) 집합론에는 보통의 귀납법을 넘어서는 공리가 있고, 이로써 초한 귀납법(transfinite induction) 개념이 가능합니다. 초한 귀납법으로는 (모든 순서 집합을 “걸어갈” 수 있어) “언제나 트리가 트리를 낳는” 시스템에서도 “잎에 도달”할 수 있습니다.

이는 충분히 빠르게 성장하는 람다의 비종결성이 피아노 산술(즉 보통의 귀납법) 안에서 증명될 수 없을지라도, 집합론에서는 증명될 수 있음을 의미합니다. 하지만 집합론조차 한계가 있고, 비종결성을 증명할 수 없는 람다가 존재할 것이며, 그러한 증명을 위해서는 새로운 공리를 도입해야 할 것입니다.

그런 이슈를 가진 람다를 명시적으로 볼 수 있을까요? 여기서 이미 고려한 몇몇이 실제로 그런 사례일 가능성이 큽니다. 하지만 이를 증명하는 것은 매우 어려울 것입니다. 더 쉬운(그래도 어렵긴 한) 접근은, 피아노 산술 내에서는 모든 구성원이 종결한다는 증명이 존재할 수 없는 람다족을 명시적으로 구성하는 것입니다.

다소 복잡한 다음 정의를 고려합시다:

여기서 는 구드스틴 수열(Goodstein sequences)로, 이들이 항상 0에 도달한다는 명제는 보통 귀납법, 즉 피아노 산술만으로는 증명할 수 없는 것으로 알려져 있습니다.

다음은 비교적 단순한 람다로—구성되었는데—구드스틴 수열의 길이를 계산합니다:

정수 _n_의 표현을 입력하면, 이 람다는 해당 수열 의 길이(0에 도달하는 데 필요한 항의 수)의 표현을 계산합니다. 그리고 이 길이는 (그리고 오직 그때만) 람다 평가가 종결한다면 유한합니다. 즉 이런 종류의 모든 람다 평가가 종결한다는 명제는 모든 구드스틴 수열이 결국 0에 도달한다는 명제와 동치입니다.

그럼 실제로 이런 람다를 평가하면 어떻게 될까요? 다음은 의 처음 몇 값에 대한 결과입니다:

에서는 과정이 18 단계 후 λ[λ[2[2[1]]]]—정수 2의 표현—로 종결합니다. 이는 을 반영합니다. 에서는 38 단계 후 정수 4를 얻습니다. 이는 을 반영합니다. 에서는 훨씬 많은 단계가 필요하지만, 결국 결과는 6입니다( 을 반영). 하지만 는 어떨까요? 이 경우도 결국 종결해야 함은 알려져 있습니다. 하지만 최종 결과가 로 알려져 있으니 엄청 오래 걸릴 것입니다. 계속 가면 크기—그리고 걸리는 시간—은 훨씬, 훨씬 더 빠르게 커집니다.

이것만이 “피아노 산술의 증명 가능성”을 벗어나는 유일한 방법은 물론 아닙니다. 하지만 이런 모습이 될 수 있다는 한 예입니다.

일반적으로 람다 평가가 종결하는지 여부는 근본적으로 결정불가능—즉 어떤 유한 계산으로도 보장할 수 없음—임을 명심해야 합니다. 하지만 특정 람다 평가가 종결하지 않음을 증명하는 문제는 또 다릅니다. 람다가 무한한 수명 동안 “새로움”을 거의 만들어내지 않는다면(예: 반복적으로만 행동한다면) 그 비종결성을 비교적 간단히 증명할 수 있습니다. 하지만 람다가 하는 일이 근본적으로 다양할수록 그 증명은 더 복잡해집니다. 그리고—사실상 계산적 환원 불가능성의 결과로—행동이 임의로 복잡하고 다양한 람다가 반드시 존재합니다. 하지만 어떤 유한한 공리계도 한정된 “다양성 수준”만 포착할 수 있고, 따라서 특정 집합의 람다에 대해서만 비종결성을 증명할 수 있으리라는 점이 중요합니다.

조금 더 구체적으로, 주어진 공리계에서 종결성의 증명을 “벗어나는” 람다를 구성할 수 있는 방식을 상상해 볼 수 있습니다. 람다의 계산 보편성은 어떤 계산도 람다 평가로 인코딩할 수 있음을 시사합니다. 특히 주어진 공리계의 언어로 진술을 체계적으로 생성하고 각 진술이 그 공리계의 정리인지 여부를 결정하는 람다가 존재합니다. 그리고 모순—즉 어떤 정리와 그 부정이 동시에 나타나는—이 발견되면 그 과정이 멈추도록 구성할 수 있습니다. 즉 이 람다의 평가는 공리계의 모순을 체계적으로 찾고, 발견되면 종결합니다.

따라서 람다 평가가 결코 종결하지 않음을 증명하는 일은 그 공리계가 무모순임을 증명하는 일과 동치입니다. 하지만 근본적 사실로서, 어떤 공리계도 자신의 무모순성을 스스로 증명할 수 없습니다. 더 강력한 공리계가 필요합니다. 즉 우리가 만든 람다의 평가가 종결하지 않음을 공리계 내부에서 증명할 수 없다는 뜻입니다.

결과적으로 우리는 람다 하나의 무한 생애에 우리 공리계가 할 수 있는 모든 것을 포장해 넣을 수 있었고, 그 결과 공리계는 그 람다가 하는 일에 대해 “더 큰 무언가”—“더 멀리”—를 말할 수 없습니다. 람다의 계산 보편성은 (괴델 정리의 유비에서) 어떤 유한한 공리 모음도 모든 가능한 람다에 대해 유한한 증명을 제공할 수 없음을 함의합니다. 하지만 여기에 제시한 구성은 주어진 공리계에서 “벗어나는” 람다를 만들어내는 하나의 특정한 방법입니다. 그것만이 유일한 방법은 아닙니다. 예컨대 피아노 산술에서 비종결성이 증명 불가능한 가장 작은 람다는 무엇일까요? 위 구드스틴 수열 기반 예는 이미 꽤 작습니다. 하지만 아마도 더 작은 예들이 있을 것입니다. 물론 일반적으로 특정 람다가 실제로 예시임을 증명하는 데 필요한 난이도에는 상한이 없습니다.

가능한 모든 람다를 훑어보면, 결국 모든 가능한 공리계에서 “벗어날” 람다가 나타나는 것은 불가피합니다. 그리고 계산적 우주에서의 경험으로 볼 때, 꽤 작은 람다에서도 그들을 “길들일” 공리계의 크기와 능력이 빠르게 가속될 것으로 예상됩니다. 원칙적으로는 특정 람다를 처리하기 위해 맞춤 공리를 추가할 수도 있지만, 핵심은 곧 “임의로 작은 지렛대” 상태에 이른다는 것입니다: 추가하는 각 공리는 우리가 도달하는 람다 중 극히 작은 조각만 덮게 됩니다.

수치적으로 해석 가능한 람다

지금까지는 “람다 자체”의 평가를 논했습니다. 하지만 특정 람다가 주어지면 언제나 그 람다에 “입력”을 적용해 “무엇을 계산하는지” 볼 수 있습니다. 물론 입력 자체도 또 다른 람다입니다. 따라서 “람다에 입력을 적용”하는 것은 “람다에 람다를 적용”하는 것이고, 그 자체로 람다입니다. 그래서 기본적으로 다시 “람다 자체”를 보는 셈입니다.

하지만 우리가 제공하는 입력이 “해석 가능”하다면 어떨까요? 예컨대 위에서 썼던 표현으로 나타낸 정수에 해당하는 람다라면요. 그런 것에 람다를 적용하면—종결한다고 가정할 때—결국 또 다른 람다를 줍니다. 대부분의 경우 그 결과 람다는 “해석 가능”하지 않을 것입니다. 하지만 가끔은 그럴 수 있습니다.

예를 들어 다음을 보세요:

이 람다를 정수(람다로 표현된) 시퀀스에 적용하면 다음과 같습니다:

즉 이 람다는 정수에서 정수로 가는 수치 함수를 구현한다고 해석할 수 있습니다—이 경우 함수는 다음입니다:

그렇다면 람다가 표현할 수 있는 이런 수치 함수는 어떤 종류일까요? 람다가 계산 보편적이기 때문에, 결국 어떤 정수 함수도 표현할 수 있어야 합니다. 다만 필요한 람다는 매우 클 수 있습니다.

위에서 일찍 팩토리얼 함수의 람다 표현을 구성한 바 있습니다:

또한 (“처치 수”) 정수 m을 나타내는 람다에 정수 n 을 나타내는 람다를 적용하면 _n_의 _m_제곱을 나타내는 람다를 얻는다는 것도 알고 있습니다. 그러면 거듭제곱의 합성으로 얻을 수 있는 어떤 함수든 나타내는 람다를 구성하는 것은 간단합니다:

그리고 테트레이션 및 더 높은 초연산에 기반한 함수도 쉽게 만들 수 있습니다. 예를 들어

은 아커만 함수의 대각선을 줍니다. 그 연속 항은 다음과 같습니다:

그렇다면 “야생의 람다”는 어떨까요? “수치적으로 해석 가능”한 경우는 얼마나 자주일까요? 그리고 어떤 종류의 함수를 나타낼까요? 예컨대 크기-5 람다에서는 82개 중 10개—약 12%—가 “해석 가능”하며, 0, 1, n, n 2 함수들을 나타냅니다. 크기-10 람다에서는 “해석 가능” 비율이 약 4%로 떨어지며, 서로 다른 함수의 발생 빈도는 다음과 같습니다:

크기가 점점 커지는 람다를 보며, 함수가 처음 나타나는 주목할 만한 “최초”들은 다음과 같습니다:

그리고 특정 함수를 주는 최소 람다의 크기를 람다에 대한 그 함수의 “알고리즘적 정보량”으로 생각할 수 있습니다.

물론 다른 놀라움도 있습니다. 예를 들어 —이는 어떤 정수를 입력해도 0을 내놓지만, 그에 걸리는 단계 수는 초지수적으로 증가합니다:

우리는 어떤 람다가 어떤 “수치” 함수를 계산하는지 논했습니다. 다른 질문은 그런 계산에 얼마나 시간이(즉 베타 축약 수가) 걸리는가—또는 중간 표현에 얼마나 “공간”이 필요한가입니다. 실제로, 출력이 같더라도 서로 다른 람다는 그 출력에 도달하기 위해 서로 다른 계산적 접근과 계산 자원을 사용할 수 있습니다. 예컨대 크기-8 람다 중 n 2를 계산하는 것은 41개입니다. 그리고 이 람다들을 n = 10 케이스로 실행할 때 생성되는 중간 표현 크기(모두 같은 스케일로 플롯)는 다음과 같습니다:

이 그림들은 서로 다른 람다가 n 2를 계산하는 다양한 접근을 가짐을 시사합니다. 어떤 접근은 더 많은 “메모리”(즉 중간 람다의 크기)를 필요로 합니다. 또한 어떤 것은 다른 것보다 더 많은 시간이 들기도 합니다.

이 특정 람다 집합에서는 필요한 시간이 항상 본질적으로 _n_에 대해 선형적으로 증가하지만, 여러 가능한 속도가 있습니다:

하지만 다른 경우에는 다른 거동이 관측되며, 매우 긴 “실행 시간”도 있습니다. 실제로 일반적으로 람다에 대한 계산 복잡성 이론 전체를, 이런 경험적, 룰리올로지적 조사에서 시작해 구축할 수 있다고 상상할 수 있습니다.

지금까지 논한 것은 단일 인수 함수들입니다. 하지만 여러 인수를 가진 함수도 볼 수 있습니다. 이들은 “커리된” 형태로 람다에 공급될 수 있습니다: f[x][y] 등. 이 설정에서 은 예컨대 _x y_를, 는 x y 3을 반환합니다.

람다 평가의 멀티웨이 그래프

다음과 같은 람다 표현식을 평가한다고 합시다:

베타 축약을 하고 싶습니다. 하지만 어느 것을? 이 표현식에는 서로 다른 결과를 내는 베타 축약 후보가 3곳 있습니다:

지금까지는 항상 매 단계 “첫 번째” 베타 축약을 한다고 가정했습니다(“첫 번째”가 무엇인지 곧 논합니다). 하지만 일반적으로 모든 가능한 “평가 경로”를 살펴볼 수 있고—그것들로 멀티웨이 그래프를 만들 수 있습니다(이중 간선은 두 개의 서로 다른 베타 축약이 같은 결과를 준다는 사실을 반영합니다):

이 경우 우리의 표준 평가 경로는 다음입니다:

그리고 이 경로는 매 단계 표현식 트리에서 “가장 높은” 관련 λ(여러 개면 가장 왼쪽)를 포함하는 가장 왼쪽 바깥쪽(leftmost outermost) 베타 축약을 고름으로써 얻습니다:

하지만 위 멀티웨이 그래프에서 보듯 어떤 경로를 택하든 결국 같은 최종 결과에 도달합니다. 사실 이것은 람다의 일반적 성질(합류성 또는 Church–Rosser 성질)로, 종결하는 람다의 모든 평가가 같은 결과로 종결함을 말합니다.

참고로, 람다를 트리 형태로 렌더링하면 멀티웨이 그래프는 다음처럼 보입니다:

크기 5에서는 모든 람다가 분기 없는 사소한 멀티웨이 그래프를 줍니다. 예:

크기 6에서는 분기—그리고 병합—가 시작됩니다:

또 다른 일이 벌어집니다. “루핑 람다” λ[1[1]][λ[1[1]]]는 루프인 멀티웨이 그래프를 줍니다:

크기 7에서는 다양한 토폴로지의 멀티웨이 그래프가 나타나기 시작합니다. 대부분은 종결로 이어집니다:

(이들 중 가장 큰 멀티웨이 그래프는 λ[1[1]][λ[λ[2][1]]]에 해당하며 노드가 12개입니다.)

그리고 루프를 도는 경우도 있습니다:

마지막으로 다음이 있습니다:

여기서는 새로운 일이 벌어집니다. 멀티웨이 그래프에 매우 많은 분기가 있습니다. 5 단계 후에는 다음과 같습니다:

여기서 각 노드의 크기는 그 노드가 나타내는 람다의 크기를 뜻하고, 분홍색 노드는 추가 베타 축약이 가능한 람다입니다. 한 단계만 더 가면 멀티웨이 그래프는 다음과 같아지고

또 한 단계 더 가면 하이퍼볼릭 임베딩에서 다음과 같습니다:

이 경우 어느 분기도 종결하지 않으며, 연속 단계에서 멀티웨이 시스템의 전체 크기는 다음과 같습니다:

크기-8 람다에서는 종결하는 멀티웨이 그래프가 더 클 수 있습니다(첫 번째 경우 노드 124개):

그리고 비종결의 경우에도 온갖 새로운 토폴로지가 나옵니다. 예:

이 그래프들은 연속 5회의 베타 축약으로 얻은 것입니다. 루프로 끝나는 것들은 더 많은 축약을 해도 변하지 않습니다. 하지만 분홍색 노드가 있는 것들은 변합니다. 대부분의 경우 할 수 있는 축약 개수는 점차 증가합니다(종종 지수적이지만 여기서는 단계 _t_에서 2 t – 1):

한편 어떤 경우에는 “미해결 축약”의 수가 일정하게 유지되기도 합니다:

베타 축약의 고정점은 있다면 항상 유일하다는 것을 알고 있습니다. 그런데 고정점은 유일하지만, 영원히 계속되는 분기들도 있을 수 있을까요? 그럴 수 있습니다. 그 최초의 람다는 다음입니다:

우리의 표준 평가 방식으로 이 람다는 5 단계 후 λ[1]에서 종결합니다. 하지만 따라갈 수 있는 다른 경로가 있어 종결하지 않습니다(끝의 분홍색 노드로 표시):

그리고 단계 t에서 그런 경로의 수는 피보나치 유사 점화식으로 주어지며, 점근적으로 처럼 증가합니다.

크기-9 람다에서는 이 현상(종결/비종결)이 훨씬 더 단순한 경우로도 나타납니다:

이제 매 단계마다 오직 하나의 비종결 경로만 있습니다:

하나와 둘 사이에서 비종결 경로 수가 번갈아드는 다른 람다도 있습니다:

그리고 점근적으로 항상 정확히 5개의 비종결 경로를 갖는 또 다른 람다도 있습니다:

좋습니다. 어떤 람다는 매우 “우거진” (또는 무한한) 멀티웨이 그래프를 갖고, 어떤 것은 그렇지 않습니다. 우리의 표준 평가 과정으로 얻은 수명과는 어떻게 상관될까요?

크기-8 람다 중 유한 수명을 가진 모든 것에 대해, 멀티웨이 그래프 크기 대 수명 플롯은 다음과 같습니다:

위에서 논한 경우(여기 빨간 화살표로 표시) 하나를 제외하고는 멀티웨이 그래프가 유한입니다—그리고 그 크기와 표준 평가 수명 사이에는 어느 정도 상관이 있음을 봅니다. 다만 표준 평가에서 가장 긴 수명(12)을 가진 람다도 상당히 소박한(27 노드) 멀티웨이 그래프를 갖고

가장 큰 (유한) 멀티웨이 그래프(노드 124)는 표준 평가 수명 7인 람다에서 나타납니다.

크기 9에서는, 표준 평가 수명이 가장 긴 10개 람다의 멀티웨이 그래프(5 단계까지 계산)가 다음과 같습니다:

표준 평가 수명 17인 경우 멀티웨이 그래프는 유한합니다:

하지만 나머지 경우에는 그래프가 아마 무한일 것입니다. 예컨대 수명 55인 경우 멀티웨이 그래프에서 단계 _t_에서의 노드 수는 다음과 같이 증가합니다:

하지만 이 여러 경로 중 적어도 하나는—적어도 55 단계 후—λ[1]에서 종결함을 우리는 압니다.

다른 평가 전략들

멀티웨이 그래프는 람다에 대한 모든 가능한 베타 축약 시퀀스를 보여 줍니다. 우리의 “표준 평가 과정”은 특정 시퀀스 하나를 선택합니다—매 단계 어떤 베타 축약을 할지 고르는 특정 전략을 통해서요. 하지만 다른 전략을 쓰면 어떻게 될까요?

첫 예로 다음을 보세요:

이 람다에는 베타 축약을 할 수 있는 위치가 4곳 있습니다(위치는 Wolfram Language 관례로 지정):

우리의 표준 평가 전략은 여기서 첫째로 나열된 베타 축약을 수행합니다. 그런데 왜 그 축약이어야 하는지 어떻게 결정할까요? 람다 표현식 트리에서 가능한 각 축약의 위치를 지정하는 0과 1로 이루어진 리스트를 보고, 그중 가장 짧은 위치 리스트를 선택합니다(동률이면 사전식 정렬로 고릅니다).

트리 구조 관점에서 이는 트리 렌더링에서 “가장 높고 가장 왼쪽에 있는” 베타 축약을 고르는, 가장 왼쪽 바깥쪽 전략에 해당합니다:

그렇다면 다른 전략은 무엇이 있을까요? 전략을 지정하는 한 방법은 0과 1의 리스트 모음 중 하나를 고르는 알고리즘을 제시하는 것입니다. (지금은 한 번에 단일 위치 리스트—즉 단일 축약—만 고르는 “순차 전략”만 다룹니다.) 다른 방법은 표현식 트리에 대한 순서를 정의하고, 그 순서로 트리를 순회할 때 처음 도달하는 베타 축약을 수행한다고 정하는 것입니다. 예컨대 우리의 가장 왼쪽 바깥쪽 전략은 너비 우선 순회에 해당합니다. 또 다른 평가 전략은 가장 왼쪽 가장 안쪽(leftmost innermost)으로, 이는 트리에 대한 깊이 우선 순회에 해당하며, 베타 축약의 모든 트리 위치를 길이에 무관하게 순수 사전식 순서로 정렬합니다.

Wolfram Language에서는 TreeTraversalOrder 옵션이 TreeMap 같은 함수에서 사용할 수 있는 순회 순서를 상세히 매개화합니다—그리고 이들 각각의 순서는 람다에 대한 평가 전략을 정의하는 데 사용할 수 있습니다. Wolfram Language의 표준 ReplaceAll (/.) 연산을 표현식 트리에 적용하면—바로 우리의 표준 바깥쪽 가장 왼쪽 전략—평가 전략이 정의됩니다. 한편 λ[x_][y_]:=…와 같은 할당 후 표준 Wolfram Language 평가를 사용하면 가장 왼쪽 가장 안쪽 평가 전략이 됩니다(모든 레벨에서 머리 λ[…]가 인자보다 먼저 평가되기 때문). λ에 Hold 속성이 있다면, 이번에는 “적용적(applicative)” 순서가 됩니다. 이 경우 본문보다 인자를 먼저 평가합니다. 이 전체 설정은 몇 해 전 제가 콤비네이터에 대해 꽤 자세히 논했던 것과 사실상 동일합니다.

좋습니다. 다른 전략에서는 무슨 일이 벌어질까요? 다양한 경우에 생성되는 평가 체인의 예시는 다음과 같습니다:

각각은 멀티웨이 그래프에서 다른 경로를 따르는 것에 해당합니다:

그리고 각각은 결국 최종 결과에 도달하는 다른 방식에 해당합니다:

각 단계에서 얻은 람다의 크기를 플롯하면, 다른 전략이 서로 다른 프로파일을 가짐을 볼 수 있습니다—특히 이 경우 표준 전략이 깊이 우선보다 더 많은 단계가 걸립니다:

그렇다면 이 전략들은 정확히 무엇을 의미할까요? Wolfram Language 함수 TreeTraversalOrder 관점에서는 다음과 같습니다(“적용적”은 요소가 λ인지 •인지에 따라 달라지며, 동작이 약간 다릅니다):

트리 위치 관점에서는 다음 순서에 해당합니다:

이는 트리 노드를 지나는 다음 경로에 해당합니다:

앞서 언급했듯, 특정 람다의 평가가 종결한다면 그 결과는 사용한 평가 전략과 무관하게 항상 같습니다. 즉 멀티웨이 그래프에 종결 경로가 있다면 모두 같은 고정점으로 수렴해야 합니다. 어떤 경로는 다른 것보다 더 짧을 수 있는데, 이는 어떤 평가 전략이 다른 것보다 더 효율적일 수 있음을 나타냅니다. 위에서도 예를 하나 보았지만, 차이는 훨씬 극dramatic할 수 있습니다. 예컨대 는 표준 평가 전략으로는 74 단계가 걸리지만, 깊이 우선으로는 10 단계만 걸립니다:

실제로 표준 평가와 깊이 우선이 매우 다른 거동을 보이는 경우가 흔합니다. 때로는 하나가, 때로는 다른 하나가 더 효율적입니다. 하지만 “어떻게 가는지”에 차이가 있더라도 최종 고정점 결과는 언제나 같습니다.

멀티웨이 그래프의 일부 경로만 종결한다면 어떨까요? 크기 8까지의 람다에서는 그런 일이 없습니다. 하지만 크기 9에서는 예컨대 가 표준 평가에서는 종결하지만 깊이 우선에서는 종결하지 않습니다:

더 간단한 예로는 가 있습니다:

두 경우 모두 표준 평가는 종결로 이어지지만 깊이 우선 평가는 그렇지 않습니다. 사실 특정 람다에서 종결이 가능하다면, 우리의 표준(“가장 왼쪽 바깥쪽”) 평가 전략은 이를 성공적으로 달성할 것입니다.

하지만 종결이 전혀 불가능하다면? 다른 평가 전략은 서로 다른 거동으로 이어질 수 있습니다. 예컨대 는 주기 2 또는 주기 1의 루프에 갇힐 수 있습니다:

또한 한 전략은 영원히 커지는 람다를 내놓고, 다른 전략은 (이 사례처럼) 예컨대 크기가 주기적인 람다—즉 종결하지 않는 다른 방식—를 내놓을 수도 있습니다:

그런데 람다 집합 전체를 보면 어떨까요? 일반적으로는? 모든 멀티웨이 그래프에는 고정점, 몇 개의 루프, 그리고 (트리 같은) 무한 성장이 있을 수 있습니다. 각 전략은 멀티웨이 그래프에서 경로를 정의하며—잠재적으로 이들 결과 중 어떤 것으로도 이어질 수 있습니다. 보통 한 유형의 결과가 다른 것보다 훨씬 더 가능성이 높고—다른 유형의 결과를 얻으려면 어떤 “특별한 조정”이 필요합니다.

이 경우

거의 모든 평가 전략이 종결로 이어집니다—단, 우리가 “트리 레이아웃 순서”라 부를 수 있는 특정 전략만 제외하고요:

각 단계에서 가능한 베타 축약 중 무작위로 하나를 같은 확률로 고르는 전략을 쓰면 어떻게 될까요? 위에서 본 [1(11)][[2(211)]] 람다에 대한 몇 가지 예는 다음과 같습니다. 이 람다는 표준 평가 전략으로 74 단계가 걸립니다:

곡선 모양이 꽤 다양합니다. 하지만 주목할 점은 비종결 사례가 보이지 않는다는 것—그리고 종결까지 걸리는 시간이 표준 평가보다 상당히 더 짧다는 것입니다. 실제로 종결 시간의 분포는 표준 평가에서의 74라는 값에 겨우 닿습니다:

평가가 항상 종결하는 람다에 대해, 평가 과정에서 생성되는 표현식 크기 시퀀스는 양 끝이 “핀”으로 고정된 것으로 생각할 수 있습니다. 종결하지 않을 때는 크기 시퀀스가 더 난폭해질 수 있습니다. 예컨대 [11][1(1(1[[3]]))]의 경우들처럼요:

람다의 동치성

다음 람다들을 생각해 봅시다:

각각의 형태는 다릅니다. 하지만 모두 λ[1]로 평가됩니다. 특히 수학적 관점에서 람다를 생각한다면 이 모든 람다가 어떤 의미에서 “같은 것을 나타낸다”고 볼 수 있으며, 따라서 “동치”라고 할 수 있습니다.

크기 4까지 18개의 람다 중에서, 이런 의미에서 동치인 것은 실제로 이 세 개뿐입니다. 즉 크기 4까지 “평가 비동치” 람다는 15개입니다.

크기 5까지 총 100가지 람다 형태가 있으며—이는 68개의 서로 다른 최종 결과로 진화합니다—그리고 다중-람다 동치류는 4개입니다:

이를 그래픽으로 요약하면 다음과 같습니다:

크기 6까지 총 679가지 람다 형태가 있으며—392개의 서로 다른 최종 상태(및 하나의 “루핑 람다”)로 진화합니다—그리고 다중-람다 동치류는 16개입니다:

평가가 종결하는 람다만 보면 다음과 같습니다:

큰 크기에서, 비율은 대략 지수적으로 어떤 고정 극한값(약 1/4)으로 수렴하는 듯합니다.

하지만 이는 종결하는 람다에 대해서만입니다. 종결하지 않는 람다 사이의 동치성은 어떻게 말할 수 있을까요? 이는 “동치”를 무엇으로 정의하느냐에 달렸습니다. 한 정의는 두 람다가 진화 중 어딘가에서 동일한 람다 표현을 생성한다면 동치라고 하는 것입니다. 즉 멀티웨이 그래프가 서로 겹치는(overlap) 경우입니다.

크기 7까지 보면, 종결하지 않는 람다는 8개이고, 그들의 멀티웨이 시스템 사이에는 하나의—상당히 단순한—상응 관계가 있습니다:

크기 8까지 보면, 평가가 종결하지 않는 람다는 89개입니다. 그리고 이들 사이에는 많은 상응 관계가 있습니다. 간단한 예는 다음입니다:

더 정교한 예는 다음과 같습니다:

여기서는 이제 람다 쌍에 대한 결합 멀티웨이 그래프를 보여 줍니다. 처음 두 경우에는 루핑 람다에서 겹치고, 세 번째에서는 일련의 람다 표현에서 겹칩니다.

종결하지 않는 89개 람다 전부를 보면, 겹치는 434 쌍이 무엇인지 다음과 같이 나타납니다:

여기에는 몇 가지 미묘한 점이 있습니다. 첫째, 두 람다가 “동치로 보이는지”는 사용한 평가 전략에 달릴 수 있습니다. 예컨대 어떤 전략에서는 람다가 종결하는데, 다른 전략에서는 고정점을 “놓쳐” 종결하지 않을 수 있습니다.

또한 두 람다의 멀티웨이 그래프가 겹치더라도, 어떤 평가 전략으로는 그 겹침을 “발견”하지 못할 수 있습니다.

마지막으로, 늘 그렇듯 결정불가능성 문제가 있습니다. 람다가 종결할 것이라 하더라도, 종결까지 임의로 오랫동안 걸릴 수 있습니다. 더 나쁘게는 두 람다의 멀티웨이 그래프를 점진적으로 생성해도, 그들이 겹치는지 여부를 알아내는 일이 임의로 어려울 수 있습니다. 람다의 단일 평가 경로를 결정하는 일은 계산적으로 환원 불가능할 수 있습니다. 이런 겹침을 결정하는 일은 멀티계산적으로(multicomputationally) 환원 불가능할 수 있습니다.

람다의 인과성

람다 평가에서 각 베타 축약을 어떤 입력이 어떤 출력으로 변환되는 “사건(event)”으로 생각할 수 있습니다. 사건 V의 입력이 다른 사건 U의 출력에 의존한다면, V는 U에 인과적으로 의존한다고 말할 수 있습니다. 즉 사건 V는 U가 먼저 일어나야만 발생할 수 있습니다.

베타 축약이 많은 연쇄로 이루어진 람다 평가를 고려하면, 베타 축약 사건들 사이의 “인과 그래프”를 구축할 수 있습니다.

간단한 예로, 베타 축약 사건을 명시적으로 표시하고(이 간단한 경우 명확성을 위해 변수 이름 바꾸기를 피했습니다) 다음 평가 체인을 고려합니다:

여기서 파란 간선은 하나의 람다가—사건의 결과로—다른 람다로 변환되는 과정을 보여 줍니다. 짙은 빨간 간선은 사건들 사이의 인과 관계를 보여 줍니다. 각 간선은 한 사건에서 다른 사건으로의 인과성을 “운반하는” 하위 표현식에 대응한다고 볼 수 있습니다.

사건과 인과 간선만 남기면, 이 진화의 인과 그래프는 다음과 같습니다:

인과 간선을 따라가면 순서대로 발생해야 하는 사건들의 “시간 같은(timelike)” 연쇄를 얻습니다. 그 “가로 방향”—부분순서(poset)의 언어로는—평행해 발생할 수 있는 “공간 같은(spacelike) 분리” 사건들의 반사슬(antichain)이 있을 수 있습니다. 이 경우 첫 사건(즉 첫 베타 축약)은 다음 표현식을 만듭니다:

여기서 λ[b,…]와 첫 번째 λ[c,…]에 대해 수행할 수 있는 두 개의 축약이 있습니다. 하지만 이 축약들은 서로 완전히 독립적입니다. “공간처럼 분리”되었다고 볼 수 있습니다. 우리의 표준 평가 체계에서는 이 사건들이 정해진 순서로 발생합니다. 하지만 인과 그래프는 우리가 받는 결과가 그 순서를 요구하지 않음을 보여 주고—실제로는 이 사건들이 “병렬로” 발생하는 것을 허용함을 보여 줍니다.

많은 람다는 평가를 병렬화할 수 없으므로 단순하고 선형적인 인과 그래프를 갖습니다:

인과 그래프에 단순 분기가 있는 경우가 흔합니다—베타 축약 관점에서 완전히 분리되어 있는 λ 표현식의 조각과 관련되어, 각각을 따로 평가할 수 있는 경우입니다:

람다에 대한 인과 그래프를 구성할 때 생기는 까다로운 문제 중 하나는 정확히 무엇이 무엇에 의존하는지를 파악하는 것입니다. 이 경우 첫 번째 사건은 λ[a,…]를 포함하고, 두 번째 사건은 λ[b,…]를 포함하므로 두 사건이 독립인 듯 보일 수 있습니다. 하지만 두 번째 사건은 첫 번째 사건에서 λ[a,…]의 축약에 의해 λ[b,…]가 “활성화”되기 전까지는 발생할 수 없습니다—그 결과 두 번째 사건은 첫 번째 사건에 인과적으로 의존한다고 간주해야 하며, 인과 그래프에 다음처럼 기록됩니다:

많은 람다가 단순하고 선형적이거나 분기형 인과 그래프를 갖지만, 더 복잡한 구조를 갖는 경우도 많습니다. 종결하는 람다에 대한 예는 다음과 같습니다:

종결하지 않는 람다는 무한한 인과 그래프를 갖습니다:

여기서 주목할 점은, 진화를—람다 크기 시퀀스 관점에서—시각화했을 때 단순하지 않더라도, 인과 그래프는 보통 꽤 단순하고 반복적이라는 것입니다. 사실 이런 것을 보는 것이 람다의 진화가 종결하지 않음을 증명하는 것이나 마찬가지일 수도 있습니다. 하지만 주의할 점은, 종결하는 람다에서도 인과 그래프가 본질적으로 반복적으로 보일 수 있다는 것입니다—종결 직전까지도요.

멀티웨이 인과 그래프

이전 절에서 보인 인과 그래프들은 모두 표준(가장 왼쪽 바깥쪽) 평가 체계로 생성된 특정 람다 평가 체인의 인과 의존성을 분석해 만든 것입니다. 하지만—우리의 물리학 프로젝트처럼—모든 가능한 평가 시퀀스를 나타내는 멀티웨이 그래프의 모든 상태 사이의 인과 연결을 보여 주는 멀티웨이 인과 그래프도 만들 수 있습니다.

위 첫 인과 그래프의 멀티웨이 버전은 다음과 같습니다:

어떤 인과 그래프는 멀티웨이 경우에도 선형으로 남지만, 다른 것들은 여러 경로로 갈라집니다:

멀티웨이 인과 그래프는 보통 일반 인과 그래프보다 훨씬 더 복잡합니다. 예컨대 [1(11)][[212]]의 일반 인과 그래프는 다음인데

멀티웨이 버전은 다음과 같습니다:

한편 상태에 대한 멀티웨이 그래프는 다음과 같습니다:

즉 람다에 대해서도 멀티웨이 인과 그래프를 만들 수 있습니다. 하지만 이것들이 의미하는 바는 무엇일까요? 이야기는 다소 복잡합니다. 하지만 여기서 자세히 다루지는 않겠습니다—그 내용은 기본적으로 제가 몇 년 전 콤비네이터에 관해 논한 이야기와 동일하기 때문입니다. 다만 람다는 콤비네이터에서 고려했던 공유 부분식 DAG을 설정하게 해 주지 않습니다. 람다의 변수(또는 드브루인 지수)는 사실상 장거리 상관을 유발해, 콤비네이터에서 사용했던 모듈식 트리형 접근을 막습니다.

선형 람다의 경우

일반적으로 람다는 매우 복잡한 일을 할 수 있음을 보았습니다. 하지만 “선형 람다”라는 특정 부류는 훨씬 단순한 방식으로 거동하여 꽤 완전한 분석이 가능합니다. 선형 람다는 람다의 본문에서 각 변수가 한 번만 나타나는 람다입니다. 따라서 λ[a, a]는 선형 람다이지만, λ[a, a[a]]는 아닙니다.

처음 몇 개의 선형 람다는 다음과 같습니다:

드브루인 지수 형태는 다음과 같습니다:

선형 람다는 중요한 성질을 갖습니다. 베타 축약하에서 크기가 절대 증가하지 않는다는 것입니다. (하나의 변수의 다중 출현이 없으므로, 베타 축약은 부분식을 제거할 뿐이고 부분식 복제를 유발하지 않습니다.) 실제로 선형 람다의 평가에서는 매 단계 최대 한 개의 λ가 제거될 수 있을 뿐입니다:

선형 람다는 항상 각 λ에 하나의 변수가 있으므로, 크기는 항상 짝수입니다.

선형 람다의 개수는 주어진 크기의 전체 람다 개수에 비해 적습니다:

(점근적으로 크기 2 _m_인 선형 람다의 개수는 처럼 성장합니다.)

크기 6 선형 람다의 Tromp 다이어그램은 다음과 같습니다:

선형 람다의 평가는 항상 종결합니다. 소요 단계 수는 평가 체계와 무관하며, 최대는 λ의 개수와 같습니다. 크기 6 선형 람다에 대한 분포는 다음과 같습니다:

선형 람다의 멀티웨이 그래프는 꽤 단순합니다. 모든 λ가 서로 독립이므로, 축약 순서는 중요하지 않으며, 멀티웨이 그래프는 다이아몬드들의 모음으로 구성됩니다. 예를 들어:

크기 6에서 가능한 멀티웨이 그래프(중복도 포함)는 다음과 같습니다:

크기 8에서는 다음과 같습니다:

마지막 그래프는 더 분명히 대칭인 방식으로 다음처럼 그릴 수 있습니다:

크기 10에서는 다음과 같습니다:

선형 람다뿐 아니라, 각 변수의 출현을 0 또는 1회로 허용하는 어파인(affine) 람다도 볼 수 있습니다. 어파인 람다는 선형 람다와 매우 비슷하게 거동하지만, 이제 멀티웨이 그래프에 다음처럼 “퇴화한 다이아몬드 구조”가 일부 생깁니다:

람다 대 콤비네이터

이제 람다의 룰리올로지를 이만큼 탐구한 뒤, 몇 해 전 내가 콤비네이터에서 발견한 것과 비교하면 어떨까요? 핵심 현상 중 다수는 확실히 매우 비슷합니다. 실제로 람다와 콤비네이터 사이를 변환하기도 쉽습니다—다만 한 크기의 람다가 매우 다른 크기의 콤비네이터에 대응할 수 있습니다.

예를 들어 크기 4 람다는 다음과 같은 동등한 콤비네이터를 갖고

크기 3 콤비네이터는 다음과 같은 동등한 람다를 갖습니다:

놀랄 일은 아니지만, 드브루인 지수가 존재하기 때문에 람다는 사실상 더 큰 “알파벳”으로 작업하는 셈이라, 동등한 콤비네이터에 비해 (LeafCount 기준) 람다의 크기가 약간 작은 경향이 있습니다.

하지만 결국 람다와 콤비네이터는 “같은 일을 모두 할 수 있습니다”. 다음과 같은 사례처럼요:

계산 등가성의 원리(Principle of Computational Equivalence)는, 거동이 자명하게 단순하지 않은 시스템의 룰리올로지가 근본적 수준에서 적어도 어느 정도는 동일하다고 함의합니다.

하지만 람다는 확실히 우리에게 특유의 도전을 안겨줬습니다. 첫째, 변수와 그것이 함의하는 비국소성의 문제입니다. 마치 셀룰러 오토마톤이나 튜링 기계처럼 모든 갱신이 지역적으로 일어나는 게 아닙니다. 트리에서라도 지역적인 콤비네이터와도 다르고—하이퍼그래프에서 지역인 하이퍼그래프 재작성 시스템과도 다릅니다. 람다는 계층적이면서도 비국소적입니다. 람다 표현식은 트리 구조를 가지지만, 변수는 이 트리의 조각들을 임의로 복잡한 방식으로 엮습니다. 그리고 베타 축약은 사실상 임의로 긴 실을 당길 수 있습니다.

이 모든 것은 또 다른 이슈와 얽힙니다. 람다는 일상적으로 매우 커질 수 있습니다. Wolfram Language가 상징 구조를 다루는 아주 효율적인 방법을 제공한다고 해도, 람다가 하는 일을 압축할 분명한 방법이 없다는 점이 문제가 됩니다. 그 결과 여기서 내가 한 일들이 종종 계산 자원을 한계까지 몰아붙였습니다.

그래도 결국 우리는 람다의 룰리올로지를 탐구하는 최소한의 작업을 해냈고, 계산적 우주의 또 하나의 모퉁이가 놀랍고 경이로운 현상들로 가득 차 있음을 보았습니다. 나는 1980년대 초부터 람다가 “야생에서” 어떤 모습일지 궁금해했습니다. 그리고 마침내—오랜 세월이 지나—람다의 세계와 그 룰리올로지의 고유함과 보편성을 엿볼 수 있게 되어 기쁩니다.

참고문헌 메모

지난 90년간 람다에 관해 엄청난 양이 쓰였습니다. 하지만 대부분은 실증·룰리올로지적이라기보다 형식·이론적 초점이었습니다. 2020년에 콤비네이터에 관해 글을 쓸 때, (훨씬 더 작은) 콤비네이터 문헌에 대해 매우 방대한 서지 목록을 모으는 연구를 했습니다. 람다에 대해서는 비슷한 작업을 시도하지는 않았습니다. 하지만 콤비네이터와 람다 사이의 중첩—그리고 동등성—을 고려하면, 내 콤비네이터 서지의 상당 부분이 람다에도 그대로 적용됩니다.

콤비네이터 서지 »

감사의 말

광범위한 도움을 준 Wolfram Institute 펠로우 Nik Murzin과 Willem Nielsen에게 감사드립니다. 또한 Wolfram Institute 소속의 여러 분들—특히 Richard Assar와 Joseph Stocke—께도 감사드립니다. 더불어 여기서 설명한 내용에 대해 구체적 의견을 주신 Alex Archerman, Utkarsh Bajaj, Max Niederman, Matthew Szudzik, Victor Taelin께 감사드립니다. 수년에 걸쳐 Henk Barendregt, Greg Chaitin, Austin Jiang, Jan Willem Klop, Roman Maeder, Dana Scott, John Tromp 등 많은 분들과 람다에 대해 교류했습니다. 그리고 실무 차원에서 1970년대 후반부터 Wolfram Language와 Mathematica의 Function 함수, 그리고 그 전신인 SMP에 관해 셀 수 없이 많은 논의를 했습니다.