[해키피디아] Turing Machine, Halt Problem

앨런 튜링의 에니그마 암호 해독을 담은 영화 이미테이션 게임의 마지막 장면에 나오는 글입니다.

Turing’s work inspired generations of research into what scientist calls “turing machines”. Today, we call them computers.

튜링머신은 앨런 튜링이 고안한 기계로 특정 알고리즘을 통해 덧셈, 뺄셈, 곱셈은 물론 현대 컴퓨터가 수행할 수 있는 계산은 모두 수행할 수 있습니다. (다만 시간이 오래 걸립니다.)

튜링-완전(Turing-Complete)하다는 것은 어떤 컴퓨터가 튜링머신으로 할 수 있는 계산을 할 수 있다면 그 컴퓨터를 튜링-완전하다고 말합니다.

데이비드 힐베르트(David Hilbert)는 ‘모든 수학적 문제에 대해서 그 문제가 참인지 거짓인지를 확실하게 결정해줄 명확한 방법이 존재하는지 증명하시오’ 와 같은 문제를 내고, 앨런 튜링은 이를 정지 문제(Halting Problem)로 발전시켰습니다.

정지 문제란 ‘주어진 프로그램이 해결하고자 하는 문제를 해결하는지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?’(어떤 입력 데이터를 받았을 때, 유한한 단계 이후에 답이 나올 것인지, 무한루프 등을 돌며 영원히 끝나지 않을 것인지)라는 문제며 이를 튜링머신으로 논리적으로 불가능하다는 것을 증명했습니다.

그럼 튜링머신은 무엇일까?

끝없이 긴 칸에 기호들이 적혀있는 테이프(Tape)와 테이프에 기록된 기호를 읽거나 수정하는 장치(Head), 그리고 튜링머신의 상태를 기록하는 상태 기록기(State register), 기계의 작동 규칙표(Action Table)로 구성되어있습니다.

작동 규칙표의 예를 들면 ‘현재 상태가 ‘A’일 때 테이프에서 ‘1’을 만나면 ‘P’를 쓰고 오른쪽으로 한 칸 이동하고 상태를 ‘B’로 수정’, ‘현재 상태가 ‘C’일 때 테이프에서 ‘1’을 만나면 ‘P’를 쓰고 오른쪽으로 한 칸 이동하고 상태를 ‘HALT’(정지)으로 수정과 같은 규칙이 포함되어 있습니다.

작동 규칙에 따라 테이프 칸의 기호를 읽고 수정하며 좌우로 움직이면서 기계의 상태를 변경하는 것이 전부이며, 이러한 과정으로 결과를 얻을 수 있습니다. 한 기계가 덧셈만 수행할 수 있다면, Universal Computing Machine은 모든 튜링머신이 할 수 있는 계산을 수행할 수 있습니다.

그럼 다시, 정지 문제를 해결하기 위해 귀류법을 이용하여 튜링머신이 정지할지 안 할지를 계산하여 판별하기 위해 이것을 판별할 수 있는 튜링머신이 있다고 가정하겠습니다.

이 정지 문제 판별 알고리즘을 exit(a, i) 함수를 구현할 수 있습니다. 이는 튜링머신 a가 입력 i에 대해 정지하고 결과를 반환하면 true, 아니라면 false를 반환합니다. 즉 a(i)가 무한루프에 빠진다면 exit(a, i)==false입니다.

exit를 모순 시키는 subroutine() 함수를 정의하겠습니다. 이때 exit(s,s)는 자기 자신을 입력으로 넣고 실행할 때 결과를 반환하는지를 검사합니다.

function subroutine(s){
	if exit(s,s) == false
		return true
	else
		infinite loop
}

true의 경우에는 infinite loop에 의해 무한루프를 하므로 참일 수가 없으며, false이면 true를 반환하므로 거짓일 수가 없습니다.

복잡해 보이지만 이는 마치 ‘이 문장은 거짓말이다’ 라는 문장이 참일지, 거짓일지 판단하는 것과 비슷합니다.

모순이 발생하여 결국 정지 문제를 해결할 알고리즘이 존재한다는 것이 모순이기 때문에 그런 알고리즘은 존재하지 않는다는 결론이 나오며 튜링머신은 사실상 ‘계산’이라는 것의 한계를 밝혔습니다.

정지 문제에 대해 가장 쉽게 알려주는 영상과 사람들이 남긴 질문에 대한 답입니다. 이해하는데 어려움이 있다면 보시기를 추천합니다.