결정가능성

논리학에서 결정가능성(decidability)은 참/거짓을 묻는 결정 문제가 가질 수 있는 성질의 하나로, 해답을 내어놓는 기계적인 절차가 존재하는 성질을 가리킨다. 대표적으로 정지 문제의 결정불가능성이 알론조 처치와 앨런 튜링에 의해 증명된 바 있다.

이론(theory)은 논리적 귀결 관계에 대하여 닫힌 문장들의 집합으로 정의되며, 이는 정해진 공리에 대해 추론규칙을 적용하여 나올 수 있는 모든 문장의 집합이라는 정의와 동치이다.

어떠한 이론이 결정가능하다 함은, 그 이론의 언어로 주어진 임의의 문장에 대해 그 문장이 이론에 속하는지의 여부를 기계적으로 결정할 수 있다는 의미이다. 이론에 대해 구문론적 완전성과 재귀적 열거가능성이 성립하면 결정가능성도 성립한다. 한편 결정가능한 이론의 확장은 결정불가능할 수도 있다.

결정가능한 1차논리 이론의 대표적 예시로 실폐체의 이론이나 프레스버거 산술(Presburger arithmetic) 따위가 있으며, 결정 불가능한 이론의 예시로 산술의 기초적인 명제들을 증명할 수 있는 로빈슨 산술(Robinson arithmetic)이나 군의 이론 따위가 있다.

• 결정 문제
• 정지 문제
• 1차 논리
• 계산가능성 이론