Theory of Computation의 개념과 3대 핵심 기둥
전자 컴퓨터가 실제로 발명되기도 전인 20세기 초반, 힐베르트·괴델·처치·튜링·클리니 등의 수리논리학자들은 "기계적이고 단순한 방법(알고리즘)으로 해결 가능한 수학 문제의 범위는 어디까지인가?"를 묻기 시작했습니다. 여기서 출발한 계산이론(Theory of Computation)은 오늘날 다음 3가지 상호 연결된 핵심 축으로 구성됩니다.
오토마타 & 형식언어 이론
(Automata & Formal Languages)
메모리 제약에 따라 추상 기계가 인식할 수 있는 형식언어의 등급을 분류합니다. 유한 상태 기계(FSM · 정규표현식)에서 스택을 추가한 푸시다운 오토마타(PDA · 문맥자유문법), 선형 유계 오토마타(LBA · 문맥의존문법), 그리고 무한 테이프를 가진 튜링 기계로 이어지는 촘스키 계층(Chomsky Hierarchy)을 다룹니다.
계산가능성 이론
(Computability Theory)
"이 문제를 푸는 알고리즘이 아예 존재하는가?"를 연구합니다. 튜링 기계, 재귀함수, 람다 계산법, 마르코프 알고리즘, 포스트 시스템이 계산 능력 면에서 완벽히 동등하다는 처치-튜링 명제를 토대로 결정 가능(Decidable) vs 결정 불가능(Undecidable, 예: 정지 문제)의 절대 경계를 증명합니다.
계산복잡도 이론
(Computational Complexity Theory)
이론적으로 풀 수 있는(Decidable) 문제라도 우주의 수명보다 오래 걸린다면 무용지물입니다. 입력 크기 N에 대해 필요한 시간·공간 자원에 따라 P(다항 시간 해결), NP(다항 시간 검증), NP-complete, PSPACE, EXPTIME, 병렬 부류 NC, 확률 부류 BPP, 양자 부류 BQP 등으로 난이도 지도를 그립니다.
AI와 LLM에서 Theory of Computation이 중요한 5대 이유
과거에는 계산이론이 컴파일러나 암호학의 기초로만 여겨졌으나, 오늘날 대규모 언어 모델(LLM)과 추론형 AI(Reasoning Models) 시대에 들어서면서 계산이론은 "트랜스포머가 본질적으로 무엇을 계산할 수 있고 무엇을 못 하는가", "왜 생각의 사슬(CoT)이 AI 지능을 도약시키는가", "왜 검증이 생성보다 쉬운가"를 규명하는 가장 강력한 설계 나침반이 되었습니다.
단일 패스 트랜스포머의 회로 복잡도 한계 (TC0) vs CoT를 통한 튜링 완전성 돌파
회로 복잡도 이론(Circuit Complexity) 연구(Merrill & Sabharwal 등)에 따르면, 레이어 깊이가 고정된 표준 트랜스포머(Transformer)가 중간 토큰 생성 없이 단 한 번의 순전파(1-step Forward Pass)로 수행할 수 있는 계산 능력은 상수 깊이 임계 회로 부류인 TC0 내부로 제한됩니다(TC0 ⊆ NC1 ⊆ P). 이 때문에 단일 패스 LLM은 입력 길이가 길어질수록 단순한 짝수/홀수 패리티 판별, 다중 괄호 깊이 검증, 임의 길이 상태 추적(State Tracking), 다단계 논리 추론과 같은 NC1-완전 또는 P-완전 문제를 원리적으로 처리하지 못하고 환각(Hallucination)을 일으킵니다.
반면 모델이 Chain-of-Thought (CoT) 방식으로 중간 추론 토큰을 생성하여 스스로의 컨텍스트 창(외부 테이프 역할)에 기록하고 다시 읽는 과정을 반복하면, 단일 패스의 TC0 병목을 깨고 다항 시간 복잡도 P 및 사실상 튜링 기계(Turing Machine)와 동등한 보편 계산 능력(Turing-completeness)에 도달할 수 있습니다. 또한 표준 Self-Attention의 O(N2) 시공간 복잡도 병목을 FlashAttention 타일링이나 O(N) 선형 순환 구조를 지닌 Mamba(SSM) 등으로 극복하는 시도 역시 오토마타 상태 압축과 복잡도 이론의 직접적 성과입니다.
유한 오토마타(FSM) & 문맥자유문법(CFG) 기반 LLM 구조화 출력 제어
LLM은 본질적으로 어휘 사전 전체에 대한 확률 분포를 계산하는 통계적 모델이므로, 자유롭게 텍스트를 생성하면 JSON 닫는 괄호를 빠뜨리거나 SQL 구문 오류, 존재하지 않는 API 파라미터를 출력할 위험이 상존합니다.
이를 해결하기 위해 최신 AI 추론 엔진(Outlines, vLLM, Guidance, llama.cpp GBNF 등)은 촘스키 계층의 형식언어·오토마타 이론을 디코더 단계에 직접 이식합니다. JSON Schema는 결정적 유한 오토마타(DFA)로, 프로그래밍 언어 AST나 복잡한 중첩 수식은 문맥자유문법(CFG) 및 푸시다운 오토마타(PDA)로 컴파일한 뒤, 매 토큰 샘플링 직전에 현재 오토마타 상태에서 전이가 불가능한 토큰들의 로짓(Logit)을 음의 무한대(-∞)로 마스킹하는 제약 디코딩(Constrained Decoding)을 수행하여 100% 문법 무결성을 보장합니다.
P vs NP 검증 비대칭성과 Test-Time Compute(추론 모델)의 폭발적 성장
계산복잡도 이론의 핵심 통찰인 P vs NP 구조는 "정답을 처음부터 완벽하게 찾아내는 것(Generation)은 극도로 어렵지만, 누군가 제시한 후보 해답이 맞는지 검사하는 것(Verification)은 훨씬 쉽다"는 검증자-생성자 비대칭성(Verifier-Generator Gap)을 설명합니다.
최신 추론 AI 패러다임은 바로 이 계산이론적 비대칭성을 공학적으로 극대화한 결과입니다. Google DeepMind의 AlphaProof는 난해한 수학 정리 증명을 탐색하되 검증은 P 시간 내 확정 판정하는 Lean 4 형식 증명 검증기에 맡겼고, OpenAI o1/o3 및 DeepSeek-R1(RLVR) 역시 단위 테스트 통과 여부·수학 답안 정오처럼 다항 시간 내 자동 검증 가능한 보상을 활용해 학습과 테스트 타임 탐색(Test-Time Compute)을 수행함으로써 단일 순전파 한계를 뛰어넘는 추론 성능을 달성했습니다.
정지 문제(Halting Problem) · 라이스 정리와 AI 안전성 · 자율 에이전트 통제
자율 AI 코딩 에이전트가 생성한 소프트웨어, 혹은 에이전트 자신이 다른 에이전트를 호출하며 실행하는 워크플로우에 대해 "이 AI 코드가 무한 루프에 빠지지 않고 반드시 정지하는가?", "악의적 프롬프트 인젝션이나 치명적 보안 결함을 절대 유발하지 않는가?"를 100% 완벽하게 판별할 수 있을까요?
계산가능성 이론의 튜링 정지 문제(Halting Problem)와 이를 모든 비자명한 의미적 성질로 일반화한 라이스 정리(Rice's Theorem)는 튜링 완전한 프로그램의 동작 성질을 보편적·완전 자동으로 판별하는 알고리즘은 수학적으로 존재 불가능함(Undecidable)을 엄밀히 증명합니다. 따라서 현대 AI 안전성(AI Safety) 설계는 불가능한 "100% 정적 완벽 필터링"에만 의존하지 않고, 실행 스텝 상한(Max Tokens / Timeout), 샌드박스 격리, 권한 최소화, 휴먼-인-더-루프(HITL) 같은 유한 자원 경계와 다층 방어를 필수 원칙으로 삼습니다.
병렬 복잡도(NC) · 양자 가속(BQP) · 계산주의(Computationalism) 철학
GPU 수만 장을 동원한 AI 가속에서도 복잡도 이론은 결정적입니다. 행렬 곱셈과 어텐션 Score 계산은 고도로 병렬화 가능한 NC 부류 성격이 강하지만, 자기회귀(Autoregressive) 토큰 생성은 이전 토큰에 순차 의존하므로 하드웨어 병렬성만으로는 즉각 단축되지 않습니다. 투기적 디코딩(Speculative Decoding)은 가벼운 드래프트 모델의 짧은 순차 예측을 거대 모델의 단일 병렬 검증 배치로 한 번에 평가하여 이 병목을 영리하게 우회합니다.
나아가 하단 문헌의 Allen Newell(기계와 계산)과 David Chalmers(Computationalism)가 정립한 계산주의는 "지능적 인지와 의식조차 물리적 기질 위에서 실행되는 형식 계산 시스템으로 구현될 수 있는가?"라는 AI의 근본 질문을 던지며, 오늘날 LLM 내부 가중치에서 오토마타·회로 구조를 역추적하는 기계적 해석가능성(Mechanistic Interpretability) 연구로 이어지고 있습니다.
| 계산이론 핵심 개념 | 이론적 함의 / 복잡도·결정 경계 | 최신 AI · LLM 구현 및 파급 효과 |
|---|---|---|
| 회로 복잡도 (TC0 vs P) | 상수 깊이 병렬 회로는 순차 상태 추적 불가 | 단일 패스 한계를 CoT(중간 토큰 스크래치패드)로 돌파하여 튜링 완전성 근접 |
| FSM(정규) & PDA(문맥자유 CFG) | 상태 전이표·스택 기반 엄밀 문법 수리 | Outlines · vLLM · GBNF 로짓 마스킹으로 JSON/SQL/API 100% 구조화 출력 보장 |
| P vs NP 비대칭성 | 정답 탐색보다 주어진 답의 다항시간 검증이 압도적으로 용이 | AlphaProof(Lean 4), o1/o3, DeepSeek-R1(RLVR) 및 Test-Time Search 엔진 |
| 정지 문제 & 라이스 정리 | 임의 프로그램의 정지·의미 성질 보편 판별 불가(Undecidable) | 자율 AI 에이전트 샌드박싱, 스텝/토큰 타임아웃, 다층 가드레일 설계 필수화 |
| 병렬(NC) · 시간복잡도 · 양자(BQP) | O(N2) 병목, 병렬 가능 연산과 순차 의존 연산의 엄밀한 분리 | FlashAttention, Mamba(O(N) SSM), Speculative Decoding, 양자 AI 가속 탐색 |
원전 해설 및 계산·언어·복잡도 분류표 (원본 보존)
계산이론 (Theory of Computation) 은 컴퓨터과학의 한 분야로, 어떤 문제를 컴퓨터로 풀수 있는지, 또 얼마나 효율적으로 풀수 있는지를 탐구한다. 이 분야는 크게 계산가능성 이론 (Computability Theory) 과 계산복잡도이론 (Computational Complexity Theory) 으로 나뉘어 있는데, 두 분야 모두 추상 기계를 다룬다.... 위키백과 : 계산이론
Computation 은 주어진 입력으로부터 문제의 해법을 찾는 것으로 정의될 수 있다. 그것이 컴퓨터과학과 수학의 하위과목인 계산이론 (Theory of Computation) 에서 다루는 것이다. 그것은 현대적인 전자컴퓨터가 발명되기 전인 20 세기에 처음 등장했다. 그때 수학자들은 수학문제들이 간단한 방법으로 해결가능한지 아닌지를 알려고 노력했다. 첫째 단계가 문제를 풀기위한 "간단한 방법 (simple method)" 이 의미하는 바를 정의하는 것이었다. 달리말하면, 계산의 형식모델 (formal model of computation) 을 필요로 했다.
초기의 연구자들에 의해 여러개의 계산모델이 만들어졌다. 그중 하나가 튜링기계 (Turing Machine) 으로서 read/write head 가 스캐닝하는 데로 언제든지 사각형의 무한 길이의 테이프상에 문자를 저장하는 것이다. 또다른 모델이 재귀함수 (Recursive Function) 으로서 수에 관한 연산을 위해 함수와 함수의 조합을 사용한다. 람다 계산법 (Lambda Calculus) 도 유사한 접근방법을 사용한다. 이와는 다른 것으로서 마르코프 알고리즘 (Markov Algorithm) 과 포스트 시스템 (Post Systems) 은 문자열에 관한 연산을 위해 grammar-like rules 를 사용한다. 이러한 형식모델 (formalisms) 들은 계산능력에서 동등한 것으로 보여지는데 -- 즉 그중 하나의 모델로 수행될 수 있는 어떠한 계산도 다른 모델로도 수행될수 있다. 또한 그 모델들은 컴퓨터가 무한 메모리를 가지고 있다고 가정하면 보통의 컴퓨터에서 동등한 능력을 보인다. 결국 알고리즘 개념이 "적절하게 (proper)" 형식화되면 모든 알고리즘은 Turing Machine 에서 수행될수 있다고 알려지게 되었고 ; 그것은 처치-튜링 명제 (Church-Turing Thesis) 라고 알려지게 되었다. 대개 어떤 것이 기계로 계산될 수 있는가에 대한 의문은 계산가능성 이론 (Computability Theory) 에서 다루어진다.
계산이론 (Theory of Computation) 은 이러한 일반적인 계산모델을 연구하며, 또한 컴퓨팅의 한계도 연구한다 : 어떤 문제가 컴퓨터로 해결불가능 한가? (예를들면 halting problem, Post correspondence problem) 어떤 문제가 컴퓨터로 해결가능 하지만 해법이 비현실적이어서 계산에 너무 오랜 시간이 필요한가? (예를들면 Presburger arithmetic) 주어진 해법을 체크하는 것보다 문제를 해결하는 것이 더 어려울 수 (hard) 있는가? (예를들면 복잡도 부류 P 와 NP). 대개 주어진 문제에서 필요로 하는 시간과 메모리와 관련된 의문은 계산복잡도이론 (Computational Complexity Theory) 에서 다루어진다.
일반적인 계산모델에 덧붙여서, 더 단순한 계산모델들이 특별히 제한된 응용에 사용된다. 예를들면 regular expressions 이 유닉스와 Perl 같은 프로그램 언어에서 문자열 패턴을 나타내는데 사용된다. Regular expression 과 수학적으로 동등한 또다른 형식 (formalism) 인 Finite automata 는 회로설계와 여러 종류의 problem-solving 에 사용된다. 문맥자유 문법 (Context Free Grammar) 는 프로그램 언어 문법에서 사용된다. Non-deterministic pushdown automata 는 context-free grammar 와 동등한 또다른 형식이다. Primitive recursive function 은 recursive function 의 하위부류이다.
계산의 다른 모델들은 다른 작업을 수행하는 능력을 가진다. 계산모델의 능력을 측정하는 한가지 방법은 그 모델이 생성할 수 있는 형식언어 (Formal Language) 의 종류를 연구하는 것이다 ; 이것은 언어에 대한 촘스키계층 (Chomsky Hierarchy) 로 이끈다.
다음 표에서는 계산가능성 이론 (Computability Theory) (청색) 과 계산복잡도이론 (Computational Complexity Theory) (녹색) 에서 고려되는 문제들 (또는 언어, 문법들) 을 분류하는 일부를 보여준다. 만일 문제 X 가 Y 의 진부분집합 이라면 X 는 Y 의 아래에 위치하고 검은색 선으로 연결된다. 만일 X 가 부분집합이지만 같은 집합 (equal sets) 인지도 모를 때는 점선으로 연결된다. ........... (Wikipedia : Computation)

