컴퓨터과학이 여는 세계_4. 앨런 튜링과 튜링 기계

4. 앨런 튜링과 튜링 기계

2.1 기계적 계산의 정의: 튜링기계

[ 책 p.31~34 ]

 제2차 세계대전에서 독일 나치의 암호체계, 에니그마를 풀어내 연합군을 승리에 큰 공헌을 이바지한 사람이자, 컴퓨터 공학의 아버지라고 불리는 천재 수학자, 앨런 튜링은 괴델의 증명을 단도직입적으로 다시 증명했다. 그는 "기계적인 방식"이 뭔지를 정의내렸고, 그 방식만으로는 모든 사실을 만들 수 없음을 증명했다. 

 튜링은 다섯 종류의 단순한 기계 부품들을 정의하고 그 부품들로 만든 기계로 돌릴 수 있는 것만을 "기계적인 방식"이라고 정의했다. 그리고 이 방식으로는 절대 돌릴 수 없는 계산 문제를 하나 보여 기계적인 방식으로는 모든 참인 명제를 만들어낼 수 없다는 결론을 이끌어 냈다. 

 그는 우선 자신이 정의한 "기계적인 방식"이 충분히 광범위하다는 것을 설득해야 했다. 그는 그 예로 하나의 특이한 궁극의 기계를 만들고 이 기계를 통해 괴델의 정리를 제증명하는데, 바로 이 기계에 컴퓨터의 원천 설계도가 담겨있었다. 

 튜링이 정의한 기계 부품들은 아주 단순하고 몇 개 되지도 않는다. 무한히 많은 빈칸을 가진 테이프, 테이프에 기록되는 심벌들, 테이프에 기록된 심벌을 읽거나 쓰는 장치, 그 장치의 상태를 나타내는 심벌들, 그리고 기계의 작동규칙표이다. 

 여기에서 빈칸이 무한히 많은 테이프를 제외한 나머지는 유한한 갯수로 존재한다. 

 기계마다 이 부품들이 정해지고 어떤 심벌들을 테이프에 읽고 쓰게 될 것인지, 어떤 심벌들로 상태를 구분할지, 작동규칙표는 무엇인지, 테이프의 시작 모습과 기계의 시작 상태 심벌, 그리고 테이프에서의 시작 위치가 정해진다. 

 모든 준비가 끝나면 기계는 작동규칙표에 따라 작동된다. 테이프 간의 심벌을 읽고 쓰면서 테이프 위를 좌우로 한 칸씩 움직이는 일을 한다. 

현 상태	읽은 심벌	쓸 심벌	다음 칸	다음 상태
C	*	$	>	B

* >: 오른쪽  <: 왼쪽  ||: 제자리

 현재 상태는 C이고 테이프에서 읽은 심벌이 *이면 읽은 곳에 $을 쓰고, 

오른쪽으로 한 칸 테이프를 움직이고 다음 상태는 B가 되라

 작동규칙표의 예를 들어보았다. 작동규칙표는 이처럼 한 행이 하나의 작동 규칙으로 기계가 어떤 상태에서 어떤 심벌을 읽으면 어떤 심벌로 쓰고, 어느 방향으로 움직이고, 어떤 상태로 되는지 표현해주고 있다. 

< 책(강의)의 대표적인 예 >

A: $ 찾기

B: $가 끝인가 확인하기

C: *과 $ 위치 바꾸기

 책(강의)에서 예시로 든 대표적인 튜링 기계이다. 위 기계가 하는 일은 테이프에 있는 $ 심벌을 오른쪽 끝으로 옮기는 것이다. 

 $를 찾을 때까지 오른쪽으로 가다가(A상태), $를 찾으면 $가 끝인지 확인하고(B상태), 끝이 아니라면 $의 자리를 오른쪽에 있는 *와 바꾸고(C상태), 다시 $가 끝인지 확인하고, 자리를 바꾸는 작업을 $가 오른쪽 끝일 때까지 반복하는 것이다. $가 오른쪽 끝이라면 작동규칙표에 해당하는 규칙이 더 이상 없으므로 기계는 작동을 멈추게 된다. 

컴퓨터과학이 여는 세계_저자 이광근