틈틈히 개발 연구 정리 틈틈히 개발 연구 정리

계산 가능한 문제는 크게 Decidable한지 Undecidable한지로 나뉠 수 있다. 일반적으로 개발하면서 마주치고 해결하는 문제들은 decidable한 문제로, P 클래스와 NP 클래스의 문제들이 이 영역에 속한다. 그래서 대부분 알고리즘 구현을 한다던지 어떤 문제를 마주했을 때 해결하고자 하는 문제들은 다 decidable한 문제이고, 그렇기 때문에 Soundness나 Completeness에 대해 크게 고민해보지 않았을 것이다. 이번에는 Undecidable한 문제들에 대해서 다뤄볼 예정이다. Undecidable한 문제의 정의부터 해야하는데, 정의는 문제에 대한 정답이 맞는지 틀리는지 항상 도출해내는 알고리즘을 설계하는게 불가능한 문제를 의미한다. 말로 설명해서는 이해가 힘들 수 있지만, 대표..