정지문제 (Halting problem) 정지문제는 처음으로 증명된 판정불가능한 문제가 되었다고 한다. 정지문제를 간단하게 요약해보면 아래와 같다. 프로그램과 입력값이 주어졌을 때, 프로그램에 입력값을 넣고 실행한다면 프로그램이 계산을 끝내고 멈출지, 무한으로 계산할지 판정할수 있는가? 1936년에 앨런 튜링은 모든 입력값에 대해 정지문제를 풀 수 있는 일반적인 알고리즘은 존재하지 않는다는 것을 증명했다. 간단한 증명 귀류법을 사용하면 간단한데, 프로그램 a와 문자열 i입력으로 실행이 끝나면 true, 실행이 멈추지 않고 영원히 계산된다면 false가 결과값으로 나오는 halt(a, i)라는 알고리즘이 있다고 해보자. 이러한 완벽한 알고리즘을 가지고 아래의 함수를 구현했다고 한다면, 만약 trouble(..
'→ Computer Science' 카테고리의 글 목록