한양과기고 에듀테크 수업도구 대시보드

튜링 머신 — 종이 테이프 한 줄로 만든 "컴퓨터"

1936년, 앨런 튜링은 "계산이란 무엇인가"를 설명하려고 아주 단순한 상상 속 기계를 제안했다. 무한히 긴 테이프, 그 위 한 칸을 읽고 쓰는 헤드, 그리고 현재 상태 하나. 규칙표에 따라 "칸을 읽고 → 다른 글자를 쓰고 → 좌/우로 한 칸 움직이고 → 다음 상태로" 를 반복할 뿐인데, 오늘날 어떤 프로그램이든 이 기계로 표현할 수 있다(튜링 완전). 직접 돌려 보자.

1 튜링 머신 실행기

프로그램을 고르고 ▶ 재생 또는 한 단계를 눌러 보자. 보라색으로 강조된 칸이 헤드 위치, 아래 표에서 강조된 행이 지금 적용되는 규칙이다.

프로그램

입력 테이프

현재 상태

단계 수

헤드 위치

테이프의 1 개수

속도

프로그램을 고르고 재생을 눌러 보세요.

2 상태 전이표 (규칙)

튜링 머신의 프로그램은 이 표가 전부다. "상태 q에서 글자 a를 읽으면 → 글자 b를 쓰고, 헤드를 L/R로 옮기고, 상태 q'로 바꾼다." _ 는 빈 칸(blank)을 뜻한다.

3 7개짜리 부품 목록 (형식적 정의)

수학적으로 튜링 머신은 7-튜플 M = (Q, Σ, Γ, δ, q₀, q_blank, F) 로 정의된다. 말은 딱딱하지만 하나하나는 위 시뮬레이터의 부품과 정확히 대응한다.

상태 집합 — 위 표의 "현재 상태" 칸에 나오는 이름들 (S, A, B …).
입력 알파벳 — 처음 테이프에 올릴 수 있는 글자들 (여기선 0, 1).
테이프 알파벳 — 테이프에 등장 가능한 모든 글자 (0, 1, 빈 칸 _). Σ를 포함한다.
전이 함수 — (상태, 읽은 글자) → (쓸 글자, 이동 방향, 다음 상태). 바로 위의 전이표.
시작 상태 — 실행을 시작할 때의 상태.
빈 칸 기호 — 아직 아무것도 안 쓴 칸에 들어 있는 값. 테이프에 무한히 많다.
정지(수락) 상태 집합 — 이 상태에 도달하면 기계가 멈춘다 (HALT).

4 이 장난감이 왜 중요할까

· 튜링 완전성 — 파이썬, C, 자바스크립트로 짤 수 있는 모든 프로그램은 원리적으로 튜링 머신으로도 짤 수 있다. 반대도 성립한다. 그래서 "이 언어는 튜링 완전하다"는 말은 "계산 능력이 부족하지 않다"는 뜻이다. (엑셀 수식, 마인크래프트 레드스톤, 심지어 매직 카드 게임도 튜링 완전하다.)

· 처치–튜링 명제 — "직관적으로 계산 가능한 것 = 튜링 머신으로 계산 가능한 것". 지금까지 이걸 반증하는 계산 모델은 나오지 않았다.

· 정지 문제(Halting Problem) — "임의의 프로그램과 입력을 받아, 그게 언젠가 멈추는지 먼저 알려 주는 프로그램"은 절대 만들 수 없다. 튜링이 1936년에 증명했다. 아래 비지 비버가 그 예감을 준다.

# 이런 판별기 halts(prog, x) 가 있다고 가정하면 모순이 생긴다
def trouble():
    if halts(trouble, None):
        while True: pass   # 멈춘다고 하면 → 안 멈춤
    else:
        return            # 안 멈춘다고 하면 → 멈춤

· 비지 비버(Busy Beaver) — "n개의 상태로 결국 멈추면서 1을 가장 많이 찍는" 튜링 머신을 찾는 문제. 3-상태 챔피언은 13단계 만에 멈추고 1을 6개 찍는다. 그런데 상태가 조금만 늘어도(BB(5), BB(6) …) 이 수는 우주의 원자 수를 아득히 넘어가고, BB 함수는 어떤 계산 가능한 함수보다도 빨리 커진다. 정지 여부를 미리 알 수 없다는 걸 눈으로 보여 주는 예다.