AI 관점에서 본 Computability Theory의 개념과 4대 핵심 질문
인공지능(AI) 모델은 GPU 위에서 행렬 연산과 확률 추론을 수행하지만, 그 본질은 여전히 디지털 알고리즘(튜링 기계로 시뮬레이션 가능한 계산 과정)입니다. 계산가능성 이론은 AI의 속도를 논하는 계산 복잡도 이론보다 한 단계 더 근원적인 층위에서, "컴퓨터·신경망이라는 물리적 알고리즘 체계가 애초에 도달할 수 있는 지능과 문제 해결의 상한선"을 다음 4가지 축으로 정의합니다.
AI도 절대 풀 수 없는 문제가 존재하는가?
무제한의 파라미터, 데이터, GPU 시간이 주어지더라도 어떤 알고리즘으로도 풀 수 없는 결정 불가능(Undecidable) 문제가 존재합니다. 대표적으로 결정문제와 정지문제(Halting Problem)가 있으며, AI가 생성한 임의의 코드가 무한 루프에 빠질지 100% 완벽히 예측하는 판별기는 원리적으로 존재할 수 없습니다.
신경망·양자컴퓨터는 튜링 기계를 넘어서나?
처치-튜링 명제에 따르면 튜링 기계, 람다 계산법, 재귀함수는 계산 가능한 함수의 범위가 정확히 같습니다. 양자컴퓨터(Quantum Computer)나 확률적 딥러닝 모델도 속도(복잡도)는 바꿀 수 있으나, 계산 가능성 자체의 경계는 여전히 튜링 기계와 동등합니다.
LLM 단일 패스는 왜 튜링 기계보다 약한가?
촘스키 계층이 보여주듯 기계의 힘은 메모리 구조(유한 상태 ➔ 스택 ➔ 유한 테이프 ➔ 무한 테이프)에 달려 있습니다. 실제 AI는 유한 정밀도(BF16/FP8)와 고정 컨텍스트 길이를 가지므로 단일 순전파는 유한 상태/상수 깊이 회로 수준에 머물지만, 외부 메모리·도구 루프를 붙이면 튜링 완전성에 근접합니다.
오라클과 무한 정밀도 AI는 현실적인가?
이론적으로 정지 문제를 즉답하는 블랙박스인 오라클 기계(Oracle Machine)나 무한 정밀도 실수(Real Computation, 무한 정밀도 RNN 이론 등)를 가정하면 튜링 한계를 넘습니다. 그러나 유한 노이즈가 존재하는 현실 물리 세계의 AI 반도체에서는 무한 정밀도 계산이 불가능하므로, 실제 AI는 언제나 유한 계산가능성 계층 내부에서 동작합니다.
AI와 LLM에서 Computability Theory이 중요한 5대 이유
"LLM의 파라미터를 10조 개로 늘리고 데이터를 모두 학습시키면 모든 문제를 완벽히 풀 수 있을까?"라는 질문에 대해, 계산가능성 이론은 단순한 경험적 관찰이 아닌 수학적 불변 법칙(대각선 논법, 리덕션, 정지 문제)으로 명확한 답을 제시합니다. 최신 AI 및 LLM 연구에서 계산가능성 이론이 핵심적인 5가지 이유는 다음과 같습니다.
환각(Hallucination)의 계산적 불가피성 증명 (Diagonalization)
최신 이론 연구(예: Xu et al., "Hallucination is Inevitable: An Innate Limitation of Large Language Models")는 계산가능성 이론의 고전적 도구인 튜링 기계 열거(Enumeration)와 칸토어-튜링 대각선 논법(Diagonalization)을 LLM에 직접 적용했습니다. 모든 LLM은 결국 계산 가능한(Computable) 함수이므로, 계산 가능한 모든 정답 함수 집합을 100% 빠짐없이 완벽하게 학습·출력할 수 있는 단일 LLM은 수학적으로 존재할 수 없으며, 형식적 세계 모델과 완벽히 일치하지 않는 환각(Hallucination)은 구조적·원리적으로 완전히 제거 불가능함이 증명됩니다.
AI 안전성(Alignment) 검증과 자율 에이전트 통제의 이론적 경계
자율 AI 에이전트가 코드를 생성하고 툴을 연쇄 호출하는 시스템은 사실상 튜링 완전한 동적 실행 루프입니다. 정지 문제(Halting Problem)와 이를 모든 비자명한 프로그램 의미(Semantic Property)로 확장한 라이스 정리(Rice's Theorem)에 따라, 임의의 AI가 생성한 프로그램이나 에이전트 정책이 "절대 탈옥되지 않는지", "항상 유한 시간 내 안전하게 종료되는지"를 100% 정확도로 자동 사전 판별하는 보편적 감시 알고리즘은 존재하지 않습니다.
LLM + 외부 도구·CoT 루프(Agentic Tape)의 이론적 필연성
고전 연구에서 Siegelmann과 Sontag(1995)는 순환 신경망(RNN)이 튜링 완전하려면 무한 정밀도 가중치/신호가 필요함을 보였습니다(아래 원전 목록에도 수록됨). 그러나 현실 GPU 위의 트랜스포머는 유한 정밀도(FP16/BF16/FP8)와 고정 컨텍스트 창을 가지므로 순수 단일 패스만으로는 계산 능력이 엄격히 제한됩니다. 현대 LLM이 Chain-of-Thought(자기 기록) + Python 실행기 + 외부 벡터 DB/파일 시스템을 결합하는 이유는, 튜링 기계의 '무한 읽기/쓰기 테이프'를 외부로 분리해 튜링 완전한 계산 능력을 획득하기 위함입니다.
초지능 이론 AIXI · 콜모고로프 복잡도와 LLM "압축 = 지능" 원리
범용 인공지능의 이상적 수학 모델인 마르쿠스 후터(Marcus Hutter)의 AIXI와 레이 솔로모노프(Ray Solomonoff)의 보편 귀납 추론(Solomonoff Induction)은 계산가능성 이론의 전치 튜링 기계(Prefix Turing Machine)와 콜모고로프 복잡도(Kolmogorov Complexity) 위에서 정의됩니다. 그러나 가장 짧은 프로그램 길이 K(x)와 차이틴 상수(Chaitin's Ω) 자체가 비계산 가능(Uncomputable)이기 때문에, 오늘날 LLM의 다음 토큰 예측 사전학습은 바로 이 비계산 가능한 보편 귀납 지능을 유한 계산 자원으로 근사하는 가장 실용적인 접근으로 해석됩니다.
인간 지능과 기계 지능의 동치 논쟁 (강인공지능의 철학적 기초)
처치-튜링 명제의 물리적 확장판인 물리적 처치-튜링 명제(Physical Church-Turing Thesis)는 "우주 속 물리적 시스템(인간 뇌 포함)이 수행할 수 있는 모든 정보 처리는 튜링 기계로 시뮬레이션 가능하다"고 봅니다. 반면 로저 펜로즈 등은 괴델 불완전성과 계산 불가능성을 근거로 반론을 펴며 논쟁해 왔습니다. 이는 하단 참고 논문의 계산가능성과 심적과정 및 계산가능성과 전산적 마음이 탐구해 온 AGI(범용 인공지능) 가능성의 최전선 주제입니다.
AI 개발자들에게 Computability Theory가 가지는 5대 실무 의미
현업 AI/LLM 엔지니어에게 계산가능성 이론은 추상적인 수학 시험 과목이 아닙니다. 에이전트 시스템, RAG, 코드 생성, 가드레일을 설계할 때 "무엇에 자원을 쓰고 무엇을 절대 맹신하지 말아야 하는가"를 결정하는 가장 냉철한 아키텍처 기준입니다.
"불가능한 오라클" 구축에 시간 낭비 금지
라이스 정리와 정지 문제 덕분에 "LLM 출력이 100% 환각이 없고 100% 보안상 안전함을 사전 증명하는 만능 필터"는 불가능함을 압니다. AI 개발자는 완벽한 단일 가드레일 대신 다층 방어(Defense-in-Depth)와 결정론적 단위 검증으로 전략을 세워야 합니다.
LLM(제어기)과 외부 상태(Tape)의 분리 설계
유한 정밀도 트랜스포머에 복잡한 상태 추적이나 정밀 산술을 강요하지 마세요. 계산은 Python REPL·SQL 엔진·FSM 상태 머신에 위임하고, LLM은 외부 메모리(테이프)를 읽고 쓰는 제어 헤드 역할만 담당하도록 설계해야 신뢰성이 극대화됩니다.
확률적 생성과 결정 가능 검증(Decidable Verifier) 결합
신뢰할 수 있는 AI 프로덕트는 비결정적 LLM 생성기 + 결정 가능한(Decidable) 형식 검증기(JSON Schema 파서, 컴파일러, 린터, 테스트 스위트, Z3/Lean 검증기)의 결합으로 완성됩니다. 검증 가능한 문제를 고르는 능력이 곧 AI 제품 성공률입니다.
에이전트 무한 루프 · 비용 폭주 제어 필수화
서브에이전트 호출과 도구 루프를 허용하는 순간 시스템은 튜링 완전해지며 정지 보장이 사라집니다. 모든 AI 에이전트에는 반드시 최대 반복 횟수(Max Turns), 토큰/비용 예산, 순환 상태 탐지, 타임아웃 및 컨테이너 샌드박스를 하드코딩해야 합니다.
유행하는 AI 프레임워크를 넘어 변치 않는 제1원리(First Principles) 확보
프롬프트 기법, 모델 아키텍처, 에이전트 SDK는 매년 교체되지만 처치-튜링 명제, 촘스키 계층, 정지 문제, 대각선 논법은 어떤 하드웨어와 모델이 등장해도 변하지 않는 계산의 물리 법칙입니다. 계산가능성 이론을 이해한 AI 개발자는 새로운 AI 도구나 논문 앞에서 "진짜 본질적인 표현력 확장인지, 아니면 유한 자원 내의 휴리스틱 개선인지"를 즉시 간파할 수 있습니다.
원전 해설 및 4대 핵심 질문 아카이브 (원본 보존)
계산가능성 이론은 어떤 문제를 알고리즘 (또는 Turing Machine) 으로 해결할 수 있는가 (다양한 제약과 확장이 있는 가운데서) 를 다루는 계산이론 (Theory of Computation) 의 일부분이다. 그것은 4 개의 주요한 의문을 제기한다 :
- 어떤 문제를 Turing machine 이 해결할 수 있는가?
- 어떤 다른 시스템이 Turing machine 과 동등한가?
- 어떤 문제들이 더 강력한 기계들을 필요로 하는가?
- 어떤 문제들이 덜 강력한 기계로도 풀릴 수 있는가?
계산이론 (Theory of Computation) 에서는 문제들의 부류가 다른 부류의 부분집합인 관계를 보여주는 chart 를 볼 수 있다.
어떤 문제를 Turing machine 이 해결할 수 있는가?
어떤 문제도 해결할 수 없다. 결정불가능성 (undecidable) 문제는, 무제한의 시간과 메모리가 주어지더라도 ,어떤 알고리즘으로도 풀 수 없는 것이다. 많은 결정불가능성 문제들이 알려져 있다. 예를들면 결정문제 (Entscheidungsproblem) (독일어로 'decision problem') 가 그것이다. 즉 일차 술어계산 (First order predicate calculus) 의 문장이 주어졌을 때 그것이 유효한지 (universally valid) 여부를 결정하는 문제이다. Alonzo Church 와 Alan Turing 은 각각 그것이 결정불가능하다고 증명했다. 정지문제 (Halting Problem) 는 하나의 프로그램과 그것에 대한 입력이 주어졌을 때 그것이 영원히 작동할 것인지 정지할 것인지를 결정하는 문제이다. Turing 은 그것도 또한 결정불가능하다고 증명했다. 그는 계산가능한 수 (computable number) 라고 하는 것은 n 이 주어졌을 때 n 번째 숫자를 계산하는 알고리즘이 있는 실수라고 정의했다 (a real number for which there is an algorithm that, given n, calculates the nth digit). 그는 거의 모든 수는 계산불가능 (uncomputable) 하다고 증명했다. Chaitins constant 는 비록 잘 정의되었더라도 계산불가능한 수이다.
어떤 다른 시스템이 Turing machine 과 동등한가?
Turing machine 에 의해 받아들여진 언어는 formal grammars 에 의해 생성된 바로 그것이다. Lambda calculus 는 함수를 정의하는 한 방법이다. Lambda calculus 로 계산될 수 있는 함수는 Turing machine 에 의해 계산될 수 있는 바로 그것이다. 3 가지 형식, 즉 Turing machine, formal grammars, lambda calculus 는 전부 매우 다른 것처럼 보이고, 다른 사람들이 개발한 것이다. 그러나 그것들은 전부 동등한 것이며 같은 문제해결 능력을 가진다. 이것은 대개 알고리즘이나 효율적인 과정에 대한 우리들의 직관적인 언급은 Turing machine 의 수학적 정의로 포착된다고 주장하는 처치-튜링 명제 (Church-Turing Thesis) 의 증거로서 취급된다.
만일 무제한 양의 메모리 접근이 가능하다면, 전자컴퓨터 심지어는 양자컴퓨터 (quantum computer) 조차도 Turing machine 과 정확히 동등하다. 결론적으로 모든 구현가능한 프로그래밍 언어들은 기껏해야 Turing machine 의 능력과 동등하다 (실제로는 능력이 떨어진다). 그러한 언어들은 Turing-complete 하다고 한다. Turing machine 과 동등한 시스템들은 다음과 같다 :
- 튜링 기계 (Turing Machine) with several tapes
- Turing machine with a 2-dimensional "tape" (an infinite number of linear tapes)
-
Turing machine with a limited number of states and tape symbols
- States×symbols can be any of 2×18, 3×10, 4×6, 5×5, 7×4, 10×3, 22×2
- Finite state machine with 2 stacks
- Finite state machine with 2 counters
- 형식 문법 (Formal Grammar)
- 포스트 시스템 (Post Systems)
- 람다 계산법 (Lambda Calculus)
- 재귀함수 (Recursive Function)
-
거의 모든 현대적인 프로그램 언어 (무제한의 메모리가 주어질때), 다음을 포함한다 :
- A language with 1 instruction, 1 (¿Isn't it 3 parameters?) parameter (see OISC and URISC here (link doesn't seem to go to the right place))
- A language with 8 instructions, no parameters (see BrainFuck)
- Wang tiles
- Recurrent neural network (finite-precision inputs/outputs/weights, infinite-precision signals initialized to zero)
-
세포 자동자 (Cellular Automata), 다음을 포함한다 :
- Conway's 생명 게임 (Game of Life)
- Cellular automaton with just 1 dimension, 2 states, 3 cells per neighborhood (e.g. rule 110)
- Non-deterministic Turing machine
- Probabilistic Turing Machine
- Quantum computer
마지막 세 개의 예는 언어를 받아들이는 (accepting) 다소 다른 정의를 사용한다. 즉 만일 어떤 (any) 계산이 non-deterministic 을 받아들이거나, 대부분의 (most) 계산이 probabilistic and quantum 을 받아들인다면 문자열 (string) 을 받아들인다고 할 수 있다. 이러한 정의가 주어진다면 이러한 기계들은 언어를 받아들이기 위한 Turing machine 과 같은 능력을 가진다.
어떤 문제들이 더 강력한 기계들을 필요로 하는가?
어떤 기계들은 Turing machine 보다 더 강력하다고 생각된다. 예를들면 oracle machine 은 통상의 Turing machine 에서는 가능하지 않은 특수한 함수를 계산할 수 있는 블랙박스를 사용한다. theory of real computation 은 infinite-precision real numbers 를 사용하는 기계를 다룬다. 이 이론에서는 "complement of the Mandelbrot set 은 부분적으로는 결정가능하다" 와 같은 흥미로운 문장을 증명하는 것이 가능하다 (hypercomputation).
어떤 문제들이 덜 강력한 기계로도 풀릴 수 있는가?
촘스키 계층 (Chomsky Hierarchy) 는 4 부류의 알고리즘으로 받아들일 수 있는 언어를 정의한다. 그들은 모두 기계가 어떤 형태의 메모리와 결합된 non-deterministic finite state machine 로 구성된다고 가정한다. 만일 메모리가 무한 테이프라면 Turing machine 은 full power 를 가지며, unrestricted grammars 에 의해 생성된 언어를 정확히 받아들일 수 있다. 만일 입력의 크기와 비례하는 메모리만 주어진다면, 문맥인식 문법 (Context Sensitive Grammar) 에 의해 생성된 언어를 정확히 인식할 수 있다. 만일 메모리로서 하나의 stack 만 주어진다면, 문맥자유 문법 (Context Free Grammar) 에 의해 생성된 언어를 정확히 인식할 수 있다. 만일 어떠한 추가의 메모리도 주어지지 않는다면 regular grammars 에 의해 생성된 언어를 정확히 받아들일 수 있다.
메모리나 시간, 또는 다른 자원에 대한 제약이 고려될 때가 있다. 이러한 제약의 결과는 computability theory 보다는 계산 복잡도 이론 (Computational Complexity Theory) 의 일부로서 보통 고려된다. .......... (Wikipedia : Computability Theory)
참고 학술 논문 및 웹 사이트 (원본 보존)
paper :
- 계산가능성과 심적과정 : Philip N. Johnson-Laird
- 해결이 불가능한 문제들 : Rudy Rucker
- 계산가능성과 논리 : George S. Boolos Richard C. Jeffrey
- 계산가능성 이론 형성에서의 Church's Thesis 와 Turing's Thesis : 현우식, 한국수학사학회, 1998
- 계산가능성과 전산적 마음 (Computability and Computable Mind) : 이영의, 고려대철학연구소, 1994