4.20 계산 가능 함수(Computable Function)의 정의와 범위

1. 계산 가능 함수의 정의

계산 가능 함수(Computable Function)는 튜링 기계에 의해 계산될 수 있는 함수이다. 처치-튜링 명제(Church-Turing Thesis)에 의해, 이 정의는 다음과 동치이다:

부분 재귀 함수(Partial Recursive Function)
람다 정의 가능 함수(Lambda Definable Function)
알고리즘에 의해 계산 가능한 함수

1.1 전계산 가능 함수(Total Computable Function)

모든 입력에 대해 정의되는(즉, 해당 튜링 기계가 모든 입력에 대해 정지하는) 계산 가능 함수를 전계산 가능 함수(Total Computable Function) 또는 재귀 함수(Recursive Function)라 한다.

1.2 부분 계산 가능 함수(Partial Computable Function)

일부 입력에 대해 정의되지 않을 수 있는(즉, 해당 튜링 기계가 정지하지 않을 수 있는) 계산 가능 함수를 부분 계산 가능 함수(Partial Computable Function) 또는 부분 재귀 함수(Partial Recursive Function)라 한다.

2. 계산 가능 함수의 열거

2.1 효과적 열거

부분 계산 가능 함수는 효과적으로 열거(Effectively Enumerate) 가능하다. 모든 튜링 기계를 $M_0, M_1, M_2, \ldots$ 로 열거하면, 대응하는 부분 계산 가능 함수를 $\varphi_0, \varphi_1, \varphi_2, \ldots$ 로 열거할 수 있다. 여기서 $\varphi_e$ 는 인덱스(Gödel Number) $e$ 를 가진 튜링 기계가 계산하는 부분 함수이다.

2.2 열거의 비단사성

하나의 함수에 대해 여러 인덱스가 대응할 수 있다. 동일한 함수를 계산하는 상이한 튜링 기계가 존재하기 때문이다. 그러나 동일한 인덱스에 대해서는 유일한 함수가 대응한다.

3. 계산 불가능 함수의 존재

3.1 가산성 논변

부분 계산 가능 함수의 집합은 가산(Countable)이다. 이는 부분 계산 가능 함수가 자연수에 의해 열거 가능하기 때문이다.

그러나 $\mathbb{N} \rightarrow \mathbb{N}$ 전함수의 집합은 비가산(Uncountable)이다. 칸토어의 대각선 논법에 의해 $\vert \mathbb{N}^{\mathbb{N}} \vert = 2^{\aleph_0} > \aleph_0$ 이다.

따라서 “대부분의” 함수 $f: \mathbb{N} \rightarrow \mathbb{N}$ 은 계산 불가능하다.

3.2 구체적 계산 불가능 함수

정지 함수(Halting Function):

$h(e, x) = \begin{cases} 1 & \text{if } \varphi_e(x) \text{ is defined (halts)} \\ 0 & \text{otherwise} \end{cases}$

정지 함수는 계산 불가능하다(정지 문제의 결정 불가능성).

비지 비버 함수(Busy Beaver Function):

$BB(n) = \max\{k \mid \exists \text{ } n\text{-state TM } M, \, M \text{ writes } k \text{ 1's on blank tape and halts}\}$

$BB(n)$ 은 $n$ -상태 튜링 기계가 빈 테이프에서 시작하여 정지할 때 쓸 수 있는 1의 최대 수이다. 비지 비버 함수는 어떤 계산 가능 함수보다도 빠르게 성장하며, 따라서 계산 불가능하다.

알려진 비지 비버 값:

$BB(1) = 1$
$BB(2) = 4$
$BB(3) = 6$
$BB(4) = 13$
$BB(5) \geq 47,176,870$
$BB(6)$ 이상은 미지이다.

콜모고로프 복잡도 함수(Kolmogorov Complexity):

$K(x) = \min\{\vert p \vert \mid U(p) = x\}$

문자열 $x$ 를 출력하는 가장 짧은 프로그램의 길이. 콜모고로프 복잡도 함수는 계산 불가능하다.

계산 가능 집합과 재귀적으로 열거 가능한 집합

계산 가능 집합(Computable Set, Decidable Set)

집합 $A \subseteq \mathbb{N}$ 이 계산 가능(Computable)하다 함은, $A$ 의 특성 함수(Characteristic Function):

$\chi_A(x) = \begin{cases} 1 & \text{if } x \in A \\ 0 & \text{if } x \notin A \end{cases}$

가 전계산 가능 함수인 것이다. 이는 임의의 $x$ 에 대해 $x \in A$ 인지 아닌지를 알고리즘적으로 판정 가능함을 의미한다.

3.3 재귀적으로 열거 가능한 집합(Recursively Enumerable Set, RE Set)

집합 $A \subseteq \mathbb{N}$ 이 재귀적으로 열거 가능(RE)하다 함은, $A$ 의 반특성 함수(Semi-Characteristic Function):

$f(x) = \begin{cases} 1 & \text{if } x \in A \\ \text{undefined} & \text{if } x \notin A \end{cases}$

가 부분 계산 가능 함수인 것이다. 이는 $x \in A$ 인 경우 이를 확인할 수 있지만, $x \notin A$ 인 경우 확인이 보장되지 않음을 의미한다.

관계

$\text{계산 가능 집합} \subsetneq \text{RE 집합} \subsetneq \mathcal{P}(\mathbb{N})$

집합 $A$ 가 계산 가능인 것은 $A$ 와 $\overline{A}$ (보집합)가 모두 RE인 것과 동치이다.

4. 계산 가능 함수의 성질

4.1 효과적 합성(Effective Composition)

두 계산 가능 함수의 합성은 계산 가능하다. $f$ 와 $g$ 가 계산 가능하면 $g \circ f$ 도 계산 가능하다.

4.2 비효과적 연산

계산 가능 함수에 대해 닫히지 않는(Not Closed) 연산이 존재한다:

보집합(Complementation): $A$ 가 RE이면 $\overline{A}$ 가 RE일 필요는 없다.
무제한 전칭 양화: $\forall y \, P(x, y)$ 에서 $P$ 가 계산 가능하더라도 전칭 양화는 계산 가능하지 않을 수 있다.

4.3 라이스의 정리(Rice’s Theorem)

부분 재귀 함수의 인덱스 집합 $\{e \mid \varphi_e \in \mathcal{C}\}$ 에 관한 모든 비자명 성질은 계산 불가능하다. 이 정리는 프로그램의 행동적 성질(Behavioral Property)을 프로그램의 코드로부터 알고리즘적으로 판별하는 것이 일반적으로 불가능함을 확정한다.

5. 계산 가능성의 인공지능에 대한 함의

5.1 인공지능의 원리적 능력

인공지능 체계는 디지털 컴퓨터(튜링 기계의 물리적 구현)에서 실행되므로, 계산 가능 함수의 범위가 인공지능의 원리적 능력의 상한을 결정한다.

5.2 인공지능의 원리적 한계

계산 불가능한 함수와 결정 불가능한 문제는 인공지능에 의해서도 일반적으로 해결될 수 없다. 예를 들어, 임의의 프로그램이 특정 성질을 갖는지를 자동으로 판별하는 것(라이스의 정리에 의해 결정 불가능)은 어떤 인공지능 체계에 의해서도 일반적으로 수행될 수 없다.

5.3 실용적 관점

결정 불가능성은 최악의 경우(Worst Case)에 관한 결과이며, 특정 인스턴스나 제한된 문제 클래스에 대해서는 알고리즘적 해결이 가능할 수 있다. 현대 인공지능의 성공은 이론적 한계에도 불구하고 실용적으로 중요한 문제 클래스에 대해 효과적인 해법이 존재함을 보여준다.