S와 K

유용한 계산을 수행할 수 있는 가장 단순한 컴퓨터는 어떤 모습일까? 오랫동안 이론 전산학자들은 튜링 기계나 람다 대수처럼 여러 단순한 계산 모델을 고안해 왔다. 이 문제에서는 1924년 Moses Schönfinkel이 고안한, 단 두 글자 $S$와 $K$만으로 이루어진 더욱 단순한 체계를 살펴본다. 이 글자들을 구조화하기 위해 이진 트리로 배열하며, 트리의 모든 잎 노드는 $S$ 또는 $K$ 중 하나이다.

이러한 이진 트리는 다음과 같이 문자열로 인코딩한다. 잎 노드는 $S$ 또는 $K$로 쓴다. 잎이 아닌 내부 노드는 $(ab)$로 쓰며, $a$는 왼쪽 자식의 문자열, $b$는 오른쪽 자식의 문자열이다. 예를 들어, 어떤 트리는 문자열 $((SK)K)$로 표현된다.

트리는 아래 규칙을 반복 적용하여 변환한다. 매 단계마다 규칙을 주어진 순서대로, 즉 규칙 (1)을 먼저, 그다음 규칙 (2)를 시도하며, 어떤 규칙이 변환을 수행하자마자 전체 트리의 루트에서 다시 규칙 (1)부터 검사를 시작한다.

1. 트리가 $((Ka)b)$ 형태이고 $a$, $b$가 임의의 부분 트리일 때, 전체를 부분 트리 $a$로만 바꾼다.
2. 트리가 $(((Sa)b)c)$ 형태이고 $a$, $b$, $c$가 임의의 부분 트리일 때, $((ac)(bc))$로 바꾼다. 이는 $a$와 $b$를 각각 한 번씩, $c$를 두 번 포함한다.
3. 위 두 규칙을 현재 노드에서 적용할 수 없으면, 현재 노드의 왼쪽 자식 부분 트리에 이 규칙들을 재귀적으로 적용한다.
4. 그래도 적용할 수 없으면, 현재 노드의 오른쪽 자식 부분 트리에 이 규칙들을 재귀적으로 적용한다.
5. 어느 곳에서도 규칙을 적용할 수 없으면, 결과 트리의 문자열 표현을 출력하고 멈춘다.

이 단순한 규칙들로 어떻게 계산을 하는가? 먼저 자연수의 표현을 정한다. 여러 방법이 가능하지만, Alonzo Church가 고안한 방식이 가장 널리 쓰인다. 0을 $0 = (K((SK)K))$로, 다음 수 연산자를 $\sigma = (S((S(KS))K))$로 정의한다. 그러면 자연수는 $1 = (\sigma 0)$, $2 = (\sigma 1)$, $3 = (\sigma 2)$, … 와 같이 정의되며, $\sigma$나 $0$ 같은 기호를 우리가 정의한 부분 트리로 매번 치환한다. 따라서 수 $4$는 다음 트리로 표현된다

$$\displaystyle 4 = ((S((S(KS))K))((S((S(KS))K))((S((S(KS))K))((S((S(KS))K))(K((SK)K))))))$$

이 트리에는 부분 트리 $\sigma$가 네 번 나타난 뒤 부분 트리 $0$이 따른다. 이렇게 인코딩된 수들은 다음 부분 트리로 더할 수 있다

$$\displaystyle + = ((S((SK)K))(K(S((S(KS))K))))$$

예를 들어 $+$, $3$, $4$를 각각의 부분 트리로 치환하여 트리 $((+3)4)$를 만들고 변환 규칙을 적용하면, 결국 수 $7$을 나타내는 트리에 도달한다. 곱셈은 더 간단한 부분 트리 $* = ((S(KS))K)$로 할 수 있다. 다만 $*$ 같은 연산자가 만들어 내는 결과는 같은 방식으로 동작하더라도 위에서 정의한 수와 글자 그대로 같아 보이지 않을 수 있다. 이때 정규화 연산자

$$\displaystyle N = ((S((S((SK)K))(K(S((S(KS))K)))))(K(K((SK)K))))$$

를 적용하면 동치인 수들을 같은 모습으로 만들 수 있다. 예를 들어 트리 $(N((*2)4))$에 변환 규칙을 적용하면 수 $8$을 나타내는 트리가 된다.

조금 더 손을 보면 비교, 조건문, 재귀처럼 프로그래밍 언어에서 기대할 만한 다른 연산을 위한 트리도 만들어 더 복잡한 프로그램을 작성할 수 있다. 예를 들어 다음 트리는 팩토리얼을 계산한다:

$$\displaystyle \begin{align*} ! &= ((((SS)K)((S(K((SS)(S((SS)K)))))K))((S(K(S((S((S((S((SK)K))(K(K(K((SK)K)))))) \\ &\mathrel{\phantom=} (KK)))(K((S((S(KS))K))(K((SK)K))))))))((S(K(S((S(KS))K))))((S((S(KS))K)) \\ &\mathrel{\phantom=} (K((S(K(S(K(S(K((S((SK)K))(K(K((SK)K))))))))))((S((S(KS))((S(K(S(KS)))) \\ &\mathrel{\phantom=} ((S(K(S(KK))))((S((S(KS))K))(K((S((S(KS))((S(K(S(K((S((S(KS))((S(KK))((S(KS)) \\ &\mathrel{\phantom=} ((S(K(S((SK)K))))K)))))(KK))))))((S((S(KS))K))(K((S((SK)K))(KK))))))) \\ &\mathrel{\phantom=} (K((S((SK)K))(KK))))))))))(K(K((S((S((S(KS))((S(KK))((S(KS)) \\ &\mathrel{\phantom=} ((S(K(S((SK)K))))K)))))(KK)))((SK)K))))))))))) \end{align*}$$

이것을 정규화 연산자 및 수 $4$와 결합하여 트리 $(N(!4))$에 변환 규칙을 적용하면, $24$ (즉 $4!$)를 나타내는 트리가 된다.

입력은 트리를 나타내는 여러 문자열로 이루어지며, 한 줄에 트리 하나씩 주어진다. 입력 한 줄은 $1000$자를 넘지 않는다. 입력의 마지막 줄은 빈 줄이다.

마지막 빈 줄을 제외한 각 입력 줄에 대해, 더 이상 변환이 불가능할 때까지(규칙 5) 주어진 트리에 변환 규칙을 반복 적용한 뒤, 결과 트리의 문자열 표현을 한 줄에 출력한다. 참고로 다음과 같은 일부 트리는

$$\displaystyle (((S((SK)K))((SK)K))((S((SK)K))((SK)K)))$$

규칙을 영원히 적용할 수도 있으나, 그러한 트리는 테스트 데이터에 포함되지 않는다.