정지 문제(停止 問題, halting problem)는 판정 문제의 한 갈래로, "주어진 프로그램이 해결하고자 하는 문제가 해결 가능한지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다.
출처 : 나무위키 https://namu.wiki/w/%EC%A0%95%EC%A7%80%20%EB%AC%B8%EC%A0%9C
컴퓨터 과학에서 정지 문제, Halting Problem, Halting therem 이라고 불리는 이것
C언어 책 보다가 무슨 말인가 해서 찾아보다가 알게 되었다.
쉽게 말하면 이렇다.
어떤 프로그램의 설계도 (코드... 라고 봐도 될까?)와 문제(입력값)이 주어졌을 때, 이 프로그램이 문제를 해결할 수 있을지 없을지 판단할 수 있는 만능기계가 존재할까?
더 쉽게말하면
이 코드가 잘 동작하겠니? 라고 코드만 보고 말해줄 수 있는 기계나 프로그램이 있을 수 있나 이다.
나의 백마디 설명보다 이 영상하나면 해결된다.
결론은 불가능하다 이다.
댓글