computation_model / knowledge

3n+1을 계산하는 튜링 머신

paul 2025.07.21 589words (2m)

이진수가 적힌 테이프에서 Collatz를 끝까지 돌려 1이 되면 받아들이는 튜링 머신이다. 버블 정렬을 만들 때보다 상태가 훨씬 많아져서 구조부터 바꿨다.

상태마다 함수를 두지 않는다

앞에서는 상태 하나에 함수 하나를 두고 sigma 안에서 elif 로 갈랐다. 상태가 열세 개가 되니 그 방식으로는 감당이 안 됐다.

전이를 통째로 dict 하나로 옮겼다.

python 
deltas = {
    ('q_checkeven', '0'): ('q_gotostart', '0', 'L'),
    ('q_checkeven', '1'): ('q_odd_1t', '0', 'L'),
    ('q_gotostart', '0'): ('q_gotostart', '0', 'L'),
    ...
}

(상태, 읽은 기호) 를 키로 두고 (다음 상태, 쓸 기호, 방향) 을 값으로 둔다. 전이 함수의 정의를 그대로 옮긴 모양이다.

python 
def sigma(name, read):
    global cur, cnt

    if name == 'q_accept':
        print(f'ACCEPTED: {tape.values()}, CYCLE: {cnt}')
        return

    cnt += 1

    iv = (name, read)
    if iv not in deltas:
        print("REJECTED:", iv)
        return

    next, write, dir = deltas[iv]
    tape[cur] = write
    cur = cur + 1 if dir == 'R' else cur - 1
    if cur not in tape:
        tape[cur] = 'M'

    sigma(next, tape[cur])

시뮬레이터가 짧아졌다. 상태가 몇 개든 이 함수는 그대로다. 상태를 추가하는 건 dict에 줄을 넣는 것이다.

if iv not in deltas: REJECTED 도 좋다. 정의하지 않은 조합을 만나면 조용히 이상하게 도는 대신 거기서 멈추고 무엇이 없었는지 알려준다. 표를 설계하다 빠뜨린 칸을 찾는 데 이게 쓸모 있다.

테이프를 dict로

python 
tape = dict(zip(range(len(n)), n))
cur = len(n) - 1

if cur not in tape:
    tape[cur] = 'M'

리스트가 아니라 dict다. 인덱스가 음수로 가도 되고 오른쪽으로 무한히 늘려도 된다. 없는 칸에 처음 닿으면 그때 'M' 을 넣는다.

튜링 머신의 테이프는 양쪽으로 무한하다는 정의를 그대로 옮긴 것이다. 리스트였으면 미리 넉넉히 잡아두거나 앞쪽에 붙이는 처리를 해야 한다.

시작 위치는 맨 오른쪽이다. 이진 덧셈을 하려면 낮은 자리부터 봐야 한다.

상태 이름이 자리올림을 기억한다

홀수 쪽 상태 이름이 규칙적이다.

text 
q_odd_0f  q_odd_1f  q_odd_0t  q_odd_1t

3n+1 은 n + 2n + 1 이다. 2n 은 n 을 한 칸 민 것이므로, 지금 자리에 더해질 값은 한 칸 오른쪽의 원래 비트다. 그런데 그 비트는 이미 지나오면서 덮어써 버렸다.

그래서 상태에 담는다. 이름의 0 과 1 이 그 값이고, t 와 f 가 자리올림이 있는지 여부다. 네 가지 조합이 네 개의 상태가 된다.

머신에는 저장 공간이 테이프밖에 없으므로 기억할 게 있으면 상태 개수로 갚아야 한다. 기억할 것이 두 비트라 상태가 네 배로 늘어난 것이다.

짝수는 자리를 통째로 민다

짝수를 2로 나누는 건 오른쪽 끝의 0을 떼는 것인데, 테이프에서는 그냥 지울 수 없다. 그래서 왼쪽 끝으로 갔다가 오른쪽으로 오면서 전체를 한 칸씩 민다.

q_moveright_0 와 q_moveright_1 이 그 일을 한다. 지금 읽은 값을 상태에 담고, 앞 상태가 담고 있던 값을 그 자리에 쓴다. 한 칸씩 밀며 오른쪽으로 간다.

q_gotostart 로 왼쪽 끝까지 가는 것도 한 칸씩이다. 이 왕복이 그대로 비용이 된다.

결과

text 
n = '10101'
ACCEPTED: dict_values(['M','M','M','M','1','M','M','M','M']), CYCLE: 92

21을 넣으면 92번의 전이를 거쳐 테이프에 1만 남는다.

text 
'111'   (7)   CYCLE: 210
'1010'  (10)  CYCLE: 68

cnt 로 전이 횟수를 세는 게 유용하다. 단계 수가 아니라 실제 기계가 움직인 횟수라, 왔다 갔다 하는 비용까지 포함된 값이다. 7은 10보다 작은데 세 배 넘게 걸린다.

재귀로 만든 대가

python 
sigma(next, tape[cur])

전이 하나가 함수 호출 하나다. 그래서 전이 횟수만큼 재귀가 깊어진다.

'11011' 인 27을 넣으면 RecursionError 가 난다. 27은 1까지 가는 데 111단계가 걸리고 도중에 9232까지 올라가는 수라, 전이가 파이썬의 기본 재귀 한도인 1000을 훌쩍 넘는다.

while 로 바꾸면 깊이 제한이 사라진다. 전이가 꼬리 호출뿐이라 반복문으로 그대로 옮겨진다. 상태 전이를 재귀로 쓰면 정의에 가까워 보이지만 실행에는 이 한계가 따라온다.