괴델과 튜링

00. TL;DR

• 괴델과 튜링 모두 인간이 만든 논리 체계나 계산 시스템이 결코 완전하지 않다는 점을 보여줌
• “모든 걸 설명하는 궁극의 이론”은 존재하지 않는다는 철학적 결론으로 이어짐
• 체계를 아무리 정교하게 설계해도, 그 바깥에 항상 새로 등장하는 예외적인 문제가 존재함
• 이는 인간의 사고, 지능, 언어, 계산 능력 전체에 구조적 한계가 있다는 것을 드러냄

---

01. 괴델의 불완전성 정리

01.01. 전제 조건

괴델은 다음 세 가지 조건을 만족하는 체계에서 불완전성이 발생함을 증명했습니다:

1. 일관성(Consistency): 모순이 없는 체계
2. 완전성(Completeness): 참인 명제를 모두 증명할 수 있는 체계
3. 표현력(Richness): 최소한 자연수 산술 정도를 표현할 수 있는 체계

01.02. 증명의 아이디어

▶ “논리 = 숫자”로 바꾸는 발상

괴델은 “모든 논리 명제, 증명, 규칙”을 숫자로 바꾸는 “괴델 수(Gödel Numbering)”라는 기법을 개발합니다.

▶ 자기 자신을 말하는 명제 만들기

• “이 명제는 증명되지 않는다”는 문장을 수학적 형식으로 구성함
• 이 명제가 참이라면, 증명할 수 없으므로 체계는 불완전함
• 거짓이라면, 거짓인 명제를 증명한 것이므로 체계는 모순임

01.03. 제1, 제2 불완전성 정리

• 제1 정리: 참이지만 증명 불가능한 명제가 반드시 존재한다.
• 제2 정리: 체계는 자신의 일관성을 스스로 증명할 수 없다.

01.04. 불완전성의 반복 구조

괴델의 정리는 단순히 ‘하나의 예외’가 있다는 수준을 넘어서, 체계를 보완하여 증명 불가능한 명제를 포함시켜도,
그 보완된 체계 안에서 또 다른 증명 불가능한 명제가 발생한다는 사실을 의미합니다.

즉:

• “예외를 막기 위해 체계를 확장하면,”
• “그 확장된 체계 안에서 새로운 예외가 다시 생긴다.”

이것은 완벽한 수학 체계란 영원히 도달할 수 없는 이상임을 보여줍니다.

---

02. 튜링의 계산 불가능성 정리 (정지 문제)

02.01. 문제 제기: 모든 문제는 계산으로 풀 수 있을까?

힐베르트가 제안한 “결정 가능성 문제(Entscheidungsproblem)”에 대해, 튜링은 계산 모델을 제시하고 그 한계를 증명합니다.

02.02. 튜링 기계 모델

튜링은 수학적 알고리즘을 형식화하기 위해 튜링 기계라는 추상 모델을 만듭니다:

• 무한 테이프
• 읽기/쓰기 헤드
• 상태 집합과 전이 함수

02.03. 정지 문제(Halting Problem)

▶ 질문:

“입력 x와 프로그램 P가 주어졌을 때, P(x)는 언젠가 멈출까?”

▶ 증명의 구조:

1. P(x)가 멈추는지를 판단하는 기계 H가 있다고 가정
2. H를 이용해, “자기 자신을 입력으로 받았을 때 정지 여부에 따라 반대로 행동하는 프로그램”을 만듦 (자기 참조)
3. 논리적 모순 발생 → H는 존재 불가 → 정지 문제는 계산 불가능

02.04. 계산 불가능성의 반복 구조

정지 문제의 본질은 계산 가능한 문제의 경계를 형성할 수 없다는 것입니다.

• 어떤 문제는 정답이 있어도 그 정답을 알고리즘으로 구할 수 없음
• 계산 불가능한 문제가 존재한다면, 그걸 우회하거나 피하려 해도 또 다른 정지 문제가 다시 발생함
• 따라서 계산 가능한 체계는 절대로 완성될 수 없고, 항상 미지의 계산 불능 문제가 남음

이 점에서 튜링은 괴델이 보여준 체계의 불완전성이 계산 영역에서도 동일하게 나타난다는 것을 증명한 셈입니다.

---

03. 괴델 vs 튜링 비교 정리

항목	괴델	튜링
분야	수리논리학	계산이론
핵심 대상	형식 체계(Formal System)	알고리즘 및 계산 모델
방법	자기 참조 명제 (괴델 수)	자기 참조 알고리즘 (정지 문제)
결론	참이지만 증명 불가능한 명제 존재	정답이 있어도 계산 불가능한 문제 존재
반복 구조	체계 보완 시마다 새로운 불완전성 발생	계산 가능성을 확장해도 새로운 계산 불능 문제가 나타남
철학적 의미	진리는 증명과 다르다	계산은 만능이 아니다