decidable

알고리즘을 '풀수'로 표현하여 '풀수 있는'을 제안합니다.

튜링 기계가 유한 시간 안에 정답을 내놓을 수 있느냐는 성질이 "decidability"라고 불리게 된 이유는, 답이 예/아니오인 "decision problem"으로 다른 계산 문제들을 환원시킨 후에 엄밀하게 정의했기 때문이라고 사료됩니다. 개인적으로는 "결정"과 "계산"의 어휘 모두 그 취지가 와닿는다고 생각합니다. "결정"은 상기한 예/아니오의 결정 문제를 중심에, "계산"은 그 결정 문제가 본질적으로 담고 있는 계산 문제를 중심에 둔 선택이라고 볼 수 있을 것 같습니다. 특히 수학의 "decidability"를 핵심 과제로 제시한 힐베르트와, 연산을 구체화하여 이에 답한 튜링의 역사를 고려했을 때, 어느 것이 더 본질적이냐는 해석의 여지가 다분하다고 생각합니다. 그래서 두 단어 모두 포괄할 수 있는 "답하다" 역시 고려해봄직하다고 생각합니다. 또한, "계산가능성"이나 "결정가능성"과 같은 용어는, 실제 계산/결정 과정을 실행하는 매체와 무관하다는 인상을 줍니다. 하지만 "decidability"는 튜링 기계가 아닌 다른 컴퓨터 모델 (유한상태 오토마타 따위), 혹은 심지어 논리 체계와 같은 기저 환경에 대해 상대적으로 정의되는 개념입니다. 따라서 이를 용어 번역에 명시하는 것이 좋다고 생각합니다. 본 제안에는 전산학에서 가장 많이 쓰이는 튜링 기계의 연산 능력이라는 의미로 "컴퓨터"를 기저로 삼았습니다. 예를 들어 명제 논리 체계에 대해서는 "명제 논리로 답할/결정할/증명할 수 있는"과 같은 방식으로 치환하여 번역하는 것이 가장 명확할 것 같습니다.

계산 가능한을 제안합니다.