튜링 기계

소프트웨어 계산물리 마지막 수정: 2026-08-04 04:31:12

1. 개요[편집]

튜링 기계 Turing Machine
제안	앨런 튜링 (1936)
구성	무한 테이프 + 유한 상태 제어부 + 헤드
핵심 결과	정지 문제는 결정 불가능
보편성	모든 기계를 흉내 내는 단일 기계가 존재
등가 모형	λ 대수, μ-재귀함수, 레지스터 기계
튜링 완전 예	rule 110, 생명 게임, 랭턴의 개미

“이 계산 언제 끝나요?”는 예의상 묻는 질문이 아니라, 일반적으로는 원리적으로 답이 없는 질문이다.

튜링 기계(Turing machine)는 무한히 긴 테이프, 그 위에서 한 칸씩 움직이며 기호를 읽고 쓰는 헤드, 유한 개의 상태를 가진 제어부만으로 정의되는 계산의 수학적 모형이며, “알고리즘으로 계산할 수 있다”는 말의 표준 정의다. 성능 모형이 아니라 가능/불가능의 경계를 긋는 도구라는 점이 중요하다. 이 기계로 못 하는 일은 어떤 슈퍼컴퓨터로도 못 한다.

튜링이 1936년에 이걸 만든 목적은 컴퓨터를 설계하려는 게 아니라 힐베르트의 결정문제(Entscheidungsproblem)에 답하기 위해서였다. “1차 논리의 임의의 명제가 증명 가능한지 판정하는 기계적 절차가 있는가”에 답하려면 먼저 “기계적 절차”를 정의해야 했고, 그 정의로 만든 부산물이 본편이 됐다.¹ 답은 “없다”였고, 그 증명의 핵심 장치가 아래의 정지 문제다.

2. 종이와 연필을 형식화하면[편집]

튜링의 논증은 사람이 종이에 계산하는 과정을 관찰하는 데서 출발한다. 사람이 한 번에 볼 수 있는 기호 수는 유한하고, 머릿속 상태도 유한하며, 한 번에 하는 일은 “지금 보는 칸을 읽고, 쓰고, 옆 칸으로 이동한다”뿐이다. 이걸 그대로 형식화하면 7-튜플이 된다.

M = (Q,\ \Gamma,\ b,\ \Sigma,\ \delta,\ q_0,\ F), \qquad \delta : Q \times \Gamma \rightarrow Q \times \Gamma \times \{L, R\}

$Q$ 는 유한한 상태 집합, $\Gamma$ 는 테이프 기호, $b$ 는 공백, $\delta$ 가 전이함수다. 무한한 것은 테이프 하나뿐이고 나머지는 전부 유한하다는 점이 이 모형의 전부다.

여기서 계산 가능성의 정의가 나온다. 함수 $f$ 를 계산하는 튜링 기계가 존재하면 $f$ 는 계산 가능하다. 집합 $A$ 의 특성함수가 계산 가능하면 $A$ 는 결정 가능(decidable), 원소인 경우에만 “예”를 내고 아닌 경우엔 영원히 돌아도 되면 반결정 가능(semi-decidable, 재귀적 열거 가능)이다. 이 구분이 실무에서 계속 튀어나온다 — 대부분의 흥미로운 성질은 결정 가능이 아니라 반결정 가능이고, 그래서 “돌려보면 맞다는 건 알 수 있지만, 틀렸다는 건 영원히 확인 못 한다”.

계산 불가능한 함수가 존재한다는 것 자체는 세는 것만으로 끝난다. 튜링 기계는 유한한 문자열로 적을 수 있으니 가산 무한개뿐인데, $\mathbb{N} \to \{0,1\}$ 함수는 비가산 무한개다. 따라서 거의 모든 함수는 계산 불가능하다. 다만 이 논증은 구체적인 예를 하나도 주지 않는다. 구체적인 예를 준 게 다음이다.

3. 보편 기계와 정지 문제[편집]

튜링은 기계 $M$ 과 입력 $w$ 를 문자열 $\langle M, w \rangle$ 로 인코딩한 뒤, 그걸 테이프에서 읽어 $M$ 의 동작을 그대로 재현하는 단일 기계 $U$ 를 만들었다. 이것이 보편 튜링 기계(UTM)다. “프로그램도 데이터다”라는 문장을 수학적으로 못 박은 결과이자, 저장 프로그램 컴퓨터라는 발상의 이론적 원형이다. 오늘 쓰는 인터프리터·에뮬레이터·가상머신이 전부 이 정리의 응용이다.

보편 기계가 있으면 자기 자신을 입력으로 넣는 장난이 가능해진다. 정지 문제를 판정하는 기계 $H(\langle M \rangle, w)$ 가 있다고 가정하고, 이런 기계 $D$ 를 만든다.

D(\langle M \rangle) = \begin{cases} \text{무한 루프} & H(\langle M \rangle, \langle M \rangle) = \text{"정지"} \\ \text{정지} & \text{그 외} \end{cases}

$D$ 에 $\langle D \rangle$ 를 넣으면, $D$ 가 정지하는 경우에만 정지하지 않고 그 역도 성립한다. 모순이므로 $H$ 는 존재하지 않는다. 정지 문제는 결정 불가능이다.

여기서 끝이 아니다. 라이스의 정리(1951)는 이걸 무자비하게 일반화한다. 프로그램이 계산하는 함수에 대한 자명하지 않은 성질은 무엇이든 결정 불가능이다. “이 코드가 언젠가 NaN을 내는가”, “이 반복이 수렴하는가”, “이 두 솔버가 항상 같은 답을 내는가” — 전부 여기 걸린다. 임의의 프로그램을 받아 이런 질문에 항상 옳게 답하는 도구는 만들 수 없고, 만들었다고 주장하는 도구는 반드시 어딘가에서 “모르겠다”를 반환하거나 틀린 답을 낸다. 정적 분석기가 짜증날 정도로 보수적인 이유가 이것이고, 반복 솔버에 최대 반복수 상한이 붙어 있는 이유도 이것이다 — 수렴을 판정할 수 없으니 포기 조건을 사람이 손으로 넣는 수밖에 없다.²

4. 처치-튜링 논제[편집]

같은 1936년, 알론조 처치는 람다 대수로, 괴델과 에르브랑은 μ-재귀함수로, 포스트는 또 다른 형식으로 “계산 가능”을 정의했다. 놀랍게도 넷이 정확히 같은 함수 부류를 정의했고, 이후 등장한 레지스터 기계·태그 시스템·현대 프로그래밍 언어도 전부 같은 부류였다. 이 수렴 현상에 근거해 세운 명제가 처치-튜링 논제다.

직관적으로 “효과적으로 계산 가능”한 함수는 정확히 튜링 기계로 계산 가능한 함수다.

이건 정리가 아니라 논제다. 좌변이 형식적 정의가 없는 직관적 개념이라 증명 대상이 아니기 때문이다. 반증은 가능하다 — 누가 직관적으로 명백히 계산인데 튜링 기계로 못 하는 절차를 들고 오면 된다. 80년 넘게 아무도 못 했다.

혼동하기 쉬운 게 물리적 처치-튜링 논제다. “물리적으로 실현 가능한 임의의 장치로 계산할 수 있는 것은 튜링 기계로도 계산할 수 있다”는 별개의, 경험적인 주장이다. 양자역학 기반 컴퓨터는 이걸 깨지 않는다 — 양자 컴퓨터가 바꾸는 것은 복잡도이지 계산 가능성이 아니고, BQP는 여전히 계산 가능한 문제 안에 있다. 반대로 정지 문제를 푸는 “초계산” 장치 제안들은 거의 예외 없이 무한 정밀도의 실수, 무한한 에너지, 또는 유한 시간 안의 무한 스텝 같은 물리적으로 수상한 자원을 요구한다.

5. 규칙 두 줄로도 충분하다[편집]

튜링 완전성은 어떤 계가 임의의 튜링 기계를 흉내 낼 수 있다는 뜻이다. 요구 조건이 놀랄 만큼 낮다.

rule 110. 이웃 3칸을 보고 갱신하는 1차원 셀룰러 오토마타 규칙 하나가 튜링 완전이다. 매튜 쿡이 1990년대에 증명하고 2004년에 발표했다. 주기적 배경 패턴(ether) 위에서 움직이는 국소 구조들을 신호로 삼아 순환 태그 시스템을 구현하는 방식이며, 니어리와 우즈가 2006년에 시뮬레이션 오버헤드를 지수에서 다항으로 낮춰 rule 110의 예측 문제가 P-난해임을 확정했다.
생명 게임. 글라이더 총과 글라이더 충돌로 논리 게이트를 짜면 된다. 실제로 생명 게임 안에 생명 게임을 구현한 패턴도 있다.
랭턴의 개미. 규칙이 두 줄인데 불 회로를 구성할 수 있고, 무한하지만 규칙적인 초기 배치를 허용하면 튜링 완전이다.

여기서 가장 작은 보편 기계를 찾는 경쟁도 있었는데, 상태 2개·기호 3개짜리 기계가 보편이라는 2007년 결과는 초기 테이프로 비주기적 무한 배경을 요구한다는 점 때문에 “보편성의 정의를 늘린 것 아니냐”는 논쟁을 낳았다.³

시뮬레이션 쪽에서 중요한 건 튜링 완전성이 능력의 선언인 동시에 저주라는 점이다. 어떤 계가 튜링 완전이면, 그 계의 장기 거동을 판정하는 문제는 정지 문제로 환원되므로 결정 불가능이다. 즉 “실제로 돌려보는 것보다 본질적으로 빠른 지름길”이 존재하지 않는다. 울프람이 계산 비환원성(computational irreducibility)이라 부른 것이 이 상황이고, 이것이 창발적 거동을 해석적으로 요약하려는 시도가 자주 실패하는 이유의 형식적 판본이다.

6. 시뮬레이션에 실제로 걸리는 제약[편집]

계산 불가능성은 철학 세미나용 소품이 아니라 수치해석에 진짜 걸린다.

범용 종료·정확도 보장은 없다. 라이스의 정리 때문에 “임의의 사용자 코드가 주어졌을 때 유한 시간에 끝나는가”, “오차가 tol 이하로 떨어지는가”를 판정하는 도구는 원리적으로 불가능하다. 그래서 실무는 전부 충분조건으로 돌아간다 — CFL 조건, 대각우세, 수축 사상 조건처럼 “이 조건을 만족하면 수렴한다”는 보수적 판정만 쓰고, 나머지는 최대 반복수와 발산 감시로 때운다. 검증 및 확인에서 코드 검증이 “정확한 답”이 아니라 “관측 수렴 차수”를 보는 것도 같은 맥락이다.
물리계 자체가 결정 불가능일 수 있다. 2015년 큐빗·페레스-가르시아·볼프는 국소 상호작용을 갖는 2차원 격자 해밀토니안 족을 구성해, 그 계의 스펙트럼 갭이 존재하는지 여부가 결정 불가능임을 보였다. 유한 크기 계에서 갭을 재고 열역학적 극한으로 외삽하는 표준 절차가 원리적으로 실패할 수 있다는 뜻이다 — 갭이 유한 크기에서는 계속 열려 있다가 어떤 거대한 크기에서 닫히도록 만들 수 있고, 그 크기를 미리 알 방법이 없다.
유체도 예외가 아니다. 2021년 카르도나·미란다·페랄타-살라스·프레사스는 3차원 구면 위의 정상 오일러 방정식 (비점성 유동) 해 중에 튜링 완전한 것이 있음을 구성적으로 보였다. 어떤 유선이 특정 영역에 도달하는지 판정하는 문제가 결정 불가능이 되는 흐름이 존재한다는 이야기다.

다만 여기서 허무주의로 넘어가면 안 된다. 결정 불가능성은 **“모든 인스턴스를 처리하는 단일 알고리즘이 없다”**는 진술이지, “우리가 지금 푸는 이 문제를 못 푼다”가 아니다. 실무에서 다루는 방정식은 대개 구조가 좋아서 잘 풀리고, 문제가 되는 것은 계산 불가능성이 아니라 비용이다. 반대로 “돌려봤더니 잘 되더라”를 일반 보장으로 승격하면 안 된다는 경고로는 정확히 유효하다.

7. 실수를 계산한다는 것 — BSS 모형과 부동소수점[편집]

튜링 기계는 유한 문자열만 다룬다. 그런데 수치해석은 $\mathbb{R}$ 위에서 논다. 이 간극을 메우는 모형이 둘 있고, 실제 계산기는 그 어느 쪽도 아니다.

계산 가능한 해석학(computable analysis)은 실수를 “임의 정밀도의 유리수 근사열을 내놓는 기계”로 정의한다. 이 정의에서 $+,\times,\exp,\sin$ 은 전부 계산 가능하다. 하지만 등호 판정은 계산 불가능하다. $x = 0$ 을 확인하려면 근사열을 무한히 봐야 하는데, $x \ne 0$ 이면 언젠가 확정되지만 $x = 0$ 이면 영원히 확정되지 않는다(반결정 가능의 전형이다). 그래서 정확 실수 산술 라이브러리는 x == 0 을 제공하지 못하고, 구간 연산은 부호 판정에 “모름”을 반환한다. 덧붙여 계산 가능한 실수는 프로그램만큼만 있으므로 가산이고, 따라서 거의 모든 실수는 계산 불가능하다.

BSS 모형(Blum–Shub–Smale, 1989)은 반대쪽 이상화다. 실수 하나를 셀 하나에 담고 $+,-,\times,\div$ 와 부호 비교를 각각 1스텝에 처리한다고 가정한다. 수치해석 알고리즘의 연산 횟수를 세는 관행을 그대로 형식화한 모형이라 $\mathbb{R}$ 위의 P와 NP를 정의할 수 있고, 4차 다항식의 실근 존재성이 이 세계의 NP-완전 문제다. 동시에 이 모형은 자기가 얼마나 센 가정인지도 드러낸다. 만델브로 집합은 BSS 모형에서 결정 불가능이고, 더 노골적으로는 임의의 실수 상수를 하나 허용하면 그 상수의 이진 전개에 정지 문제의 답을 통째로 넣어 1스텝에 정지 문제를 풀 수 있다. 무한 정밀도 실수를 공짜로 저장하고 정확히 비교한다는 가정이 물리적으로 불가능한 힘을 몰래 들여온다는 뜻이다.

실제 계산기는 셋 중 어느 쪽도 아니다. 부동소수점 연산은 유한 집합 위의 연산이고, 메모리가 $M$ 비트인 기계는 상태가 $2^M$ 개인 유한 상태 기계다. 그러므로 원리적으로는 정지 문제가 결정 가능하다 — 상태를 전부 훑다가 반복이 나오면 무한 루프로 판정하면 된다. 물론 $2^M$ 이 우주적 크기라 아무 위안이 못 된다.⁴ 여기서 얻을 교훈은 두 가지다. 첫째, 실무의 벽은 계산 불가능성이 아니라 복잡도다. 둘째, 부동소수점은 BSS 모형도 아니다 — 결합법칙이 깨지고, 등호 비교가 반올림 순서에 좌우되며, 병렬 리덕션의 합산 순서만 바꿔도 결과 비트가 달라진다. 종이 위의 알고리즘이 옳다는 증명과 그 구현이 옳게 도는 것은 별개의 문제이고, 그 간극을 다루는 게 후진 오차 해석이다.

8. 관련 문서[편집]

논문 제목이 “On Computable Numbers, with an Application to the Entscheidungsproblem”이다. 즉 결정문제는 응용이고 본편은 계산 가능한 수의 정의였다. 부록으로 만든 기계가 컴퓨터 과학 전체의 기초가 된 셈인데, 이런 걸 보면 논문 제목의 “with an application to”는 함부로 넘길 게 아니다. ↩
“그럼 정지 판정기를 만들어 팔면 되겠네”라는 생각이 든다면, 그 판정기를 자기 자신에게 먹였을 때 무슨 일이 벌어지는지 5분만 생각해 보면 된다. 참고로 실무에서 쓰는 종료 증명 도구들은 순위 함수(ranking function)를 찾는 방식이라 “찾으면 종료 증명, 못 찾으면 모름”이다. 정직하게 반쪽짜리다. ↩
상금까지 걸린 문제였고 증명 자체는 인정받았지만, “보편 기계”의 정의에서 초기 테이프가 유한해야 하느냐를 두고 논쟁이 붙었다. 무한한 배경 패턴을 깔아도 된다면 그 배경을 만드는 데 이미 계산이 들어간 것 아니냐는 반론. 정의를 정하는 일이 증명보다 어려운 전형적 사례. ↩
64비트 배정도 배열 $10^6$ 개만 잡아도 상태 수가 $2^{6.4\times10^7}$ 이다. 관측 가능한 우주의 원자 수가 $10^{80}$ 쯤이니, “원리적으로 결정 가능”이라는 문장이 얼마나 공허할 수 있는지 보여주는 좋은 예다. ↩