4.18 처치-튜링 명제(Church-Turing Thesis)의 정식화

1. 명제의 정식화

처치-튜링 명제(Church-Turing Thesis)는 다음과 같이 정식화된다:

직관적으로 “효과적으로 계산 가능한(Effectively Computable)” 함수의 클래스는 재귀 함수(Recursive Function)의 클래스—또는 동등하게, 튜링 기계에 의해 계산 가능한 함수의 클래스, 람다 정의 가능한 함수의 클래스—와 정확히 일치한다.

이 명제는 두 개의 하위 주장으로 분해된다:

1. 형식적 → 직관적: 재귀 함수(튜링 계산 가능 함수)는 모두 직관적으로 효과적으로 계산 가능하다. 이 방향은 자명하다. 재귀 함수의 정의에 의해, 각 함수의 계산은 유한한 기계적 절차로 수행된다.

2. 직관적 → 형식적: 직관적으로 효과적으로 계산 가능한 모든 함수는 재귀 함수이다. �� 방향이 명제의 본질적 내용이며, 증명이 아닌 경험적·철학적 정당화에 의해 지지된다.

2. 명제의 인식론적 성격

2.1 수학적 정리가 아닌 이유

처치-튜링 명제는 수학적 정리(Theorem)가 아니다. 이 명제는 비형식적 ��념(“직관적으로 효과적으로 계산 가능”)과 형식적 개념(“재귀적/튜링 계산 가능”)을 동일시하는 것이며, 비형식적 ���념의 정밀한 수학적 정의가 선행되지 않으므로 수학적 증명의 대상이 아니다.

2.2 정의적 명제로서의 해석

일부 학자는 처치-튜링 명제를 “효과적 계산 ��능성“이라는 비형식적 개념에 대한 정의(Definition)의 제안으로 해석한다. 이 해석에서 명제는 ���/거짓의 문제가 아니라, 정의의 적절성(Adequacy)의 문제이다.

2.3 경험적 가설로서의 해석

다른 학자는 처치-튜링 명제를 ��증 가능한(Falsifiable) 경험적 가설로 해석한다. 만약 직관적으로 계산 가능하지만 재귀적이지 않은 함수가 발견되면, 명제는 반증된다. 현재까지 그러한 반례는 발견되지 않았다.

3. 명제를 지지하는 증거

3.1 독립적 형식화의 수렴

처치-튜링 명제의 가장 강력한 지지 증거는 독립적으로 제안된 여러 계산 모델이 모두 동일한 함수 클래스를 정의한다는 사실이다:

이 모든 클래스가 동치임이 증명되었다.

3.2 반례의 부재

80년 이상의 연구에도 불구하고, 직관적으로 계산 가능하지만 재귀적이지 않은 함수가 제시된 적이 없다.

3.3 튜링의 인간 계산자 분석

튜링이 인간 계산자의 기계적 계산 과정을 분석하여 튜링 기계의 정의에 도달한 논증은 명제의 직관적 정당화에 핵심적 역할을 한다. 괴델은 이 분석이 형식화의 올바름에 대한 결정적 논거를 제공한다고 평가하였다.

4. 명제의 변형

4.1 물리적 처치-튜링 명제(Physical Church-Turing Thesis)

물리적으로 실현 가능한 모든 계산 과정은 튜링 기계에 의해 시뮬레이션 가능하다.

이 변형은 물리 법칙에 의해 허용되는 계산 과정이 튜링 기계의 계산 능력을 초과하지 않는다고 주장한다. 양자 컴퓨팅의 등장에 의해 이 명제의 유효성이 논쟁되고 있으나, 양자 튜링 기계도 고전적 튜링 기계로 시뮬레이션 가능하므로(지수적 시간 감속을 허용할 때), 물리적 명제는 현재까지 반증되지 않았다.

4.2 강한 처치-튜링 명제(Strong Church-Turing Thesis)

다항 시간(Polynomial Time)에 물리적으로 실현 가능한 모든 계산은 확률적 튜링 기계(Probabilistic Turing Machine)에 의해 다항 시간�� 시뮬레이션 가능하다.

이 변형은 효율성까지 포함하는 명제이며, 양자 컴퓨팅에 의해 도전받고 있다. 쇼어 알고리즘(Shor’s Algorithm)이 정수 분해(Integer Factorization)를 양자 컴퓨터에서 다항 시간에 수행하는 반면, 고전적 컴퓨터에서의 다항 시간 알고리즘은 알려져 있지 않다. 이는 강한 명제의 반례가 될 수 있으나, BQP ⊆ P인지 여부(양자 다항 시간이 고전적 다항 시간에 포함되는지)가 미해결이므로 확정적이지 않다.

5. 명제에 대한 반론과 비판

5.1 초재귀(Hypercomputation) 주장

일부 학자는 튜링 기계를 초월하는 계산 모델을 제안하였다:

• 오라클 기계(Oracle Machine): 결정 불가능한 문제의 해답을 제공하는 “오라클“에 접근 가능한 기계
• 무한 시간 튜링 기계(Infinite Time Turing Machine): 초한 서수(Transfinite Ordinal) 단계까지 계산을 수행하는 기계
• 아날로그 컴퓨터(Analog Computer): 연속적 물리량을 사용한 계산

이 모델들이 물리적으로 실현 가능한지는 미해결이며, 대부분의 계산 이론가는 이 모델들이 처치-튜링 명제에 대한 실질적 반례를 제공하지 않는다고 평가한다.

5.2 인간 마음과 처치-튜링 명제

펜로즈(Roger Penrose)는 “The Emperor’s New Mind”(1989)와 “Shadows of the Mind”(1994)에서 인간의 수학적 직관이 알고리즘적 과정을 초월하며, 따라서 처치-튜링 명제가 인간 마음의 계산 능력에는 적용되지 않는다고 주장하였다. 이 주장은 괴델의 불완전성 정리에 기반하지만, 학계에서 널리 수용되지는 않는다.

6. 명제의 현대적 의의

처치-튜링 명제는 컴퓨터 과학의 가장 근본적인 가정이다. 이 명제가 정확하다면:

1. 모든 알고리즘은 튜링 기계로 포착된다: 어떤 프로그래밍 언어나 계산 장치도 튜링 기계를 초월하는 계산 능력을 갖지 못한다.
2. 결정 불가능성은 절대적이다: 튜링 기계에 의해 해결 불가능한 문제는 어떤 기계적 방법으로도 해결 불가능하다.
3. 인공지능의 원리적 범위가 규정된다: AI 체계의 계산 능력은 튜링 기계의 계산 능력을 초과하지 않는다.

처치-튜링 명제는 “계산“이라는 개��의 본질에 대한 가장 심원한 통찰을 담고 있으며, 이 통찰이 현대 컴퓨터 과학과 인공지능의 이론적 기초를 구성한다.