결정 가능성: 답을 찾는 것과 항상 답하는 것은 다르다
결정 가능성은 어떤 예·아니오 문제에 대해 모든 유효 입력에서 멈추고 올바른 답을 주는 알고리즘이 존재하는지 묻는 성질이다. 실행 시간이 매우 길어도 항상 종료하는 알고리즘이 있으면 결정 가능하다. 빠르게 풀 수 있는지와는 별도의 질문이다.
결정 가능성은 항상 종료하는 정확한 판정 절차의 존재를 묻는다.
결정기와 인식기의 차이
언어 L의 결정기는 입력이 L에 있으면 수락, 없으면 거절하며 모든 경우에 멈춘다. 인식기는 L에 있는 입력에서 반드시 수락하지만, 없는 입력에서는 거절하거나 계속 실행할 수 있다. 참인 사례를 언젠가 확인하는 능력만으로 모든 거짓 사례도 확인할 수 있는 것은 아니다.
DFA가 어떤 문자열을 수락하는지 판단하는 문제는 결정 가능하다. 입력을 끝까지 읽고 수락 상태인지 확인하면 된다. 반면 임의 프로그램이 주어진 입력에서 멈추는지라는 일반 문제는 결정 불가능하다.
Decider for language L:
input in L -> halt with YES
input not in L -> halt with NO
Recognizer for language L:
input in L -> halt with YES
input not in L -> halt with NO, or run forever
인식기가 오래 실행했다고 입력이 거짓이라고 결론 내릴 수는 없다. 참인데 더 많은 시간이 필요한 경우와 영원히 끝나지 않는 경우를 일반적으로 구별할 근거가 없기 때문이다. 타임아웃은 운영 정책이지 그 문제의 결정 절차가 아닐 수 있다.
정지 문제는 인식할 수 있다
프로그램을 실제로 모사하여 멈추면 “정지한다”고 답할 수 있다. 멈추지 않는 프로그램의 모사는 계속 실행된다. 따라서 정지하는 프로그램·입력 쌍의 집합은 인식 가능하지만 일반적인 결정기는 존재하지 않는다.
어떤 언어와 그 여집합에 각각 인식기가 있다면 둘을 번갈아 한 단계씩 실행할 수 있다. 입력은 둘 중 하나에 속하므로 해당 인식기가 결국 수락한다. 그때 어느 쪽이 수락했는지로 예·아니오를 결정할 수 있다. 공평하게 실행 단계를 나눠야 한 인식기의 무한 실행이 다른 인식기를 막지 않는다.
이 구조는 인식 가능성과 결정 가능성의 차이를 보여 준다. 동시에 실행한다는 표현이 실제 병렬 하드웨어를 요구하는 것은 아니다. 한 기계가 두 상태를 번갈아 모사할 수 있다.
결정 불가능하다는 결과는 모든 특정 사례가 어려워 보이거나 해결할 수 없다는 뜻이 아니다. 제한된 언어, 유한 상태 프로그램, 정해진 입력 범위에서는 결정 절차가 존재할 수 있다. 일반 문제의 입력 범위를 어떻게 제한했는지 명시해야 한다.
정적 분석 도구는 종료를 보장하기 위해 보수적으로 알 수 없음이나 과도한 경고를 줄 수 있다. 이런 절충을 이해하려면 결정 불가능성과 자원 부족을 구분해야 한다. 알고리즘이 없다는 이론적 한계, 알고리즘은 있지만 비싼 복잡도, 실제 환경의 시간 제한은 서로 다른 이유다.
이론의 입력은 유한한 설명이어야 한다. 무한한 외부 정보를 정답표로 주는 가정은 일반적인 알고리즘 모델과 다르다.