알고리즘 (1) 썸네일형 리스트형 알고리즘1 The HALTING Problem The HALTING Problem 프로그램에 입력이 들어오면 종료할 것이냐? 멈추지 않는다면 알려주는 것이 좋지 않을까? 무한루프는 멈추지 않는 프로그램 중 하나 어떤 프로그램이 종료하지 않는지를 미리 알 수 있는가? 언젠가 끝난다는 것을 말할 수 있는 시점이 있을까? 반대로 절대로 안 끝난다는 것을 확신할 수 있는 시점이 있을까? Alan Turing의 증명 -> 결론 : 이 문제는 안 풀린다. -> 이 문제는 풀린다고 가정함. (귀류법으로 증명) 프로그램 D = 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 종료할 지 영원히 계속 수행될지 판단할 수 있다고 하자. - 프로그램 D는 Yes/No를 대답하는 프로그램 - 프로그램 D는 항상 종료함 즉, 프로그램 D의 입력은 어.. 이전 1 다음
