봉황대 in CS

* 본 글은 2023학년도 2학기에 수강한 '알고리즘' 과목 강의 내용을 함께 정리하여 작성하였습니다. The Halting Problem 프로그램 M과 입력 X가 있을 때, M에 입력 X를 주고 수행을 시킨다면(M(X)) 이 프로그램은 종료하는가? 'Halting Problem을 푼다'는 것은 M과 X의 모든 경우에, 어떠한 프로그램이 반드시 종료하는지, 아니면 영원히 수행될지(e.g., 무한 루프)를 해당 프로그램을 돌려보기 전에 판별할 수 있다고 하는 것과 같다. → Halting Problem은 풀 수 없다. The Proof by. Alan Turing 가정: 프로그램 D는 존재한다 모든 프로그램 M과 M에 대한 모든 입력 X에 대해서 M(X)를 실행하면 이것이 종료할지, 아니면 영원히 수행될..