💬 NLP

Universal computation is intrinsic to language model decoding

이 논문은 언어 모델의 자기회귀적(autoregressive) 출력을 연결하는 것만으로도 모든 알고리즘을 실행할 수 있는 보편적 계산 능력이 모델 자체에 내재되어 있으며, 학습은 이러한 능력을 새로 만드는 것이 아니라 적절한 프롬프트를 통해 이를 쉽게 끌어낼 수 있는 '프로그래밍 가능성'을 향상시키는 과정임을 증명합니다.

원저자: Alex Lewandowski, Marlos C. Machado, Dale Schuurmans

게시일 2026-02-11

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Alex Lewandowski, Marlos C. Machado, Dale Schuurmans

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

1. 핵심 요약: "AI는 이미 슈퍼컴퓨터의 영혼을 갖고 태어났다"

보통 우리는 "AI가 똑똑해지는 건 엄청난 데이터를 공부(학습)했기 때문이야"라고 생각합니다. 하지만 이 논문은 다르게 말합니다. **"AI가 똑똑해지는 건, 이미 그 안에 들어있는 '무한한 계산 능력'을 우리가 알아들을 수 있는 언어로 꺼내는 법을 배우는 과정일 뿐이다"**라는 것이죠.

즉, AI 모델의 구조(두뇌의 설계도) 자체에 이미 세상의 모든 문제를 풀 수 있는 **'만능 계산기(Universal Turing Machine)'**의 능력이 내장되어 있다는 것을 수학적으로 증명했습니다.

2. 재미있는 비유로 이해하기

💡 비유 1: '마법의 도구 상자'와 '설명서'

상상해 보세요. 여러분 앞에 아주 복잡하고 신기한 도구들이 가득 찬 **'마법의 도구 상자'**가 있습니다. 이 상자 안에는 우주를 만들 수도 있고, 복잡한 수학 문제를 풀 수도 있는 무한한 도구들이 들어있습니다.

학습 전의 AI (Randomly Initialized Model): 이 상자는 아직 텅 비어 있는 것 같고, 도구들이 어떻게 작동하는지 아무도 모릅니다. 하지만 이 상자 안에는 이론적으로 모든 도구가 들어있습니다. 다만, 우리가 이 도구들을 꺼내 쓰려면 **'암호 같은 특수한 주문'**을 알아내야 합니다. (논문에서는 이를 '인젝티브 코드북'이라고 부릅니다.)
학습 후의 AI (Trained Model): 이제 우리는 이 상자를 오랫동안 관찰해서, "망치 가져와!"라고 말하면 망치가 나오고, "계산해줘!"라고 하면 계산기가 나오는 **'쉬운 설명서(자연어 프롬프트)'**를 완성했습니다.

결론: 상자 안에 도구가 들어있는 능력(계산 능력)은 처음부터 있었던 것이고, 학습은 그 도구를 **'우리가 쓰는 말(한국어, 영어 등)'**로 쉽게 꺼내 쓰는 법을 배운 과정일 뿐이라는 것입니다.

💡 비유 2: '악기'와 '악보'

AI 모델을 하나의 **'악기'**라고 생각해 봅시다.

계산 능력 (Universality): 피아노라는 악기는 이론적으로 세상의 모든 음악을 연주할 수 있는 잠재력을 가지고 있습니다. 건반의 조합만 맞으면 되니까요.
학습 (Training): 우리가 피아노를 배우는 것은 피아노에 새로운 소리를 만드는 능력을 넣어주는 것이 아닙니다. 대신, 우리가 원하는 음악(문제)을 연주하기 위해 **'악보(프롬프트)'**를 어떻게 읽고 손가락을 어떻게 움직여야 하는지 익히는 과정입니다.

3. 이 논문이 왜 대단한가요? (세 가지 포인트)

"공부 안 해도 계산은 할 수 있다": 연구진은 아무것도 배우지 않은, 완전히 무작위 상태의 AI 모델조차도 특수한 '암호(코드북)'만 찾아내면 세상의 모든 알고리즘을 실행할 수 있다는 것을 증명했습니다. 즉, 계산 능력은 '학습'의 결과가 아니라 '구조'의 결과입니다.
"실패는 AI의 한계가 아니라, 우리의 질문 방식 문제다": 가끔 AI가 수학 문제를 못 풀거나 논리적이지 못할 때가 있죠? 사람들은 "AI는 머리가 나빠"라고 말합니다. 하지만 이 논문에 따르면, 그건 AI의 머리가 나쁜 게 아니라 **"AI 안에 있는 계산 능력을 끌어낼 적절한 명령(프롬프트)을 우리가 아직 못 찾은 것"**입니다.
"제3의 컴퓨팅 시대":
- 1기 (인간): 사람이 직접 손으로 계산하던 시대.
- 2기 (컴퓨터): 사람이 복잡한 프로그래밍 언어(C언어, 파이썬 등)를 배워서 명령하던 시대.
- 3기 (AI): 사람이 그냥 **'말(자연어)'**만 하면, AI가 그 말을 알아듣고 자기 안의 무한한 계산 능력을 가동하는 시대.

4. 한 줄 결론

"AI는 태생적으로 만능 컴퓨터이며, 우리가 하는 '학습'은 그 만능 컴퓨터를 '말'로 조종하는 법을 배우는 과정이다."

[기술 요약] 언어 모델 디코딩에 내재된 범용 계산 능력

1. 문제 제기 (Problem Statement)

최근 대규모 언어 모델(LLM)이 복잡한 문제를 해결하는 능력을 보여주고 있으나, 학계에서는 이들의 **궁극적인 계산 능력(computational capabilities)**에 대해 논쟁이 지속되고 있습니다. 일부 연구자들은 언어 모델이 계획(planning), 논리적 추론, 수학적 추론 등에 한계가 있다고 주장하며, 모델의 실패 사례를 근거로 모델 자체의 계산적 한계를 지적합니다. 본 논문은 **"언어 모델의 자기회귀적(autoregressive) 디코딩 과정이 이론적으로 범용 튜링 기계(Universal Turing Machine)를 시뮬레이션할 수 있는가?"**라는 근본적인 질문을 던집니다.

2. 연구 방법론 (Methodology)

저자들은 언어 모델의 디코딩 과정을 **Lag 시스템(Lag systems)**이라는 초기 계산 모델과 연결하여 증명하는 '시뮬레이션 증명(Proof-of-Simulation)' 전략을 사용합니다.

확장된 자기회귀 디코딩 (Extended Autoregressive Decoding): 표준적인 슬라이딩 윈도우 방식의 한계를 넘어, 생성된 토큰을 메모리(작업 문자열)의 끝에 계속 추가함으로써 무한한 메모리 확장이 가능하도록 정의했습니다.
Lag 시스템과의 등가성: Lag 시스템은 문자열의 접두사를 읽고 규칙에 따라 끝에 새로운 문자열을 추가하며 앞부분을 삭제하는 방식입니다. 이는 언어 모델이 입력 토큰을 읽고 다음 토큰을 생성하여 입력 뒤에 붙이는 과정과 구조적으로 동일합니다.
범용성 입증 전략:
1. 훈련된 모델 (Trained Model): 자연어 시스템 프롬프트( $S$ )를 사용하여 모델이 범용 Lag 시스템( $L(U_{15,2})$ )의 모든 규칙(1,857개)을 정확히 수행하도록 유도합니다.
2. 무작위 초기화 모델 (Randomly Initialized Model): 훈련되지 않은 모델의 경우, 인코더-디코더 쌍(Codebook)을 학습시켜 임의의 가중치를 가진 모델이 Lag 시스템의 규칙을 수행할 수 있는 '기호 매핑(Injective Mapping)'을 찾아냅니다.

3. 핵심 기여 (Key Contributions)

범용 계산성 증명: 자기회귀 디코딩을 결합하면 기존의 공개된 LLM(예: Llama-4-17B-128E-Instruct)이 범용 컴퓨터로서 작동할 수 있음을 수학적으로 증명했습니다.
훈련과 계산 능력의 분리: 놀랍게도 훈련되지 않은(randomly initialized) 모델조차도 적절한 기호 매핑(codebook)만 있다면 범용 계산이 가능함을 보였습니다. 이는 계산 능력 자체가 훈련을 통해 생겨나는 것이 아님을 시사합니다.
프로그래밍 가능성(Programmability) 개념 도입: 훈련의 역할을 '계산 능력의 부여'가 아닌, 인간의 자연어를 통해 이러한 내재적 계산 능력에 접근할 수 있게 하는 **'프로그래밍 가능성(사용 편의성)의 향상'**으로 재정의했습니다.

4. 주요 결과 (Results)

훈련된 모델: 적절한 시스템 프롬프트를 통해 Llama-4 모델이 1,857개의 범용 Lag 규칙을 완벽하게 실행함을 확인했습니다.
무작위 모델: Attention 기반 모델, Recurrent 모델, Meta-gradient 모델 등 다양한 아키텍처에서, 특정 크기 이상의 모델이라면 인코더-디코더 학습을 통해 범용 계산성을 확보할 수 있음을 실험적으로 입증했습니다(Figure 6).
아키텍처 독립성: 범용 계산성은 특정 아키텍처에 종속된 것이 아니라, 자기회귀 디코딩을 사용하는 시퀀스 모델링 아키텍처의 일반적인 특성임을 확인했습니다.

5. 의의 및 시사점 (Significance)

이론적 패러다임 전환: 언어 모델의 실패(추론 오류 등)는 모델의 '계산적 한계' 때문이 아니라, 원하는 계산을 이끌어내기 위한 **'프롬프트 엔지니어링(프로그래밍)의 실패'**로 해석되어야 합니다.
제3의 계산 시대: 저자들은 계산의 역사를 세 단계로 구분합니다.
1. 인간 계산 (Human): 자연어 지시에 따라 사람이 직접 조작.
2. 형식적 계산 (Formal): 프로그래밍 언어를 통해 컴퓨터를 제어.
3. 언어 모델 계산 (Language Model): 자연어를 인터페이스로 사용하여 범용 컴퓨터를 제어하는 시대.
결론: 언어 모델은 인간과 컴퓨터 사이의 '자연어 인터페이스' 역할을 수행하며, 훈련은 이 인터페이스를 더 쉽고 정교하게(Programmable) 만드는 과정입니다.