Halting Problem (정지 문제)

오늘을 Halting Problem 이라는 유명한 판정 문제를 소개해 보겠습니다. Alan Turing의 증명과 내 나름의 이해한 것을 바탕으로 풀이를 써보았습니다. The Halting Problem - 프로그램 M 과 입력 X 가 있을 때 M에 입력 X를 주고 수행시키면 M은 종료할 것인가? 이 프로그램 M이 계산을 끝나고 멈출지, 아니면 영원히 멈추지 않을지 판정하라. Halting Problem 이라는 유명한 문제인데 이 문제를 처음 봤을 때는 이게 뭐지...? 싶었다. 프로그램 M이 멈추냐, 안 멈추냐 뭐 이런 뜻 같은데.... 상황에 따라 멈출 수도 있고 안 멈출수도 있지 않나? 라고 생각했다. "상황에 따라서" 말이다. 당연한 얘기일 것이다. 프로그램을 어떻게 짜느냐에 따라 멈출 수도 있..

2022.09.02