13.6 결정 가능성의 개념

1. 절의 학술적 목표

본 절은 형식 체계의 결정 가능성(decidability)의 개념을 학술적으로 검토하는 것을 목표로 한다. 결정 가능성은 논리 체계의 증명 가능성 또는 타당성을 판정하는 알고리즘의 존재 여부에 관한 메타이론적 성질이며, 계산 이론과 논리학의 접점에 위치한다. 본 절은 결정 가능성의 형식적 정의, 알고리즘의 개념, 결정 절차, 반결정 가능성, 결정 불가능성, 힐베르트의 결정 문제, 학술적 의의를 체계적으로 정리한다.

2. 결정 가능성의 직관적 개념

결정 가능성의 직관적 개념은 “주어진 명제가 형식 체계의 정리인지 아닌지를 유한한 단계로 판정하는 알고리즘이 존재한다“로 표현된다. 즉, 체계 L과 명제 A가 주어졌을 때, 유한 시간 내에 “⊢_L A“인지 아닌지를 기계적으로 판정할 수 있는 절차가 존재하는 경우 L은 결정 가능하다고 한다. 이러한 개념은 논리 체계의 효율적 사용 가능성과 밀접히 관련되며, 계산 이론과 논리학의 접점에 위치한다. 결정 가능성은 체계의 정리 집합이 산출 가능(effectively computable)하다는 요구로 해석될 수 있다(Kleene, 1952).

3. 결정 가능성의 형식적 정의

결정 가능성의 형식적 정의는 다음과 같다. 논리 체계 L이 결정 가능하다는 것은 “L의 정리 집합 T_L = {A : ⊢_L A}이 결정 가능 집합(decidable set)임“을 의미한다. 즉, 명제 A가 주어졌을 때 “A ∈ T_L“인지 “A ∉ T_L“인지를 유한 단계로 판정하는 알고리즘(또는 튜링 기계)이 존재한다. 이 정의는 결정 가능성의 개념을 계산 이론의 결정 가능 집합의 개념으로 환원하며, 결정 가능성을 수학적으로 정확히 정의할 수 있게 한다(Turing, 1936).

4. 알고리즘과 결정 절차

결정 가능성은 알고리즘의 존재를 요구하며, 알고리즘의 개념은 계산 이론에서 엄밀히 정의된다. 알고리즘은 유한한 규칙의 집합으로서 주어진 입력에 대하여 유한한 단계로 출력을 산출하는 기계적 절차이다. 알고리즘의 형식적 정의는 튜링 기계, 람다 계산, 부분 재귀 함수 등 다양한 모델에 의하여 주어지며, 처치-튜링 테제(Church-Turing thesis)에 의하여 이 모델들이 모두 동등한 계산 능력을 가진다고 주장된다. 결정 절차(decision procedure)는 특정 문제에 대한 알고리즘이며, 결정 가능성의 증명은 결정 절차의 구성에 의하여 이루어진다(Church, 1936; Turing, 1936).

5. 명제 논리의 결정 가능성

명제 논리는 결정 가능하다. 결정 절차의 기본 예시는 진리표 방법이다. 주어진 명제 A가 포함하는 명제 변항의 개수를 n이라 하면, 2^n개의 가능한 진리 할당에 대하여 A의 진리값을 계산할 수 있다. 만약 A가 모든 할당에서 참이면 A는 타당하며, 따라서 증명 가능하다(완전성 정리에 의하여). 만약 A가 어떤 할당에서 거짓이면 A는 타당하지 않으며, 따라서 증명 가능하지 않다(건전성 정리에 의하여). 이러한 진리표 방법은 유한 단계로 명제의 증명 가능성을 판정하며, 명제 논리의 결정 가능성을 증명한다(Post, 1921).

6. 반결정 가능성

반결정 가능성(semi-decidability) 또는 재귀 열거 가능성(recursive enumerability)은 결정 가능성보다 약한 성질이다. 체계 L의 정리 집합 T_L이 반결정 가능하다는 것은 “A ∈ T_L인 경우에는 알고리즘이 유한 단계로 ’예’를 출력하지만, A ∉ T_L인 경우에는 알고리즘이 종료하지 않을 수 있음“을 의미한다. 즉, 반결정 가능 집합은 원소를 유한 단계로 확인할 수 있지만, 비원소를 유한 단계로 확인할 수 없는 집합이다. 모든 결정 가능 집합은 반결정 가능하지만, 역은 성립하지 않는다. 1차 술어 논리는 반결정 가능하지만 결정 가능하지 않다(Turing, 1936).

7. 결정 불가능성

결정 불가능성(undecidability)은 결정 가능성의 실패를 의미한다. 체계 L이 결정 불가능하다는 것은 “L의 정리 집합의 판정 알고리즘이 존재하지 않음“을 의미한다. 결정 불가능성의 가장 유명한 예는 정지 문제(halting problem)이며, 이는 임의의 튜링 기계와 입력에 대하여 그 기계가 정지하는지를 판정하는 알고리즘이 존재하지 않음을 주장한다. 튜링은 1936년 논문 “On Computable Numbers, with an Application to the Entscheidungsproblem“에서 정지 문제의 결정 불가능성을 증명하였으며, 이를 통하여 1차 술어 논리의 결정 불가능성도 증명하였다(Turing, 1936).

8. 힐베르트의 결정 문제

힐베르트의 결정 문제(Entscheidungsproblem)는 1928년 힐베르트와 아커만의 『Grundzüge der theoretischen Logik』에서 제기된 문제이며, “1차 술어 논리의 모든 명제에 대하여 그것이 타당한지 아닌지를 결정하는 알고리즘이 존재하는가“라는 질문이다. 이 문제는 수학 기초론의 핵심 질문 중 하나였으며, 힐베르트는 긍정적 답을 기대하였다. 그러나 처치(Alonzo Church)와 튜링(Alan Turing)은 1936년에 각각 독립적으로 이 문제에 대한 부정적 답을 증명하였다. 즉, 1차 술어 논리는 결정 불가능하며, 힐베르트의 결정 문제는 원칙적으로 해결 불가능하다. 이 결과는 수학 기초론과 계산 이론의 근본적 결과이다(Church, 1936; Turing, 1936).

9. 결정 가능성과 완전성의 관계

결정 가능성과 완전성은 독립적 성질이지만 상호 관련이 있다. 완전하고 결정 가능한 체계는 이상적이며, 명제 논리가 이러한 예이다. 그러나 완전하지만 결정 불가능한 체계가 존재한다(1차 술어 논리). 반대로, 결정 가능하지만 불완전한 체계도 존재할 수 있다. 또한 충분히 강한 체계(페아노 산술을 포함하는 체계)에서는 괴델의 불완전성 정리에 의하여 완전성이 실패하며, 이러한 체계는 결정 불가능하기도 하다. 결정 가능성과 완전성의 독립성은 두 메타이론적 성질이 서로 다른 측면을 다룸을 보여 준다(van Dalen, 2013).

10. 결정 가능성과 계산 복잡도

결정 가능성은 알고리즘의 존재만을 요구하며, 알고리즘의 효율성을 고려하지 않는다. 그러나 실용적 관점에서는 알고리즘의 계산 복잡도(computational complexity)가 중요하다. 명제 논리의 타당성 판정은 결정 가능하지만, 일반적으로 NP-완전 문제에 속하며, 효율적인 알고리즘(다항 시간)이 존재하는지는 P 대 NP 문제와 연결된다. 결정 가능성의 개념은 이론적 분석의 기초를 제공하지만, 실제 응용에서는 계산 복잡도의 고려가 추가된다. 이러한 구분은 결정 가능성의 이론적 의의와 실용적 의의를 명료히 한다(Cook, 1971).

11. 결정 가능성의 학술적 의의

결정 가능성 개념의 학술적 의의는 다음과 같이 정리된다. 첫째, 그것은 논리 체계의 효율적 사용 가능성에 관한 기본 질문을 제기한다. 둘째, 그것은 계산 이론과 논리학의 접점을 제공하며, 두 분야의 통합적 이해를 가능하게 한다. 셋째, 그것은 수학 기초론의 메타이론적 분석의 핵심 개념이다. 넷째, 그것은 자동 정리 증명, 형식 검증, 프로그래밍 언어 이론 등 컴퓨터 과학의 응용에 이론적 기초를 제공한다. 다섯째, 결정 불가능성 결과(튜링의 정지 문제 증명, 처치의 결정 문제 증명)는 형식 체계의 원칙적 한계를 드러낸다. 이러한 의의는 결정 가능성이 메타논리학의 중요한 개념임을 보여 준다(Kleene, 1952).

12. 본 절의 결론적 정리

결정 가능성은 형식 체계의 증명 가능성을 판정하는 알고리즘의 존재 여부에 관한 메타이론적 성질이다. 결정 가능성의 형식적 정의는 체계의 정리 집합이 결정 가능 집합임을 요구하며, 이 정의는 계산 이론의 알고리즘 개념에 기반한다. 명제 논리는 진리표 방법에 의하여 결정 가능하지만, 1차 술어 논리는 처치와 튜링의 1936년 결과에 의하여 결정 불가능하다. 반결정 가능성은 결정 가능성보다 약한 성질이며, 원소의 확인은 가능하지만 비원소의 확인이 불가능한 경우를 다룬다. 힐베르트의 결정 문제는 1차 술어 논리의 결정 가능성에 관한 수학 기초론의 핵심 질문이었으며, 부정적 답이 증명되었다. 결정 가능성은 완전성과 독립적이며, 계산 복잡도의 고려와 구별된다. 학습자는 결정 가능성의 직관적 개념, 형식적 정의, 알고리즘과의 관계, 결정 불가능성의 예, 힐베르트의 결정 문제, 학술적 의의를 정확히 이해해야 한다.

13. 출처

• Post, E. L. (1921). Introduction to a general theory of elementary propositions. American Journal of Mathematics, 43(3), 163–185.
• Church, A. (1936). An unsolvable problem of elementary number theory. American Journal of Mathematics, 58(2), 345–363.
• Turing, A. M. (1936). On computable numbers, with an application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, 42, 230–265.
• Kleene, S. C. (1952). Introduction to Metamathematics. Amsterdam: North-Holland.
• Cook, S. A. (1971). The complexity of theorem-proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 151–158.
• van Dalen, D. (2013). Logic and Structure (5th ed.). Berlin: Springer.

14. 버전

• 문서 버전: 1.0
• 작성 기준일: 2026-04-15