판정 불가능성과 정지 문제
정지 문제(halting problem)는 주어진 프로그램이 특정 입력에 대해 결국 멈추는지 여부를 묻는 것으로, 모든 경우에 대해 답할 수 있는 알고리즘이 없다는 튜링의 증명은 판정 불가능한 문제의 기초적인 예시입니다.
Definition
결정 문제(decision problem)는 모든 입력에 대해 올바르게 답할 수 있는 알고리즘이 없을 때 판정 불가능하다고 합니다. 임의의 프로그램이 임의의 입력에 대해 정지하는지 여부를 결정하는 정지 문제는 자기 참조적인 대각선 논증에 의해 판정 불가능함이 증명된 대표적인 판정 불가능 문제입니다.
Scope
이 주제는 정지 문제의 판정 불가능성을 확립하는 대각선 논증, 판정 가능(decidable), 인식 가능(recognizable), 그리고 공동 인식 가능(co-recognizable) 문제 간의 구별, 프로그램의 모든 비자명한 의미론적 속성이 판정 불가능함을 보여주는 라이스 정리(Rice's theorem), 그리고 논리, 수학, 컴퓨터 과학 전반에 걸친 자연적인 판정 불가능 문제들의 목록을 다룹니다.
Core questions
- 왜 어떤 단일 알고리즘도 모든 프로그램이 정지하는지 여부를 결정할 수 없는가?
- 문제가 판정 가능한 것과 단순히 인식 가능한 것의 차이는 무엇인가?
- 왜 프로그램 행동의 본질적으로 모든 흥미로운 속성들이 판정 불가능한가?
- 판정 불가능성은 정지 문제에서 다른 문제들로 어떻게 확산되는가?
Key theories
- 정지 문제의 판정 불가능성
- 정지를 결정하는 알고리즘이 있다고 가정하면, 정지하지 않을 것이라고 예측될 때 정확히 정지하는 프로그램을 통해 모순에 이르게 되므로, 그러한 알고리즘은 존재할 수 없습니다.
- 라이스 정리
- 프로그램이 계산하는 함수의 모든 비자명한 속성, 즉 행동에 기반하여 일부 프로그램에는 적용되고 다른 프로그램에는 적용되지 않는 모든 것은 판정 불가능하며, 이는 정지 결과를 모든 의미론적 속성으로 일반화합니다.
Clinical relevance
정지 문제와 라이스 정리에 의해 프로그램의 모든 비자명한 행동적 속성이 판정 불가능하기 때문에, 어떤 도구도 무한 루프를 완벽하게 감지하거나, 임의의 정확성을 검증하거나, 모든 프로그램을 완전히 분석할 수는 없습니다. 따라서 정적 분석기(static analyzers)와 검증기(verifiers)는 근사치를 사용하거나, 오탐(false alarms)을 수용하거나, 범위를 제한해야 합니다.
History
튜링은 칸토어(Cantor)와 괴델(Gödel)에게서 영감을 받은 대각선 논증을 사용하여 1936년에 정지 문제와 논리 결정 문제의 판정 불가능성을 확립했습니다. 라이스는 1953년에 그의 광범위한 일반화를 증명했으며, 이후 수십 년 동안 디오판토스 방정식(Diophantine equations)에 대한 힐베르트의 열 번째 문제(Hilbert's tenth problem)를 포함한 많은 자연스러운 문제들이 판정 불가능함이 밝혀졌습니다.
Key figures
- Alan Turing
- Henry Gordon Rice
- Emil Post
- Alonzo Church
Related topics
Seminal works
- turing1937
- sipser2013
Frequently asked questions
- 프로그램이 정지하는지 확인하기 위해 그냥 실행해 볼 수는 없나요?
- 실행하는 것은 실제로 정지할 경우에만 정지했음을 알려줍니다. 만약 영원히 실행될 예정이라면, 어떤 유한한 기다림도 그것을 밝혀내지 못합니다. 정지 문제는 모든 프로그램과 입력에 대해 유한한 시간 내에 항상 올바른 답을 주는 방법을 요구하며, 튜링은 그러한 방법이 존재하지 않음을 증명했습니다.
- 판정 불가능성이 프로그램 분석을 절망적으로 만드나요?
- 아닙니다. 하지만 완벽한 분석이 불가능한 이유를 설명해 줍니다. 도구들은 보수적으로 접근하여 안전하다고 증명할 수 없는 모든 것을 표시하거나, 제한된 클래스의 프로그램을 정확하게 처리하거나, 적대적이거나 병리적인 경우에는 실패할 수 있음을 인정하면서도 많은 실제 사례를 해결함으로써 대처합니다.