컴퓨터과학이 여는 세계_2.2 튜링기계의 예1_이광근

강좌 동영상

 튜링기계로 테이프에 쓰여진 심볼을 복사할 수 있다. 예를 들어 0110을 복사하여 0110110을 만든다고 해보자.

 이 때 밑에 그림과 같이 마커를 이용해 빈 공간에 마커가 가리키는 심볼을 쓰고, 마커와 기계의 위치를 하나씩 오른쪽으로 이동해 같은 내용을 반복하면 된다.

 그런데, 튜링기계에 마커라는 도구는 없지 않았나? 어떻게 마커가 등장한 것이지 라고 생각할 수 있다. 허나 이 마커는 실제 튜링기계에서 다음과 같이 각 심볼뒤에 마커가 위치할 수 있는 빈공간이 하나씩 있다고 생각하자.

 이렇게 한다면, 튜링기계 하나에 모두 표현할 뿐더러 기계가 마크를 옮기는 것까지 고려해 튜링기계를 만들 수 있다.

 따라서, 튜링기계는 위와 같은 방법으로 복사가 가능하다.