계산 가능성의 개념은 매우 중요하고 아름다운 수학적 개념이다. 그리고 그것이 수학의 근본 성질을 다룬다는 점에서 보면 1930 년대에 처음 등장했다는 것이 놀라울 정도로 근자에 와서 연구되기 시작한 분야이기도 하다. 이 개념은 수학의 모든 분야에 관련된다. (물론 거의 모든 수학자들이 계산 가능성에 대해서는 종종 염두에 두지 않는 것도 사실이다.) 이 개념이 놀라운 이유 중의 하나는 몇몇 잘 정의된 수학 문제들이 실제로 계산 불가능하다는 데 있다. (튜링 기계의 정지성 여부에 대한 문제가 그 한 예이고 그 밖에 제 4 장에서 다른 예를 볼 것이다.) 왜냐 하면 그와 같은 계산 불가능한 문제가 없었더라면 계산 가능성의 개념은 별로 수학적 흥미를 일으키지 않았을 것이기 때문이다. 수학자들은 따지고 보면 퍼즐을 좋아하는 사람들이다. 어떤 수학의 연산이 계산 가능한가를 밝히는 것은 그들에게 매우 흥미로운 퍼즐이 될 수 있는 것이다. 그리고 그러한 퍼즐에 대한 일반적 해답이 계산 불가능하다는 것이 그 퍼즐을 더욱 흥미롭게 만든다.
한 가지 확실히 밝혀 두어야 할 것은 계산 가능성이 순전하고 확실한 수학적 개념이라는 사실이다. 그것은 앞에서 기술한 튜링 기계에 의한 특정 구현의 차원을 넘는 훨씬 추상적인 개념인 것이다. 앞서 밝힌 바와 같이 튜링의 기발하고 독창적인 방법을 특징짓는다고 볼 수 있는 '테이프' 니 '내적 상태' 니 하는 것에 꼭 중요성을 부가할 필요는 없다. 계산 가능성의 개념을 표현할 수 있는 다른 방법들이 있는데 역사적으로 최초의 방법은 미국의 논리학자 처치가 클린의 도움으로 만든 람다 계산법 (lambda calculus) 이다. 처치의 방법은 튜링의 방법과는 완전히 달랐고 훨씬 추상적이었다. 실제로 처치가 자신의 아이디어를 기술한 수식들을 살펴보면 그것과 '기계적' 이라고 불릴 수 있는 그 무엇과는 어떤 연결성을 발견해 내기가 쉽지 않다. 처치 방법의 중심 아이디어는 실로 그 핵심에서 볼 때 추상적이다. 즉, 하나의 수학 연산을 사용하는데 처치도 실제로 그것을 추상화 (abstraction) 라 불렀던 것이다.
여기에서 처치의 방법을 간략하게 제시하는 것이 가치가 있다고 생각된다. 이는 계산 가능성이라는 개념이 어떤 특정한 계산 기계와는 독립적이라는 것을 보이기 위함도 있지만 또한 수학에서 추상적 개념이 얼마나 강력한 수단이 될 수 있는가를 보여 주기 때문이다. 수학적 개념에 대해서 이해하기 어려운 독자들이나 그러한 것에 별로 흥미가 없는 독자는 다음 장으로 건너뛰더라도 문맥 진행에 별 문제가 없을 것이다. 하지만 그러한 독자들도 잠시만 더 같이 인내함으로써 처치의 방법이 가져다 주는 마술과도 같은 명료함을 목격할 수 있을 것이다.
이 방법은 다음과 같이 표기되는 객체들이 이루는 '세계 (universe)' 에 관한 것이다.
a, b, c, d, ..., z, a', b', ..., z', a'', b'', ..., a''', ..., a'''', ...
위의 객체들은 수학의 연산 혹은 함수를 의미한다. (표지가 달린 기호는 단지 수없이 많은 함수들을 표기하기 위하여 편의상 붙인 것이다.) 이 함수의 '독립 변수 (argument)' 들, 즉 함수가 계산에 사용하는 값들도 역시 같은 종류들인 함수이다. 게다가 함수를 계산한 결과 역시 함수이다. (실로 처치의 체계는 개념상 놀라울 정도로 경제적이라 할 수 있다.) 그러므로 다음 식이 의미하는 것은 함수 b 에 함수 c 를 적용한 결과가 함수 a 가 된다는 것이다.
a = bc
이 방법에 따르면 함수가 두 개 이상의 독립 변수를 갖는 경우도 쉽게 표현할 수 있다. 예를 들어 f 라는 함수가 두 개의 독립 변수 p 와 q 를 갖는다고 하면 다음과 같이 표현하면 된다. (함수 fp 에 q 를 적용한 결과임.)
(fp)q
또, 세 개의 변수가 필요하면,
((fp)q)r
이와 같이 계속하면 된다.
이제 강력한 연산자인 추상화에 대해서 살펴보자. 이를 위해서 그리스 문자 λ (람다) 를 쓰고 그 바로 다음에 처치의 함수를 표시하는 변수 기호, 예를 들어 x 를 써 주는데 이 변수는 다만 '명목 변수 (dummy variable)' 역할을 한다. 그 바로 다음에 대괄호로 둘러싸인 식이 나오는데 그 식 안에 등장하는 모든 x 들은 식 바로 다음에 오는 것이 들어갈 수 있는 '빈 자리' 의 역할을 한다. 그러므로,
λx.[fx]
가 의미하는 것은 함수로서 만일 a 라는 값을 적용하면 fa 를 만들어 주는 함수이다. 즉,
(λx.[fx])a = fa
다시 말하면 λx.[fx] 는 단지 함수 f 를 의미할 따름이다. 즉,
λx.[fx] = f
이것에 대해서는 약간 더 깊은 고찰이 필요하다. 처음에는 그냥 현학적이고 당연스러워 보이는 수식 장난 같아서 그 요점을 놓치기 쉽다. 우리가 잘 아는 중ㆍ고등학교 수학 문제를 예로 들어 보자. 함수 f 가 어떤 각도의 사인값을 취하는 삼각함수 연산이라고 가정하여 보자. 추상화된 함수 'sin' 은 다음과 같이 정의된다.
λx.[sin x] = sin
(각도 x 가 어떻게 '함수' 가 될 수 있는가에 대해서는 전혀 염려할 필요가 없다. 잠시 후 수라는 개념도 함수가 될 수 있음을 보일 것인데 각도도 수로 간주할 수 있기 때문이다.) 지금까지는 참으로 '당연' 하다고 볼 수 있다. 그런데 만일 'sin' 이라는 개념이 아직 발명되지 않았고 단지 다음과 같이 sin x 의 전개식 (power series) 만을 알고 있다고 가정하자.
그렇다면 다음과 같이 sin 함수를 정의할 수 있다.
좀더 간단한 예를 들면 '세제곱의 6 분의 1' 이라는 함수는 이를 지칭하는 표준화된 함수 이름이 없다 할지라도 다음과 같이 정의할 수 있다.
그리고 이 함수에 (a + 1) 이라는 값이 주어지면 다음과 같이 전개된다.
지금 다루는 내용과 좀더 관련 있는 예를 들어 보자면 처치의 기본 함수 연산만으로 구성된 다음과 같은 수식을 생각해 볼 수 있다.
λf.[f(fx)]
이 함수는 다른 함수를 받아서 이를 x 값에 두 번 반복하게 하는 역할을 한다. 예를 들면,
(λf.[f(fx)])g = g(gx)
여기에서 x 를 먼저 '추상화' 시켜 버리면,
λf.[λx[f(fx)]]
이를 다음과 같이 간략하게 표시하기도 한다.
λfx.[f(fx)]
이 연산은 g 라는 입력값을 주면 'g 를 두 번 반복한다.' 라는 함수를 생성한다. 실제로 이 함수는 처치가 자연수 '2' 를 표시하기 위하여 사용한 함수이다.
2 = λfx.[f(fx)]
그러므로 (2g)y = g(gy) 가 성립한다. 마찬가지로,
3 = λfx.[f(f(fx))], 4 = λfx.[f(f(f(fx)))], 등
처럼 되고, 0 과 1 도 다음과 같이 정의된다.
1 = λfx.[fx], 0 = λfx.[x]
실제로 처치의 2 와 3 등은 '두 번' 또는 '세 번' 의 의미에 가깝다고 볼 수 있다. 그러므로 3 이라는 연산을 함수 f 에 적용시킨 3f 는 'f 를 세 번 반복하라.' 는 의미이다. 만일 3f 에 y 를 대입하면, (3f)y = f(f(f(y))) 가 된다.
처치의 방법에서 아주 단순한 연산, 예를 들면 어떤 수에 1 을 더하는 계산이 표현될 수 있나를 살펴보기로 하자. 함수 S 는 다음과 같이 정의된다.
S = λabc.[b((ab)c)]
함수 S 가 실제로 처치의 방법으로 표현된 수에 1 을 더하는가를 확인하기 위하여 3 이라는 수를 적용시켜 보도록 하자:
S3 = λabc.[b((ab)c)]3 = λbc.[b((3b)c)]
= λbc.[b(b(b(bc)))] = 4
위에서 (3b)c = b(b(bc)) 임을 이용하였다. S 를 어떤 자연수에 적용시키더라도 마찬가지로 성립함을 알 수 있을 것이다. (실제로 S 를 λabc[(ab)(bc)] 로 정의하였더라도 같은 결과를 얻었을 것이다.)
어떤 수를 2곱 하려면 어떻게 할까? 2곱 함수는 다음과 같이 정의할 수 있다 :
D = λabc.[(ab)((ab)c)],
여기에도 3 을 대입하여 확인하여 보자.
D = λabc.[(ab)((ab)c)] 3 = λbc.[(3b)((3b)c)]
= λbc.[(3b)(b(b(bc)))] = λbc.[b(b(b(b(b(bc)))))] = 6
실제로 덧셈 (A), 곱셈 (M), 제곱 (P) 등의 기본 연산은 다음과 같이 정의될 수 있다 :
A = λfgxy.[((fx)(gx))y]
M = λfgx.[f(gx)]
P = λfg.[fg]
독자들은 위의 연산을 실제로 확인해 보든지 아니면 그대로 믿어 주기 바란다. 즉, m, n 이 처치의 함수로 표현된 두 자연수일 때 다음 식이 성립한다 :
(Am)n = m + n, (Mm)n = m × n, (Pm)n=nm
마지막 줄의 제곱 함수는 놀라울 정도로 간단하다. m = 2 이고 n = 3 인 경우를 예로 들어 확인해 보도록 하자 :
| (P2)3 = ((λfg.[fg])2)3 = (λg.[2g])3
= (λg.[λfx.[f(fx)]g])3 = λgx.[g(gx)]3 = λx.[3(3x)] = λx.[λfy.[f(f(fy))](3x)] = λxy.[(3x)((3x)((3x)y))] = λxy.[(3x)((3x)(x(x(xy))))] = λxy.[(3x)(x(x(x(x(x(xy))))))] = λxy.[x(x(x(x(x(x(x(x(xy))))))))] = 9 = 32 |
뺄셈이나 나눗셈은 이들처럼 간단하지는 않다 (실제로 'm-n' 에서 m 이 n 보다 작은 경우나 'm ÷ n' 에서 m 이 n 으로 안 나누어지는 경우에는 예외 조항을 만들어야 한다). 사실 1930 년대 초에 미국의 수학자 클린 (S. C. Kleene) 이 처치의 계산법 내에서 뺄셈을 수행하는 방법을 발견함으로써 이 분야에 큰 이정표를 수립하였다 할 수 있다. 다른 연산들도 곧 이어서 발견되었다. 결국 1937 년에 처치와 튜링이 각자 독자적인 연구에 의해서 모든 계산 가능한 (알고리즘적인) 연산들, 즉 튜링 기게로 수행될 수 있는 연산들은 처치의 계산법에 의해서도 수행될 수 있고 그 역도 성립한다는 것이 밝혀졌다.
이는 실로 놀라운 사실로서 이 결과로 인하여 계산 가능성이라는 개념이 근본적으로 객관적이고 수학적인 특성을 갖는다는 것이 설득력을 얻게 되었다. 처치의 방법에서 계산 가능성이라는 개념은 외형상 계산기와는 전혀 연관성이 없는 것처럼 보일지도 모른다. 그럼에도 불구하고 그것은 실생활의 계산과도 깊은 관계를 가지고 있다. 특히 강력하면서도 유연함을 자랑하는 컴퓨터 언어인 리스프 (LISP) 는 본질적으로 처치의 람다 계산법의 기본 구조를 사용하고 있다.
앞서 잠시 언급한 바와 같이 계산 가능성을 정의하는 데 다른 방법들도 있다. 포스트가 제안한 계산기의 개념도 튜링 기계와 흡사한데 튜링과 비슷한 시기에 튜링과는 무관하게 독자적으로 개발된 것이다. 또, 그 편의성 때문에 지금도 많이 사용되고 있지만 허브랑 (J. Herbrand) 과 괴델에 의한 계산 가능성 (재귀성) 의 정의도 있다. 그보다 약간 먼저 커리 (H. B. Curry) 는 1929 년에, 또 쇤핀켈 (M. Schönfinkel) 은 1924 년에 각각 다른 방법을 제안하였는데 처치의 계산법은 이들 방법으로부터 일부 영향을 받았다고 할 수 있다. 계산 가능성에 대한 현대적 방법들 (예를 들면, 1980 년에 커틀랜드 [N. G. Cutland]에 의해서 제안된 무한 레지스터 기계) 는 훨씬 실용적이라는 점에서 튜링의 원래 기계와는 현저하게 다르다. 그러나 어떤 방법을 취하건간에 개념적으로는 똑같은 계산 가능성을 다루고 있는 것이다.
수많은 다른 수학적 개념들, 특히 심오한 아름다움과 근본적인 내용을 지니고 있는 수학 개념들에서 볼 수 있는 것처럼 계산 가능성이라는 개념도 그 나름대로의 플라톤적 실체를 소유한 것같이 여겨진다.