0과 1만 있는 테이프를 0이 앞에 오도록 정렬하는 튜링 머신이다. 상태 다섯 개로 된다.
Q = {q_0, q_check, q_swap, q_back, q_accept}
Σ = {'0', '1'}
Γ = {'0', '1', 'B'}
Σ 는 입력에 쓰는 기호고 Γ 는 테이프에 쓸 수 있는 기호다. B 는 빈 칸이라 입력에는 없고 테이프에만 있다.
하는 일
오른쪽으로 가면서 10 을 찾아 01 로 바꾸고, 바꿨으면 맨 앞으로 돌아가 다시 시작한다. 더 바꿀 게 없으면 끝난다. 버블 정렬을 한 번에 한 쌍씩 하는 것이다.
def q_0(para):
if para == '0':
sigma('q_0', '0', 'R')
elif para == '1':
sigma('q_check', '1', 'R')
q_0 은 0을 지나친다. 1을 만나면 q_check 로 넘어간다. 상태 이름이 곧 기억이다. 방금 1을 봤다는 걸 변수에 담는 게 아니라 상태로 옮겨 담는다.
def q_check(para):
if para == '0':
sigma('q_swap', '1', 'L')
elif para == '1':
sigma('q_check', '1', 'R')
elif para == 'B':
sigma('q_accept', 'B', 'R')
1을 본 상태에서 0을 만나면 10 이므로 바꿔야 한다. 그 자리에 1을 쓰고 왼쪽으로 가서 q_swap 이 된다.
1을 또 만나면 계속 오른쪽으로 간다. 빈 칸을 만나면 끝까지 갔는데 10 이 없었다는 뜻이라 받아들인다.
def q_swap(para):
sigma('q_back', '0', 'L')
q_check 에서 이미 오른쪽 자리에 1을 써뒀으니 여기서는 왼쪽 자리에 0을 쓰면 교환이 끝난다. 읽은 값을 보지 않는다. 이 상태에 왔다는 것 자체가 여기가 1이라는 걸 보장한다.
def q_back(para):
if para == 'B':
sigma('q_0', 'B', 'R')
else:
# 0, 1은 그대로 두고 계속 왼쪽으로
맨 앞의 빈 칸까지 되돌아가 다시 q_0 으로 시작한다.
상태를 함수로
def sigma(name, value, dir):
global cur
tape[cur] = value
cur = cur + 1 if dir == 'R' else cur - 1
if name == 'q_0':
q_0(tape[cur])
elif name == 'q_check':
q_check(tape[cur])
...
전이 함수를 sigma 하나로 두고, 상태마다 함수를 하나씩 만들었다. sigma 는 쓰고, 움직이고, 다음 상태 함수를 부른다.
상태가 늘어나면 sigma 안의 elif 가 같이 늘어난다. 상태 다섯 개까지는 읽을 만한데 그 이상이면 관리가 어려워진다.
결과
입력: ['B','0','0','1','1','0','1','0','0','1','1','B','B']
출력: ['B','0','0','0','0','0','1','1','1','1','1','B','B']
0 다섯 개가 앞으로, 1 다섯 개가 뒤로 갔다.
한 번 교환할 때마다 맨 앞으로 되돌아가므로 이동 횟수가 많다. 튜링 머신에서는 테이프를 한 칸씩만 움직일 수 있어서 "맨 앞으로"가 공짜가 아니다. 되돌아가는 비용이 그대로 드러나는 게 이 모델의 특징이다.