튜링 멈춤 문제와 괴델의 불완전성 정리, 그대로 멈춰라

정지 문제란 무엇인가?

처음 프로그래밍을 할 때, 누구나 한 번쯤은 프로그램을 작성한 후 예상치 않게 컴퓨터가 멈추거나, 프로그램이 끝없이 실행되는 상황을 경험했을 것입니다. 여러분이 고심 끝에 작성한 코드가 실행되길 기대했는데, 프로그램이 멈추지 않고 계속해서 실행된다면 어떤 기분이 들까요? 심지어 이 프로그램이 여러분의 컴퓨터 자원을 모두 소모해 다른 작업도 방해한다면 단순히 불편함을 넘어서, 시스템 성능에 큰 문제를 일으킬 수 있습니다.

 

그러므로 프로그램을 작성할 때, 프로그램이 주어진 입력값에 대해 반드시 종료 될지(정지 문제), 혹은 계속해서 실행 될지(무한 실행 문제)를 미리 판별하는 것이 매우 중요합니다. 프로그램의 정지 여부를 미리 판단할 수 있다면, 예상치 못한 오류를 줄이고, 시스템의 안정성을 높일 수 있기 때문이죠.

정지 문제와 무한 실행 문제

정지 문제와 무한 실행 문제의 개념을 이해하기 위해, 예시를 살펴보겠습니다.

소인수 분해 프로그램: 정지 문제

먼저, 소인수 분해 프로그램을 생각해보겠습니다. 소인수 분해 프로그램은 어떤 자연수 $n$을 입력으로 받아서, 그 수를 소수들로 분해합니다. 예를 들어, $60$을 입력하면 프로그램은 $60$을 $2 \times 2 \times 3 \times 5$로 소인수 분해하고, 그 결과를 출력한 뒤 종료됩니다.

def prime_factors(n):
    factors = []
    divisor = 2
    while n > 1:
        while n % divisor == 0:
            factors.append(divisor)
            n //= divisor
        divisor += 1
    return factors

# 프로그램 실행
print(prime_factors(60))  # 출력: [2, 2, 3, 5]

이 프로그램이 멈추는 이유는 무엇일까요? 산술의 기본 정리에 의해 모든 자연수는 반드시 소인수로 분해되기 때문입니다. 즉, 1보다 큰 모든 자연수는 소수의 곱으로 고유하게 표현될 수 있기 때문이지요. 수학적으로 보장된 사실로부터, 어떤 자연수를 입력 하더라도 프로그램은 그 수를 소수들로 완전히 분해할 수 있으며, 더 이상 나눌 수 없는 상태가 되면 프로그램은 자연스럽게 종료됩니다.

따라서 이 프로그램은 주어진 수를 소인수로 완전히 분해한 후에 멈추고 종료되므로, 정지 문제의 예시입니다.

소수 찾기 프로그램: 무한 실행 문제

반면에, 소수 찾기 프로그램은 이와는 다른 특징을 가지고 있습니다. 이 프로그램은 자연수 2부터 시작하여 모든 자연수를 하나씩 살펴보면서 그 숫자가 소수인지 확인하고, 소수일 경우 출력합니다. 그러나 이 프로그램은 한 번 시작하면 끝나지 않습니다.

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def find_primes():
    num = 2
    while True:
        if is_prime(num):
            print(num)
        num += 1

# 프로그램 실행
find_primes()

왜 소수 찾기 프로그램은 멈추지 않을까요? 바로 소수는 무한히 존재하기 때문입니다. 고대 그리스의 수학자 에우클레이데스(유클리드)는 소수가 무한히 많다는 것을 이미 증명했습니다.

[!Note] 유클리드의 증명

1. 임의의 유한 소수 목록이 있다고 가정합니다.
2. 그 목록에 있는 모든 소수를 곱하고 1을 더한 새로운 수를 생각합니다.
3. 이 새로운 수는 목록에 있는 소수들 중 어느 하나로도 나누어지지 않습니다. 따라서 이 수는 새로운 소수이거나, 새로운 소수를 포함하는 또 다른 소수의 곱으로 분해될 수 있습니다.
4. 이 과정을 반복하면, 무한히 많은 소수가 존재함을 알 수 있습니다.

소수 찾기 프로그램은 이 무한한 소수들을 찾기 위해 끝없이 실행됩니다. 프로그램이 멈추지 않고, 계속해서 새로운 소수를 찾아내려 하기 때문에 이 프로그램은 무한 실행 문제의 대표적인 예시입니다. 이러한 프로그램은 끝나지 않으며, 우리가 예측한 시간 안에 멈출 수 없습니다.

 

미리 정지하는지 판단할 수 있다면?

만약 컴퓨터 프로그래밍에서 정지 문제와 무한 실행 문제를 미리 판단할 수 있다면, 수학적 추측이나 난제를 풀어나가는 데 매우 중요한 도구가 될 수 있습니다. 그 예로, 아직 증명되지 않은 골드바흐의 추측을 탐구해보겠습니다.

골드바흐의 추측은 “모든 2보다 큰 짝수는 두 소수의 합으로 나타낼 수 있다”는 가설입니다. 이 추측은 오랜 시간 동안 수많은 수학자들에 의해 연구되었지만, 아직까지 완전히 증명되거나 반증되지 않은 상태입니다.

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num ** 0.5) + 1):
        if num % i == 0:
            return False
    return True

def check_goldbach_conjecture():
    n = 4
    while True:
        found = False
        for i in range(2, n):
            if is_prime(i) and is_prime(n - i):
                found = True
                print(f"{n} = {i} + {n - i}")
                break
        if not found:
            print(f"골드바흐의 추측에 반하는 수 발견: {n}")
            return False
        n += 2

check_goldbach_conjecture()

골드바흐의 추측을 검증하기 위해, 우리는 짝수 $n$을 하나씩 증가 시키며, 각 짝수가 두 소수의 합으로 나타낼 수 있는지를 확인하는 과정을 생각해볼 수 있습니다.

1. 짝수 $n$ 설정:
   • 이 프로그램은 $4$부터 시작하여 짝수 $n$을 설정한다. $4$는 소수가 아닌 가장 작은 짝수로서, 첫 번째 검증 대상으로 선택된다.
2. 두 소수의 합으로 나타내기:
   • 설정된 짝수 $n$에 대해, 가능한 모든 소수 쌍 $(p, q)$을 찾다. 여기서 $p$와 $q$는 둘 다 $n$보다 작은 소수다.
   • $p + q = n$이 성립하는 소수 쌍이 존재하면, 그 짝수 $n$은 골드바흐의 추측에 부합한다.
3. 모든 가능성 탐색:
   • 가능한 모든 소수 쌍을 탐색하였으나, 어떤 소수 쌍도 $n$을 두 소수의 합으로 나타낼 수 없다면, 그 즉시 프로그램은 골드바흐의 추측이 틀렸음을 발견한 것이 된다.
   • 반대로, 만약 모든 소수 쌍을 탐색한 결과 $n$을 두 소수의 합으로 나타낼 수 있다면, 프로그램은 다음 짝수 $n + 2$로 넘어가서 같은 과정을 반복다.

만약 이 프로그램이 특정 짝수 에서 두 소수의 합으로 나타낼 수 없는 경우를 발견한다면, 그 즉시 프로그램은 멈추게 됩니다. 이때 프로그램은 골드바흐의 추측에 반하는 수를 발견한 것이므로, 골드바흐 추측을 틀렸다는 것을 밝혀낼 수 있습니다.

반대로, 프로그램이 모든 짝수 $n$에 대해 두 소수의 합으로 표현될 수 있는지를 끝없이 검증하지만, 어느 짝수에서도 반례를 찾지 못한다면, 프로그램은 결코 멈추지 않을 것입니다. 만약 우리가 이 프로그램이 정지 문제가 아니라는 것을 수학적으로 증명할 수 있다면 즉, 특정 $n$에서 결코 멈추지 않을 것임을 수학적으로 설명할 수 있다면, 이 프로그램은 무한히 실행될 수밖에 없으며, 따라서 골드바흐의 추측이 모든 짝수에 대해 참이라는 결론을 내릴 수 있습니다.

그러므로 정지 문제와 무한 실행 문제를 미리 판단할 수 있다면, 수학적 난제를 푸는 과정에서 복잡한 계산을 줄이고, 더 효율적으로 문제를 해결할 수 있습니다.

앨런 튜링의 정지 문제

오라클(Oracle)은 그리스 신화에서 유래한 용어로, 신탁을 통해 미래를 예언하거나 중요한 질문에 대한 답을 주는 신성한 존재를 의미합니다.

앨런 튜링은 컴퓨터 과학의 기초를 다지는 과정에서 계산 가능성에 대한 근본적인 질문을 연구하면서, '모든 프로그램에 대해 그 프로그램이 특정 입력에서 멈출지 여부를 항상 정확하게 판단할 수 있는 프로그램 즉, 정지 오라클(Halting Oracle)이 있을까?'라는 질문을 던졌습니다. 여러분은 이러한 프로그램이 존재할 수 있다고 생각하시나요? 만약 존재한다면 프로그래밍할 수 있는 모든 증명 문제는 손 쉽게 해결할 수 있을 것입니다. 하지만 아직까지 많은 난제들이 남아 있는 것으로 보아 이러한 프로그램은 존재할 수 없을 것 같습니다. 튜링 역시 '그런 프로그램은 존재하지 않는다'는 결론을 내렸습니다.

튜링의 증명은 '만약 정지 오라클이 존재한다고 가정하면 어떤 모순이 발생할까?'라는 생각에서 출발합니다.

 

1. 모든 프로그램의 리스트
앨런 튜링은 문제를 해결하기 위해 튜링 기계(Turing Machine)라는 개념을 도입했습니다. 튜링 기계는 매우 단순한 수학적 모델로, 현재 우리가 사용하는 모든 컴퓨터 프로그램을 표현할 수 있는 계산 모델입니다. 튜링 기계는 무한히 길 수 있는 테이프 위에서 동작하는 기계로, 테이프에 기록된 기호를 읽고, 쓰고, 왼쪽 또는 오른쪽으로 움직일 수 있으며, 특정 규칙에 따라 상태를 변경합니다.

모든 컴퓨터 프로그램은 이 튜링 기계의 동작으로 표현할 수 있습니다. 따라서 모든 프로그램은 일련의 명령어, 기호, 상태 변화 등을 통해 표현되며, 이 모든 것을 특정한 알파벳이나 숫자로 구성된 문자열로 나타낼 수 있습니다.

이제 이 문자열들은 숫자와 같은 방식으로 순서를 부여받을 수 있습니다. 예를 들어, 사전에서 단어들을 가나다 순으로 정렬하는 것처럼, 모든 프로그램은 유한한 길이의 문자열로 표현될 수 있기 때문에 모든 프로그램을 그 코드에 따라 나열할 수 있습니다. 따라서 모든 컴퓨터 프로그램에 번호를 매긴 목록을 $P(n)$이라 하겠습니다.

이러한 프로그램들은 특정한 입력을 받으면 실행을 시작하고, 특정 조건이 충족되면 멈추거나, 조건이 충족되지 않으면 무한히 실행됩니다.

 

2. 가상의 정지 오라클 $H$
그 후에 '정지 오라클'이라고 불리는 가상의 프로그램 $H$를 상상해보겠습니다. 이 오라클은 어떤 프로그램 $P$와 그 프로그램이 실행할 입력 $n$이 주어졌을 때, 그 프로그램이 멈출지(YES) 아니면 무한히 실행될지(NO)를 결정할 수 있다고 가정해보겠습니다.

[!note] 프로그램 H의 역할

• $H$는 프로그램 $P$가 입력 $n$에 대해 멈추는 경우 'YES'를 출력한다.
• $H$는 프로그램 $P$가 입력 $n$에 대해 멈추지 않는 경우 'NO'를 출력한다.

 

3. 튜링의 역설 프로그램 $R$
이제 오라클 $H$을 사용하여 또 다른 프로그램 $R$을 만들어 보겠습니다. 이 프로그램은 매우 특이한 방식으로 작동합니다

[!note] 프로그램 R의 역할

• $R$은 프로그램의 리스트에서 특정 $n$을 선택한다.
• $H$을 호출하여 $P(n)$이 멈출지 여부를 확인한다.
• 만약 $H$가 'YES'라고 응답하면, $R$은 무한 루프에 빠진다(멈추지 않고 계속 실행됨).
• 만약 $H$가 'NO'라고 응답하면, $R$은 즉시 멈춘다.

 

프로그램 $R$은 정지 오라클 $H$의 반대되는 행동을 하도록 설계되었습니다. 앞서 $H$는 주어진 프로그램 $P(n)$이 멈출지 여부를 알려주는 도구입니다. 하지만 $R$은 이 정보를 반대로 사용합니다.

이제 프로그램 $R$을 자기 자신에게 적용해보겠습니다. 즉, $R$은 자기 자신을 $P(n)$으로 삼아 자기 자신을 호출하게 됩니다. 이 경우 두 가지 가능한 시나리오가 있습니다.

첫 번째로, 만약 $R$이 멈춘다면, 정지 오라클 $H$는 'YES'를 반환했어야 합니다. 하지만 $R$은 'YES'의 응답을 받으면 무한 루프에 빠지도록 설계되었습니다. 따라서, $R$이 멈춘다면 모순이 발생합니다.

두 번째로, 만약 $R$이 멈추지 않는다면, 정지 오라클 $H$는 'NO'를 반환했어야 합니다. 하지만 $R$은 'NO'의 응답을 받으면 즉시 멈추도록 설계되었습니다. 따라서, $R$이 멈추지 않으면 또 다른 모순이 발생합니다.

 

 

이처럼 $R$은 오라클의 예측과 항상 반대되는 행동을 하며, 논리적 모순을 일으키게 됩니다. 결국 이러한 모순을 통해 튜링은 모든 프로그램의 정지 여부를 정확하게 판단할 수 있는 정지 오라클 $H$와 같은 알고리즘이 존재할 수 없음을 증명했습니다.

이러한 정지 문제의 불가능성을 고려할 때, 컴퓨터를 사용하여 수학적 난제를 해결하는 데 있어 분명한 한계가 있다는 점은 아쉬운 일입니다. 만약 정지 문제를 해결할 수 있다면, 컴퓨터 프로그램을 통해 여러 난제들을 자동으로 증명하거나 반증할 수 있을 것입니다.

그러나 정지 문제의 불가능성으로 인해, 우리는 컴퓨터가 모든 경우에 대해 정확한 답을 제공할 수 없다는 사실을 받아들여야 합니다.

하지만 이러한 한계가 그렇게 안타깝지는 않습니다. 왜냐하면 수학적 탐구에 있어 인간의 역할이 여전히 필수적임을 시사하기 때문이죠. 그리고 튜링의 접근 방식을 활용하면 괴델의 불완전성 정리를 직관적으로 이해할 수도 있습니다.

괴델의 불완전성 원리

괴델의 첫 번째 불완전성 정리는 특정 수학적 체계가 충분히 강력하고 일관성이 있는 경우, 쉽게 말해 시스템이 모순 없이 작동한다면, 그 체계 내에서 참이지만 증명할 수 없는 명제가 반드시 존재한다는 것을 의미합니다.

여기서 충분히 강력하다는 것은 페아노 산술(Peano Arithmetic)과 같이 기본적인 산술을 표현할 수 있을 정도로 일관되며, 자기 자신을 표현할 수 있는 능력을 가진 형식 체계(Self-reference) 즉, 재귀적으로 열거 가능한 공리계를 갖는다는 것을 말합니다.

그렇다면 튜링의 정지 문제를 이용해 괴델의 불완전성 정리를 어떻게 이해할 수 있는 것일까요?

 

1. 프로그램과 명제를 대응하는 함수 $f(n)$
일관된(페아노 산술을 포함하고 효과적으로 공리화할 수 있는) 수학적 시스템이 완전하다 즉, 이 시스템 내에서 모든 참인 명제가 형식적으로 증명될 수 있다고 가정하고, 계산 가능한 $f(n)$이라는 함수를 정의해보겠습니다. $f(n)$는 $n$-번째 프로그램 $P(n)$이 멈추는지, 멈추지 않는지를 $1$ 또는 $0$으로 나타냅니다.

• $f(n) = 0$은 $P(n)$이 멈추는 경우를 의미한다.
• $f(n) = 1$은 $P(n)$이 멈추지 않는 경우를 의미한다.

 

2. 자기 참조 알고리즘
이제 계산 가능한 $f(n)$을 이용해 다음과 같은 자기참조 알고리즘을 생각해보겠습니다.

[!note] $f(n)$을 이용한 알고리즘

1. 숫자 $n$을 입력 받는다.
2. $P(n)$이 멈출지, 멈추지 않을지를 판단하기 위해 수학적 시스템 내에서 증명 가능한 모든 명제를 살펴본다.
3. 만약 '$f(n) = 0$'이라는 명제를 찾으면, '$f(n) = 0$'을 출력하고 종료한다.
4. 만약 '$f(n) = 1$'이라는 명제를 찾으면, '$f(n) = 1$'을 출력하고 종료한다.

 

3. 이러한 알고리즘이 있다면?
시스템이 일관되기 때문에, 만약 시스템 내에서 '$f(n) = 0$'이라는 명제를 증명할 수 있다면, 실제로 '$f(n) = 0$'이 성립합니다. 마찬가지로, '$f(n) = 1$'을 증명할 수 있다면, 실제로 '$f(n) = 1$'이 성립합니다.

모든 참인 명제를 증명할 수 있다는 가정 하에, $f(n)$이 $0$ 또는 $1$중 하나로 귀결될 수밖에 없고, 알고리즘은 입력 $n$에 대해 $f(n)$의 값을 반드시 찾아내므로 이 알고리즘은 어떤 입력에 대해서도 유한한 시간 안에 멈추게 됩니다

그런데 이러한 결과는 앞서 본 정지 문제의 불가능성과 모순됩니다. 결과적으로 시스템이 완전하다는 가정이 모순을 일으킨다는 것으로 부터, 괴델의 불완전성 정리를 증명하는 것입니다.

마치며

영화 매트릭스(The Matrix)에서 오라클은 미래를 예언하는 능력을 가진 중요한 인물로 등장합니다. 오라클은 네오와 대화를 나누며 '그 꽃병을 깨는 것에 대해 걱정하지 마세요.'라고 말합니다. 네오는 순간 놀라며 뒤를 돌아보게 되고, 그 과정에서 실수로 꽃병을 쳐서 떨어뜨리게 됩니다. 꽃병은 바닥에 떨어져 깨지고 말죠.

오라클의 예언은 단순한 미래 예측을 넘어, 등장인물들의 행동을 유도하여 예언이 그 자체로 사건을 일으키는 역할을 하는 자기참조적 구조를 보여줍니다. 이는 논리적 체계 내에서 자기참조적 명제가 그 체계의 한계를 드러내는 방식과 매우 유사합니다. 오라클의 예언이 네오의 행동을 유도해 스스로 예언을 실현시키듯이, 괴델의 불완전성 정리는 수학적 체계가 자기참조적 구조를 포함할 때, 그 체계가 해결할 수 없는 문제를 내포할 수밖에 없음을 보여줍니다.

우리는 튜링의 정지 문제를 통해 이를 증명함으로써, 이러한 한계가 단순히 추상적이거나 철학적인 문제가 아니라, 매우 구체적이고 실질적인 계산 문제와도 연결되어 있음을 알 수 있습니다.

우리가 구축하는 시스템과 체계는 과연 완전할 수 있을까요? 오라클의 예언처럼, 우리가 마주하는 문제들 속에 숨겨진 자기참조적 구조가 우리를 어디로 이끌지, 그 끝은 누구도 알 수 없습니다. 여러분은 이 한계 속에서 어떤 선택을 하실 것인가요? 그리고 그 선택은 어떤 결론에 도달하게 될까요?