컴퓨터과학이 여는 세계_3.1 튜링기계 만들기_이광근

강좌 동영상

 튜링기계를 만드는 것은 소프트웨어를 만드는 것이다. 물론 아주 Low-Level 언어이기 때문에 쓰는 사람은 거의 없겠지만 말이다.

 사람들은 주로 High-Level 언어를 사용해 튜링기계를 만들게 된다. 저번에 예를 들었던 튜링기계를 살펴보자.

 이 기계는 '튜링 머신'이라는 포스팅에서 설명했듯 '$'심볼을 맨 오른쪽에 옮기는 일을 한다. 그렇다면 이때 기계의 상태는 무엇을 나타낼까? 우선 저 표를 순서도로 나타내보자.

(조금 더 복잡해진것 같지만 기분 탓이니 상관하지 말자...)

 이 그림을 보면 A상태는 '$'심볼을 찾은 뒤에는 다시 돌아오지 않는다. 또 찾은후에 B와 C상태를 왔다갔다 한다. 따라서 이 기계의 상태는 다음과 같이 해석할 수 있다.

A: '$' 찾기    (찾으면 B로! 아니면 계속 찾기)

B: '$' 오른쪽에 '*' 있는지 확인    ('*'이 있으면 C로! 아니면 종료)

C: '$' 와 B에서 확인한 '*' 바꾸기    (바꾼후엔 다시 B로)

 그렇다면 튜링은 위에 해석처럼 알아보기 쉬운 High-Level 언어가 아니라 Low-Level 언어를 썼는데, 이는 수학자들이 주로 사용하는 불필요한 부분을 제거해 가장 간단히 시작하는 습관이라고 한다. 튜링의 증명은 계속 이어진다.