정지 문제

정지 문제는 논리와 수학의 계산 가능성 이론에서 중요한 문제입니다. 1936년 영국의 수학자 앨런 튜링이 제안한 것으로, 관련 논문은 튜링의 유명한 논문 "계산 가능한 숫자에 관하여, 결정 문제에 대한 응용정지 문제와 튜링 머신 개념이 처음으로 제안된 논문입니다. 런던 수학 협회 회보(Proceedings of the London Mathematical Society)에 게재된 이 논문은 현대 컴퓨터 과학의 토대를 마련했습니다. 튜링의 원래 논문은 정지 문제로 알려지게 된 문제를 직접적으로 다루지는 않았지만, 그의 연구는 계산의 경계를 이해하는 데 기반을 마련했습니다. 정지 문제의 해결 불가능성은 일부 문제가 알고리즘으로는 본질적으로 해결될 수 없음을 시사하는 계산 이론의 핵심 개념입니다.

정지 문제는 어떤 프로그램이 제한된 시간 내에 실행을 마칠 수 있는지 여부를 판별하는 문제를 논의합니다. 즉, 프로그램과 입력이 주어졌을 때, 프로그램이 항상 실행되는 것이 아니라 실행 중에 결국 멈출지 여부를 판단하는 것이 가능할까요? 튜링은 대각선 논증을 통해 정지 문제가 해결 불가능하다는 것을 증명했습니다. 즉, 모든 프로그램과 입력에 대해 프로그램이 실행을 멈출지 아니면 무한 루프에 빠질지 판단할 수 있는 보편적인 알고리즘은 없다는 것입니다. 이 문제의 증명은 컴퓨터 과학 이론의 초석 중 하나이며, 컴퓨팅의 한계를 보여줍니다.