이 논문에서 제시하는 계산 불가능한 함수의 구성은 유한하고 비어 있지 않은 음이 아닌 정수 집합에는 가장 큰 원소가 존재한다는 원칙에 기초하고 있다. 또한 이 원칙은 현재 기준으로 매우 명확하게 정의된 집합에 대해서만 사용된다. 계산 가능한 함수의 나열을 사용하지 않으므로, 이 구성에서 대각선화 방법(diagonal process)을 사용하지 않는다. 따라서 모든 수학 분야에서 자명하게 여겨지는 원칙이 비구성적 존재를 도출해낸다는 사실이 흥미롭다.
I. 서론
이 논문의 목적은 몇 가지 매우 간단한 계산 불가능한 함수의 예를 제시하는 것이다. 이러한 예들은 단순함을 넘어서 중요한 점을 조명해준다. 함수 $f(x)$가 계산 불가능한 함수의 예로 사용되기 위해서는 $f(x)$가 일반적으로 받아들여질 만큼 명확히 정의되어 있어야 한다. 따라서 계산 불가능한 함수의 예를 구성하려는 시도는, 계산 가능한 함수(일반 재귀 함수)의 범위를 넘어서는 더 넓은 범위가 존재한다는 보편적인 확신을 반영한다. 이 넓은 범위는 잘 정의된 함수의 범위로, 그 정확한 범주는 불명확하다. 일부 학자들은 언젠가 이 범위가 모두가 수용할 수 있는 정밀한 개념으로 정의될 것이라 믿고 있다.
논의할 계산 불가능한 함수의 예들은 매우 원초적인 의미에서 잘 정의될 것이다. 여기서는 비어 있지 않은 유한한 음이 아닌 정수 집합에는 가장 큰 원소가 존재한다는 원칙만을 사용할 것이다. 또한 이 원칙은 매우 명확히 정의된 집합에만 적용될 것이며, 우리의 구성은 모든 수학 분야에서 흔히 나타나는 고려사항에 기반을 둘 것이다. 흥미로운 점은 계산 가능한 함수의 나열을 사용하지 않고도 우리의 예시들이 계산 불가능한 함수임을 보인다는 것이다. 이런 의미에서 대각선화 방법을 사용하지 않는다.
II. 용어
우리는 이 논문에서 이진 튜링 머신(즉, 이진 알파벳 0과 1을 사용하는 튜링 머신)을 사용할 것이다. 이는 클레이니의 『형식 수학(Metamathematics)』에서 우수하게 설명된 방식에 기초하고 있으며(참고 문헌 참조), 다음과 같은 예외 사항을 둔다.
첫째, 우리는 중심 이동(center shift)을 허용하지 않는다. 따라서 머신은 “덮어쓰기(overprint)” 명령을 실행한 후 반드시 이동해야 한다(이는 이후 설명을 단순화하기 위함이다). 둘째, 우리는 상태(state) 대신에 카드(card)라는 용어를 사용할 것이다. 그 이유는, 아래에서 소개할 논리 게임(바쁜 비버 게임)을 통해 튜링 머신의 개념을 초보자들에게 익숙하게 설명하는 과정에서 상태나 내부 구성(internal configuration)과 같은 용어가 초보자들에게 신비한 의미를 가지는 것처럼 느껴졌기 때문이다.
사용될 표기 규칙을 설명하기 위해, 예를 들어 3장의 카드로 구성된 이진 튜링 머신을 생각해보자. 여기서 C1, C2, C3는 각각 카드 1, 카드 2, 카드 3을 의미한다. 각 카드에서 가장 왼쪽 열은 알파벳(0과 1)을 나타내며, 다음 열은 “덮어쓰기” 열이다. 그 다음 열은 “이동(shift)” 열로, 여기서 0은 왼쪽 이동을, 1은 오른쪽 이동을 나타낸다. 마지막 열은 “호출 카드(call card)” 열로, 여기에 표시된 값은 다음에 사용할 카드의 인덱스를 나타내며, 값이 0일 경우 정지(Stop)를 의미한다. 이 표기법은 특정 카드 수를 가진 튜링 머신을 나열(또는 시리얼화)하고자 할 때 매우 편리하게 사용된다.
독자는 클레이니의 설명(참고 문헌 참조)에 따라, 이진 튜링 머신이 함수 $f(x)$를 “계산한다”는 의미를 알고 있다고 가정한다. 여기서는 음이 아닌 정수의 함수만을 고려하며, 그 값 또한 음이 아닌 정수가 되는 함수만을 다루고자 한다.
III. 바쁜 비버 게임
양방향으로 무한히 이어질 수 있는 테이프를 생각해 보자(참고 문헌 참조). 각 칸에는 0이 적혀 있으며, 전체 테이프가 0으로 채워져 있다. 이제 II장에서 설명한 3장의 카드로 구성된 튜링 머신을 시작 카드인 카드 1에서 작동시키되, 임의의 테이프 칸에서 시작해 보자. 독자는 이 머신이 몇 번의 이동 후 정지하며, 멈췄을 때 테이프에 총 여섯 개의 1이 남아 있음을 발견할 것이다. 실제로 이 특정 머신은 국제 BB-3 게임(바쁜 비버 게임의 3카드 덱 분류)에서 현재까지 가장 높은 점수를 기록한 네 가지 머신 중 하나이다. 이 게임의 규칙은 다음과 같다.
1. 참가자는 양의 정수 $n$을 선택한 뒤, 자신의 $n$-카드로 구성된 이진 튜링 머신을 만든다(II장에서 설명한 표기법을 사용한다).
2. 그는 이 머신을 모든 칸이 0으로 채워진 테이프에서 카드 1부터 시작하여 작동시키고, 머신이 일정 횟수의 이동 후에 정지함을 확인한다.
3. 이후, 참가자는 자신의 머신과 이동 횟수 $\sigma$를 국제 바쁜 비버 클럽의 회원(자격을 갖춘 사람)에게 제출한다.
4. 심판은 제출된 머신이 정확히 $\sigma$번의 이동 후에 멈추는지 확인한다. 이는 결정 가능한 문제인데, 심판은 머신을 작동시키며 $\sigma$번 이동을 넘기지 않고 확인할 수 있기 때문이다. 만약 머신이 $\sigma$번의 이동 후에도 멈추지 않으면 제출은 거부되고, 만약 이동 횟수가$\sigma$번보다 적으면 참가자에게 수정 후 재제출을 요구한다. 제출이 확인되면, 점수는 머신이 멈췄을 때 테이프에 남아 있는 1의 개수로 결정된다.
BB-$n$의 챔피언은 현재까지 BB-$n$ 분류에서 가장 높은 점수를 기록한 참가자이다. 예를 들어, BB-3 분류에서 점수 6은 최초로 R. 헤겔만(미국 해군 무기 연구소, 버지니아, 달그렌)이 기록했다. 이 점수는 이후 여러 사람이 달성했으나, 여전히 이 점수가 BB-3 분류에서 가능한 최고 점수인지에 대해서는 아무도 알지 못한다. 이 문제를 해결하고자 하는 독자는 곧 이와 같은 문제에서 어려움을 실감할 것이다. 검토해야 할 경우의 수가 방대할 뿐만 아니라, 특정한 머신이 과연 정지할지를 확인하는 것 자체가 매우 어렵기 때문이다. 이런 이유로 각 참가자는 제출 시 이동 횟수 $\sigma$도 함께 제출해야 한다.
IV. 최고 점수
이제 BB-$n$ 분류에서 가능한 최고 점수를 결정하는 문제가 생긴다. 서론에서 설명한 관점에 따라 이 문제를 신중하게 정의한다.
게임 규칙 iv로 돌아가 보면, BB-$n$ 분류의 유효한 제출은 **(M, $\sigma$)**라는 쌍이며, 다음 조건을 만족해야 한다.
(a) M은 $n$-카드로 이루어진 이진 튜링 머신이다.
(b) $\sigma$는 양의 정수이다.
(c) M은 모든 칸이 0인 테이프에서 시작 카드 C1로 시작하여 정확히 **$\sigma$**번 이동한 후 멈춘다.
규칙 iv에서 논의한 바와 같이, 제출 (M, $\sigma$)가 유효한지 여부를 결정할 수 있다. 또한, (M1, $\sigma_1$), (M2, $\sigma_2$)가 M1 = M2일 때, $\sigma_1$ = $\sigma_2$임이 명백하다. 따라서 유효한 BB-$n$ 제출의 수는 모든 가능한 $n$-카드 이진 튜링 머신의 수인 N(n)을 초과하지 않는다. N(n)은 다음과 같이 구할 수 있다.
$$N(n) = [4(n + 1)]^n$$
또한 유효한 BB-$n$ 제출이 존재한다. 예를 들어, 카드 1의 0-라인을 110으로 선택하면 한 번의 이동 후 정지하는 제출을 얻을 수 있다. 따라서 유효한 BB-$n$ 제출 집합을 **En**이라 하면, En은 다음과 같은 특성을 가진 비어 있지 않은 유한 집합이 된다.
(a) En의 요소들을 실제로 보여줄 수 있으므로, En은 구체적인 관찰에 의해 비어 있지 않다.
(b) En이 유한 집합이라는 것을 알고 있을 뿐만 아니라, 유효한 제출의 수 **Nc(n)**에 대해 다음과 같은 부등식을 만족한다.
$$1 < Nc(n) < N(n) = [4(n + 1)]^n$$
(c) 모든 쌍 (M, $\sigma$)에 대해 (M, $\sigma$) ∈ En인지 여부를 결정할 수 있다.
En은 현재 기준으로 **매우 명확하게 정의된, 비어 있지 않은 유한 집합이다. 그러나 우리는 **Nc(n)**, 즉 En의 요소 수가 $n$의 계산 가능한 함수가 아님을 보여줄 것이다. 또한, 각 유효한 제출 **(M, $\sigma$) ∈ En**에는 확정적인 점수 **u(M, $\sigma$)**가 부여된다(III장에서 설명한 대로). 그러므로 같은 이유로 이 점수들의 집합은 비어 있지 않은, 음이 아닌 정수로 구성된 유한 집합이다. 우리는 이 집합의 가장 큰 요소를 Σ(n)으로 나타낸다. 따라서,
$$\Sigma(n) = \max [u(M, $\sigma$)] \text{ for } (M, $\sigma$) ∈ En$$
이제 $\Sigma(n)$이 $n$의 계산 가능한 함수가 아님을 곧 보게 될 것이다. 그러나 특정한 값에 대해서는 $\Sigma(n)$ 을 효과적으로 구할 수 있을 가능성이 충분히 존재한다. 예를 들어, 분명히 Σ(1) = 1이다. 또한, Σ(2) = 4라는 것이 증명되었다. 위에서 BB-3 제출 중 여러 개가 6의 점수를 기록했음을 언급했으며, Σ(3) = 6일 가능성이 높다. 작은 값의 $n$에 대해 높은 점수를 얻기 어렵지만, C. Y. 리 박사는 $n$의 값이 커질수록 매우 큰 점수를 얻을 수 있다는 것을 편지로 언급했다. 리 박사의 이 주석을 발전시켜 비계산성 증명이 완성되었다.
V. $\Sigma(n)$의 성장
함수 $f(x)$, $g(x)$를 (II장에서 지정한 방식으로) 두 가지 함수라고 하자. 우리는 $f(x) > - g(x)$로 표시할 것이며, 이는 $f(x) > g(x)$가 $x$가 어떤 특정한 $x_0$보다 큰 경우에 성립함을 의미한다. 이 표기법을 사용하여 다음 정리를 증명하고자 한다.
정리. $\Sigma(n)$은 모든 계산 가능한(즉, 일반 재귀) 함수 $f(n)$에 대해 $f(n) > - \Sigma(n)$를 만족한다. 따라서 $\Sigma(n)$은 계산 가능한 함수가 아니다.
증명. 계산 가능한 함수 $f(x)$를 하나 고정하자. 보조 함수로
$$F(x) = \sum_{i=0}^{x} [f(i) + i^2]$$
를 도입한다. 참고 문헌에 따르면 $F(x)$는 계산 가능한 함수이다. 명백히
$$F(x) \leq f(x)$$
$$F(x + 1) > F(x)$$
를 만족한다.
이제 $F(x)$가 계산 가능한 함수이므로, $F(x)$를 계산하는 **C개의 카드**(상태)를 가진 이진 튜링 머신 $M_F$이 존재한다(클레이니의 설명에 따라; 참고 문헌 참조). 이제 임의의 정수 $x$를 고정하자. 그러면 $x + 1$개의 연속된 1을 출력하고 이 1들의 가장 오른쪽에서 멈추는 **$x + 1$개의 카드**를 가진 이진 튜링 머신 $M(x)$이 존재한다. 예를 들어, $x = 2$일 때 $M(2)$는 세 개의 카드를 가진다.
이제 **기호적 다이어그램**을 통해 정의된 이진 튜링 머신 $M_F(x)$를 생각하자:
$$M_F(x): M(x) \rightarrow M_F \rightarrow M_F$$
$M_F(x)$의 카드를 연속된 인덱스로 배열하면 $1 + x + 2C$개의 카드를 가진다는 것을 알 수 있다. 이 머신이 모든 칸이 0인 테이프에서 시작하면, 처음에는 오른쪽으로 이동하며 $x + 1$개의 연속된 1을 출력하고, 오른쪽에 있는 0 다음에 $F(x) + 1$개의 연속된 1을 출력하며, 다시 오른쪽에 있는 0 다음에 $F[F(x)] + 1$개의 연속된 1을 출력하고 마지막으로 정지한다. 따라서 분명히 $M_F(x)$는 BB-$1 + x + 2C$ 분류에서 유효한 제출이며 점수는 다음과 같다.
$$x + F(x) + F[F(x)]$$
따라서 이 분류에서 최대 점수 $\Sigma(1 + x + 2C)$는 다음 부등식을 만족한다.
$$\Sigma(1 + x + 2C) \geq x + F(x) + F[F(x)]$$
이제 $x^2 \geq 1 + x + 2C$와 $F(x) \geq x^2$이 명백하므로, 다음과 같은 결론을 얻는다.
$$
F(x) \geq 1 + x + 2C
$$
또한, $F(x)$는 (7)에 따라 단조 증가 함수이므로, (9)를 통해 다음을 얻는다.
$$
F[F(x)] \geq F(1 + x + 2C)
$$
(8)과 (10)으로부터
$$
\Sigma(1 + x + 2C) \geq F(1 + x + 2C)
$$
따라서 (9)를 통해서도 $F(x) \geq f(x)$이므로,
$$
\Sigma(1 + x + 2C) > f(1 + x + 2C)
$$
이를 $n = 1 + x + 2C$로 설정하여 최종적으로 다음과 같은 결론을 얻는다.
$$
\Sigma(n) > f(n)
$$
이로써 정리가 증명된다.
$\Sigma(x)$의 성장 속도는 다음과 같은 직관적인 관찰로도 나타난다. 예를 들어 $H(x) = x!$를 계산하는 튜링 머신 $M_H$는 26개 이하의 상태로 구성할 수 있다. 이제 다음과 같은 튜링 머신 연쇄를 고려해 보자:
$$
M(x) \rightarrow M_H \rightarrow M_H \rightarrow M_H
$$
(8)에 따라 이 연쇄에서 생성되는 1의 개수는 $((x!)!)!)$보다 많다. 위에서 언급한 $M_H$의 구조를 사용하여 이 머신들을 적절히 결합하면, 예를 들어 $x = 7$일 때 이 연쇄에 필요한 상태 수가 100개 이하임을 보일 수 있다. 따라서 $\Sigma(100)$은 최소한 $((7!)!)!)$ 이상이다. $\Sigma(100)$은 이보다 훨씬 더 클 가능성이 높기 때문에, $\Sigma(100)$의 하한을 구하는 것이 흥미로울 것이다.
VI. 함수 $S(n)$
우리의 정의로부터 유효한 BB-$n$ 제출 집합 $E_n$은 $n$-카드 정지기(stopper)의 집합과 일치함을 알 수 있다. 여기서 정지기란 모든 칸이 0인 테이프에서 카드 $C_1$로 시작하여 시간이 지나면 멈추는 이진 튜링 머신을 의미한다. 이제 유효한 BB-$n$ 제출 $(M, s)$에서 두 번째 좌표 $s$는 양의 정수로 이루어진 유한하고 비어 있지 않은 집합을 구성한다. 우리는 이 집합의 가장 큰 원소를 $S(n)$로 나타낸다. 따라서 $S(n)$은 $n$-카드 정지기의 이동 수의 최대값이다.
분명히,
$$
S(n) \geq 1
$$
이 성립한다. 이는 중심 이동(center-shift)을 허용하지 않기 때문에 BB-$n$ 제출은 1을 출력한 후 반드시 이동해야 한다는 점에서 명백하다. V장에서의 정리와 위 부등식으로부터,
$$
S(n) > - f(n)
$$
이 성립하며, 이는 모든 계산 가능한 함수 $f(n)$에 대해 성립한다. 따라서 $S(n)$은 계산 불가능하다. 이는 이 결과가 소위 정지 문제의 결정 불가능성과 동등하다는 사실을 독자가 쉽게 이해할 수 있을 것이다.
VII. 함수 $N_e(n)$
위에서 정의한 바와 같이 집합 $E_n$의 원소의 수(즉, $n$-카드 정지기의 수)를 나타내는 함수 $N_e(n)$은 과도하게 빠른 속도로 증가하지 않는다 [(2) 참고]. 그러나 우리는 이 함수에 대해 다음과 같이 논의할 수 있다. BB-$n$ 제출 중 정확히 $s$번의 이동 후 정지하는 제출의 수를 $N(s, n)$이라 하자. $N(s, n)$을 계산하는 것은 프로그램으로 쉽게 구현 가능하다. 비공식적으로, $N(s, n)$의 값을 구하는 방법은 주어진 이동 수 $s$보다 많지 않은 횟수만큼 각 $n$-카드 이진 튜링 머신을 실행하여 정확히 $s$번의 이동 후 멈추는 것들의 수를 기록하는 것이다. 이제,
$$
G(s, n) = \sum_{i=1}^{s} N(i, n)
$$
$$
\Phi(s, n) = N_e(n) - G(s, n)
$$
로 정의하자.
분명히, $G(s, n)$은 $s$번 이하의 이동 후 정지하는 BB-$n$ 제출의 수를 나타내므로, $G(s, n) \leq N_e(n)$이며, 따라서 $\Phi(s, n) \geq 0$이다. 또한, $s = S(n)$일 때 $G(s, n) = N_e(n)$이므로, $S(n)$은 $\Phi(s, n) = 0$이 성립하는 가장 작은 $s$ 값이 된다. 기호로 나타내면,
$$
S(n) = (\min s)[\Phi(s, n) = 0]
$$
여기서 $\min s$는 "가장 작은 $s$ 값"을 의미한다. (13)-(15)로부터, 만약 $N_e(n)$이 계산 가능하다면 $S(n)$ 역시 계산 가능할 것이라는 결론을 얻을 수 있다(참고 문헌 참조). 그러나 $S(n)$이 계산 불가능하므로, $N_e(n)$ 또한 계산 불가능함을 알 수 있다.
7.1 주석
어떤 정수 $n_0$에 대해 $N_e(n_0)$의 정확한 값을 구할 수 있었다고 가정하자. (13)-(15)로부터 우리는 이때 $S(n_0)$의 값을 결정할 수 있고, 결국 $\Sigma(n_0)$도 구할 수 있음을 알 수 있다. 이와 관련하여 독자는 여러 가지 흥미로운 논평을 떠올릴 수 있을 것이다. 예를 들어, 쉽게 증명할 수 있는 부등식
$$
S(n) \leq (n + 1) \leq \Sigma(5n) \leq 2^{\Sigma(5n)}
$$
은 몇 가지 흥미로운 관찰을 유도한다.
VIII. 요약
앞서 제시한 내용을 검토해 보면, 우리는 구성을 통해 가장 큰 원소의 원칙만을 사용했음을 알 수 있다. 이 원칙은 다음과 같다:
$E$가 비어 있지 않은 유한한 음이 아닌 정수의 집합이라면, $E$는 가장 큰 원소를 가진다.
이 원칙은 수학의 모든 분야에서 자연스럽게, 끊임없이 사용된다. 위에서 제시한 예들은 이 원칙이 매우 명확하게 정의된 집합 $E$에만 적용되더라도 구성적 수학의 영역을 넘어설 수 있음을 보여준다. 물론, 일상적인 경험을 통해 이러한 현상을 설명할 수도 있다. 예를 들어, 필자가 자동차 여행 중 특정 고속도로를 찾고자 했을 때, 한 건설 작업반장은 다음과 같은 길 안내를 해주었다. "이 길을 따라 쭉 직진하세요. 그러면 몇 개의 철제 다리를 지나게 될 겁니다. 마지막 철제 다리를 지나면, 다음 교차로에서 좌회전하세요." 다행히 이 지시로 인해 생긴 해결 불가능한 문제는 작업반의 다른 일원이 "마지막 철제 다리를 지나고 나면 리치먼드(약 130마일 거리)까지 또 다른 철제 다리는 없을 겁니다."라고 자발적으로 정보를 제공해 해결되었다. 독자는 클레이니의 뛰어난 저서를 면밀히 검토하면서 이 짧은 이야기가 계산 가능한 함수 이론의 몇 가지 기본적인 원칙을 구체적으로 보여주는 예시라는 점을 확인하는 데 흥미를 느낄 것이다.
IX. 감사의 글
필자는 벨 전화 연구소의 C. Y. 리 박사에게 여러 가지 자극적인 조언을 제공해 준 데에 깊은 감사를 표한다.
참고 문헌
- 클레이니, S. C., 『형식 수학 입문』, D. 반 노스트란드 출판, 프린스턴.
You know what's cooler than magic? Math.
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!
