결정 가능성 (decidability)
쉽게 풀면
결정 가능한 문제란 '항상 답을 내는 프로그램을 만들 수 있는 문제'를 말한다. 예를 들어 두 정수가 같은지 확인하는 문제는 결정 가능하다. 반면 정지 문제처럼 어떤 입력에 대해서도 항상 옳게 답하는 알고리즘이 존재하지 않는다고 증명된 문제는 결정 불가능하다고 한다. 이는 계산 이론의 근본적인 한계를 보여준다.
왜 중요한가
결정 가능성은 어떤 문제를 자동화된 알고리즘으로 완전히 풀 수 있는지에 대한 이론적 한계를 규정하기 때문에, 프로그램 검증·컴파일러 설계·형식 언어 이론 연구에서 반드시 짚고 넘어가는 개념입니다. 어떤 문제가 결정 불가능함을 증명하면 그 문제를 완전히 자동화하려는 시도는 원천적으로 불가능하다는 것을 보여주므로, 대신 근사적·제한적 접근을 택하는 연구 방향을 정당화하는 근거로 자주 사용됩니다.
논문에서는 이렇게 쓰입니다
프로그램 분석이나 언어 이론에서 어떤 성질을 자동으로 판별할 수 있는지 논의할 때 사용된다.
형식 논리·자동 정리 증명 분야에서 특정 논리 체계의 판별 가능 여부와 그 계산 복잡도를 논의할 때 쓰인다.
프로그래밍 언어 이론에서 타입 시스템의 이론적 한계를 근거로 설계 선택을 정당화할 때 사용되는 표현이다.
조금 더 깊게 보면
결정 가능성과 밀접한 개념으로 반결정 가능성(semi-decidability)이 있는데, 이는 답이 "예"인 경우에는 언젠가 알고리즘이 종료하지만 "아니오"인 경우에는 종료를 보장하지 못하는 성질을 말합니다. 또한 계산 복잡도 이론에서는 결정 가능한 문제라도 실제로 계산하는 데 걸리는 시간이 지수적으로 커질 수 있어, 결정 가능성과 별개로 계산 가능성의 실용적 난이도를 다루는 복잡도 계층(P, NP 등)이 함께 논의되는 경우가 많습니다.
주의할 점
결정 불가능하다는 것이 '아무 정보도 얻을 수 없다'는 뜻은 아니며, 근사적이거나 제한된 경우에는 판별이 가능할 수 있다.