31. ㉠에 들어갈 내용으로 옳은 것은?
튜링기계는 수학적으로 정의된 계산 기계로서 세 부분으로 이루어진다. 첫째, 칸으로 나뉜, 양방향으로 끝이 없는 테이프가 있다. 그 칸 각각에는 특정 기호가 기재될 수 있다. 둘째, 주어진 시점에 칸들 중 한 곳에 위치해 있는 헤드가 있다. 셋째, 헤드가 수행해야 하는 작업을 지시하는 기계표가 있다.
양의 정수 2와 3을 더한다고 해 보자. 테이프와 헤드는 다음과 같은 그림으로 표현할 수 있다.
여기서 －는 해당 칸이 비어 있다는 것을 의미한다. 연속하여 배열된 두 개의 ×는 정수 2를 나타내고, 연속하여 배열된 세 개의 ×는 정수 3을 나타낸다. 해당 칸에 있는 기호를 읽은 헤드는 그것을 다른 기호로 대체하거나, 왼쪽이나 오른쪽으로 한 칸 이동하거나, 정지하는 등의 작업을 수행한다.
현재 위 그림의 헤드는 상태 1이고 다음 기계표에 따라 작업을 수행한다.
| | 입력값 : × | 입력값 : － |
|---|---|---|
| 상태 1 | 변경없음 / 오른쪽 / 2 | 변경없음 / 오른쪽 / 1 |
| 상태 2 | 변경없음 / 오른쪽 / 2 | × / 왼쪽 / 3 |
| 상태 3 | 변경없음 / 왼쪽 / 3 | ㉠ |
| 상태 4 | － / 정지 | |
이 기계표에는 헤드가 특정 상태에서 ×나 －를 읽을 때 수행할 작업 명령이 담겨 있다. 예를 들어, 헤드가 상태1에서 －를 읽을 때, '변경없음 / 오른쪽 / 1'은 '기호를 변경하지 말고, 오른쪽으로 한 칸 이동하고, 상태1을 유지하라'라는 명령이다. 헤드가 상태2에서 －를 읽을 때, '× / 왼쪽 / 3'은 '기호를 ×로 변경하고, 왼쪽으로 한 칸 이동하고, 상태 3으로 전환하라'라는 명령이다. 헤드가 상태 4에서 ×를 읽을 때, '－ / 정지'는 '기호를 －로 변경하고, 정지하라'라는 명령이다. 이러한 기계표에 따라 헤드의 작업이 이루어지면 연속하여 배열된 다섯 개의 ×만 최종적으로 남게 된다. 결국, 이 튜링기계는 2와 3의 합이 5라는 것을 계산한 셈이다.
- 변경없음 / 오른쪽 / 4
- 변경없음 / 왼쪽 / 4
- × / 오른쪽 / 4
- × / 왼쪽 / 4
- － / 왼쪽 / 4