소프트맥스 트랜스포머도 튜링 완전하다, 튜링 기계 대신 카운터 기계로

ICLR 2026 구두 발표 ‘Softmax Transformers are Turing-Complete’ 짧게 읽기

Softmax Transformers are Turing-CompleteICLR 2026 Oral

짧은 읽기
딥러닝의 과학
트랜스포머 표현력
하드 어텐션 없이 소프트맥스 어텐션만으로 생각의 사슬 트랜스포머가 튜링 완전함을 보인 논문을 짧게 읽는다. 열쇠는 튜링 기계 대신 카운터 기계를 흉내 내는 것이다.
공개

2026년 9월 30일

한 줄 요약

생각의 사슬(chain of thought, CoT)을 쓰는 트랜스포머가 튜링 완전하다는 기존 증명은 모두 하드 어텐션(hard attention)에 기댔다. 이 논문은 실제로 쓰는 소프트맥스 어텐션으로도 튜링 완전함을 증명한다. 증명에 쓴 구성은 짧은 입력으로 배워 긴 입력에서도 맞히는 길이 일반화까지 보장받는다.

무엇이 달라졌나

지금까지의 증명은 튜링 기계를 그대로 흉내 냈다. 테이프 머리가 어디 있는지를 어텐션으로 정확히 집어내야 했는데, 이 일은 점수가 가장 높은 위치에만 가중치를 몰아주는 하드 어텐션이라야 쉬웠다. 소프트맥스로도 되는지는 열린 문제였다(1절).

논문의 답은 세 층으로 나온다. 입력 기호가 한 종류뿐이거나 \(a_1^*\cdots a_n^*\) 꼴로 기호가 차례로 몰려 있는 언어라면, 인과 마스킹만 있는 소프트맥스 CoT 트랜스포머로 재귀 열거 가능한 언어를 모두 알아본다(정리 3.1, 명제 3.3). 기호가 자유롭게 섞인 일반 언어에서는 그렇지 않다. 회문조차 알아보지 못한다(명제 4.1). 여기에 상대 위치 부호화(relative positional encoding, RPE)를 하나 더하면 임의의 언어에서 튜링 완전해진다(정리 4.3).

x = (a의 개수) − 2 × (τ₀의 개수)입력생각의 사슬aaaaτ₀τ₀τ₁x=4x=2x=0x > 0 이면 τ₀를 쓴다 (x에서 2를 뺀다)x = 0 이면 τ₁을 쓰고 받아들인다카운터는 어디에도 적지 않고, 셀 때마다 새로 구한다

(가) 셈으로 흉내 내는 카운터 기계

a1b2a3□4□5…□21끝22위치 21이 보는 자리10121 = 10101 (이진수)첫 0 뒤의 세 자리1이 선 자리가 a가 있는 자리 1, 3과 꼭 맞을 때표시를 찍는다. 이제 수 21이 a의 배치를 담는다

(나) 상대 위치로 순서를 수에 담기

(가) a의 개수가 짝수인지 가리는 카운터 기계(논문 예제 1, 그림 1)를 입력 aaaa에서 돌린 모습. 매 단계 앞선 토큰을 세어 카운터 x를 다시 구하고, 그 값에 따라 다음 전이 토큰을 쓴다. (나) 4절 1단계를 입력 aba에 적용한 모습. 빈 토큰을 붙여 가다가 길이 ℓ을 이진수로 쓴 뒤 첫 0 다음 자리들이 a의 배치(101)와 같아지는 ℓ = 21에서 멈춘다. 상대 위치 부호화는 위치 ℓ이 그 1이 선 자리만 보게 해서 이 일치를 셈으로 확인하게 한다. b의 배치도 같은 방식으로 다른 수에 담는다. 논문의 구성을 작은 입력으로 옮긴 개념도다.

어떻게 보였나

튜링 기계 대신 민스키의 카운터 기계(counter machine)를 흉내 낸다. 카운터 기계는 정수 카운터 몇 개와 상태만 가진 기계로, 카운터가 0인지 아닌지 보고 더하거나 뺀다. 입력 기호별 개수를 담는 카운터 \(n\)개에 보조 카운터 3개만 더하면 튜링 기계가 하는 일을 다 한다(보조정리 3.5).

증명은 C-RASP라는 작은 프로그래밍 언어를 거친다. C-RASP는 앞선 위치 가운데 조건을 만족하는 곳의 수를 세고 비교하는 연산만 있다. 선행 연구(Huang 외, 2025)는 C-RASP 프로그램을 소프트맥스 트랜스포머로 옮길 수 있고, 그렇게 옮긴 모델은 이상화한 학습 절차에서 길이 일반화가 된다는 것을 보였다. 논문은 이 결과를 CoT로 넓힌다(명제 2.1, 2.3).

핵심은 카운터 값을 어디에도 저장하지 않는다는 데 있다. CoT의 토큰 하나하나가 카운터 기계의 전이 하나이고, 지금 카운터 값은 입력 기호의 개수에 지금까지 쓴 전이 토큰들의 효과를 더해 매번 새로 센다(식 3, 4). 그림 (가)처럼 a의 개수가 짝수인지 가리는 기계라면 a의 개수에서 \(\tau_0\) 개수의 두 배를 빼면 된다(예제 1). 세기는 소프트맥스 어텐션이 원래 잘하는 일이다.

일반 언어에서는 세기만으로 순서를 알 수 없다. ab와 ba는 기호 개수가 같다. 그래서 1단계에서 빈 토큰을 붙여 가다가, 현재 길이 \(\ell\)을 이진수로 쓴 뒤 첫 0 다음 자리들이 한 기호의 배치와 꼭 맞을 때 표시 토큰을 찍는다. 이 확인을 위해 위치 \(\ell\)이 그 이진수에서 1이 선 자리만 보게 하는 RPE를 쓴다. 이렇게 입력 전체가 몇 개의 수로 바뀌면, 2단계에서 그 수를 초깃값으로 카운터 기계를 돌린다(4절). 이 RPE는 풀려는 언어와 상관없이 하나로 고정돼 있다.

눈여겨볼 점

첫째, 모델에 몇 가지 이론적 장치가 들어 있다. 어텐션 점수에 \(\log n\)을 곱하고, 피드포워드 층에 헤비사이드(Heaviside) 활성 함수를 허용한다(2.1절). 저자들은 입력 길이가 정해지면 헤비사이드를 ReLU로 얼마든지 가깝게 근사할 수 있다고 쓴다. 증명에 쓴 RPE는 어텐션 점수에 상수를 더한다는 점에서 ALiBi나 T5식 편향과 같지만, 어느 위치에 더할지를 거리가 아니라 이진수 구조로 정한다(4절, 부록 A.3).

둘째, 튜링 완전성은 무엇을 원리상 할 수 있는지를 말할 뿐 얼마나 빨리 하는지는 말하지 않는다. 이 구성에서 카운터 값 \(N\)을 만들려면 CoT 토큰이 적어도 \(N\)에 비례해 필요하고, 카운터 기계로 튜링 기계를 흉내 내면 걸음 수가 지수적으로 는다고 알려져 있다. 계산 복잡도와의 연결은 저자들도 다음 과제로 남겼다(6절).

셋째, 실험은 카운터 기계의 전이 기록 전체를 정답 CoT로 주고 학습시켰다(부록 D). 길이 1에서 100까지로 학습하고 201에서 300까지로 시험했을 때, 이진 표현에 RPE를 쓴 모델은 다섯 과제 모두 100%였고 RPE를 뺀 모델은 0%였다(표 2). RPE를 뺀 쪽은 6층 모델로 더 컸다(표 3). 모델은 추론 과정을 스스로 찾아내지 않았다. 정해 준 과정을 긴 입력에서도 그대로 따라 했을 뿐이다. 리뷰 점수는 2점에서 10점까지 크게 갈렸고, 가장 낮은 점수를 준 리뷰어는 튜링 완전성이라는 말을 이 결과에 그대로 써도 되는지부터 물었다.

열린 질문

  1. 실제 모델이 쓰는 RoPE나 학습된 위치 편향만으로도 같은 결론이 나올까. 그렇지 않다면 위치 부호화의 어떤 성질이 순서를 수로 바꾸는 데 필요한지 가를 수 있을까.

이해 확인

인과 마스킹만 있는 CoT C-RASP가 일반 언어에서 튜링 완전하지 않은 까닭으로 가장 알맞은 것은?

  1. 소프트맥스 어텐션은 개수를 셀 수 없기 때문이다
  2. CoT가 유한한 길이에서 반드시 멈추기 때문이다
  3. 세는 연산만으로는 기호의 순서를 충분히 구별하지 못해, 회문 같은 언어를 알아보지 못하기 때문이다
  4. 카운터 기계는 튜링 기계보다 약하기 때문이다

길이 n까지의 입력에서 이런 모델은 n의 다항식 크기 오토마톤으로 흉내 낼 수 있다(보조정리 4.2). 회문은 그보다 훨씬 많은 상태가 필요하므로 알아볼 수 없다. 카운터 기계는 보조 카운터 3개만 더하면 튜링 완전하고(보조정리 3.5), 모자란 것은 순서 정보다. 상대 위치 부호화가 이를 채운다.

논문 정보