Decision problem

(in Computer science) “주어진 입력이 소수인가?”, “주어진 입력이 특정 패턴을 만족하는가?” 등 답이 “네” 또는 “아니오” 중 하나인 문제.

결정 가능성

• Decidable, if the set of inputs for which the answer is yes is a recursive set.
• Partially decidable, if the set of inputs for which the answer is yes is recursively enumerable set.
• Undecidable, if not decidable.

See also

• tekkie.wordpress.com/2009/08/29/the-death-of-certainty-and-the-birth-of-computer-science/