결정 불가능 문제 (undecidable problem)
쉽게 풀면
결정 불가능한 문제는 아무리 뛰어난 프로그래머가 아무리 오래 노력해도, 모든 경우에 대해 항상 맞는 답을 내는 프로그램을 만들 수 없다고 수학적으로 증명된 문제다. 정지 문제가 가장 유명한 예이며, 두 프로그램이 같은 일을 하는지 판별하는 문제, 어떤 문법으로 만들 수 있는 모든 문자열의 집합이 다른 문법의 집합과 같은지 판별하는 문제 등도 결정 불가능하다.
왜 중요한가
결정 불가능성은 계산이론과 프로그램 검증 분야에서 "이 문제는 원리적으로 자동화할 수 없다"는 한계를 명확히 그어주기 때문에 중요합니다. 정적 분석 도구나 컴파일러 최적화, 자동 정리 증명 같은 실무 연구에서도 목표로 삼는 문제가 결정 불가능하다는 사실을 먼저 확인한 뒤, 완전한 해결 대신 근사·제한된 범위·휴리스틱으로 접근하는 전략을 택하는 경우가 많습니다. 이런 이유로 새로운 문제를 다루는 논문에서는 그 문제의 결정 가능 여부를 밝히는 것이 연구 방향을 정하는 출발점이 됩니다.
논문에서는 이렇게 쓰입니다
언어 이론이나 프로그램 분석에서 완전 자동화가 원리적으로 불가능한 문제를 지적할 때 쓰인다.
소프트웨어 검증 분야에서, 목표로 삼은 성질을 완벽하게 자동 검증하는 것이 원리적으로 불가능함을 정지 문제로의 환원을 통해 보인 사례입니다.
순수 수학·조합론 문제도 결정 불가능할 수 있으며, 그 자체가 다른 문제의 어려움을 증명하는 도구로 쓰인다는 점을 보여줍니다.
조금 더 깊게 보면
어떤 문제가 결정 불가능함을 보이는 대표적인 방법은 이미 결정 불가능하다고 알려진 문제(흔히 정지 문제)를 그 문제로 환원(reduction)하는 것입니다. 만약 새로운 문제를 풀 수 있는 알고리즘이 존재한다면 그것을 이용해 정지 문제도 풀 수 있게 되므로, 모순에 의해 새로운 문제 역시 결정 불가능하다는 결론에 이르는 방식입니다. 또한 결정 불가능성은 이분법적인 개념이 아니라 정도의 차이가 있어서, 완전히 결정 불가능한 문제와 특정 조건을 추가하면 결정 가능해지는 부분 문제를 구분해서 논의하는 경우가 많습니다.
주의할 점
결정 불가능성은 '모든 입력에 대해 일반적으로' 판별할 수 없다는 뜻이며, 특정 제한된 입력 범위에서는 판별 가능한 경우가 많다.