AI Study
1936년 앨런 튜링이 증명한 결정 불가능성(Undecidability)의 시초 — 왜 AI도 무한 루프와 안전성을 100% 사전 검증할 수 없는가

정지 문제 (Halting Problem)

정지 문제(Halting Problem) 는 어떤 프로그램과 입력값이 주어졌을 때, 이 프로그램이 유한한 시간 안에 작업을 끝내고 멈출지 아니면 무한 루프에 빠져 영원히 실행될지를 미리 판별할 수 있는 보편적인 알고리즘이 존재할 수 없다는 이론 컴퓨터 과학의 증명입니다. AI 역시 컴퓨터 알고리즘과 튜링 머신의 계산 모델을 기반으로 작동하므로, 아무리 지능이 뛰어나도 모든 경우에 대해 이 문제를 완벽하게 해결할 수는 없습니다.

정지 문제의 핵심 개념
  • 앨런 튜링의 증명. 1936년 수학자 앨런 튜링이 대각선 논법과 귀류법을 통해 증명했습니다. 모든 프로그램의 정지 여부를 판별하는 가상의 프로그램이 존재한다고 가정하면, 자기 자신을 입력으로 넣었을 때 예측과 반대로 행동하는 역설적인 프로그램을 만들 수 있어 논리적 모순이 발생합니다.
  • 계산 가능성의 한계. 이는 하드웨어 성능이나 코드가 부족해서가 아니라 논리적·수학적으로 결정 불가능한(Undecidable) 문제입니다. 프로그램을 직접 실행해 보지 않고 결과만 미리 100% 확신하는 만능 도구는 존재할 수 없습니다.
AI(인공지능) 에 미치는 영향과 한계
  • 초지능 AI 의 근본적 한계. 현재의 대규모 언어 모델(LLM)이나 미래의 범용 인공지능(AGI) 모두 현대 컴퓨터 아키텍처 위에서 돌아가는 소프트웨어입니다. 따라서 초지능 AI 가 등장하더라도 수학적으로 불가능한 정지 문제를 100% 정확도로 풀어내는 것은 원리상 불가능합니다.
  • AI 코드 생성 및 검증의 한계. AI가 작성한 코드나 인간이 짠 코드에 무한 루프나 치명적인 버그가 있는지 완벽하게 자동 검증(Formal Verification)하는 데 한계가 있습니다. 특정 조건이나 제한된 범위 내에서는 높은 확률로 오류를 잡아낼 수 있지만, 세상의 모든 프로그램에 적용되는 완벽한 검증기는 만들 수 없습니다.
  • 자율 에이전트의 무한 루프 위험. 스스로 목표를 세우고 도구를 사용하는 AI 에이전트(Autonomous Agent) 가 작업을 수행할 때, 목표를 달성하지 못하고 같은 행동을 무한히 반복할지 사전에 완벽히 예측하기 어렵습니다. 이 때문에 실제 AI 시스템에서는 논리적 판별 대신 최대 실행 시간(Timeout) 이나 최대 반복 횟수(Max Iterations) 를 강제로 제한하는 현실적인 우회 방식을 사용합니다.
AI의 실용적 우회 전략
  • 휴리스틱과 확률적 추론. AI는 100% 완벽한 논리적 증명 대신, 방대한 데이터 학습을 통해 특정 코드나 작업이 멈출 가능성을 높은 확률로 예측하는 근사치(Approximation) 방식을 취합니다.
  • 외부 제약 조건 설정. 라이스의 정리 와 연결되는 개념으로, 시스템 내부의 논리적 고립만으로는 종료 여부를 알 수 없으므로 외부에서 실행 자원(토큰 한도, 연산 시간 등)을 통제하여 강제로 정지시키는 안전장치를 둡니다.

정지 문제(Halting Problem, 멈춤문제)는 "임의의 프로그램(또는 AI 알고리즘) P와 입력 I가 주어졌을 때, 실행을 끝까지 지켜보지 않고도 P가 유한 시간 내에 멈출지 영원히 무한 루프를 돌지 100% 판별해 주는 만능 알고리즘이 존재하는가?"를 묻는 문제입니다. 1936년 앨런 튜링이 "그러한 보편 판별기는 존재 불가능하다(Undecidable)"고 증명한 이 정리는 오늘날 LLM 추론 루프, 자율 코딩 에이전트 검증, 그리고 AI 안전성(AI Safety) 설계의 절대적 한계를 규정합니다.

SECTION 01

Halting Problem의 개념, 대각화 증명, 그리고 3대 핵심 의미

프로그래머라면 누구나 코드가 무한 루프에 빠져 멈추지 않을 때 "실행하기 전에 버그를 자동으로 잡아주는 완벽한 검사기"를 꿈꿉니다. 하지만 튜링은 칸토어(Cantor)의 대각화(Diagonalization) 기법을 이용한 우아한 귀류법으로 모든 프로그램과 모든 입력에 대해 정지 여부를 완벽히 판정하는 단일 알고리즘 H(P, I)는 논리적 자기모순 때문에 존재할 수 없음을 증명했습니다.

원리 ① · 대각화 모순 증명

만약 판별기 H가 있다면 스스로를 부정한다

정지 판별기 H(P, I)가 존재한다고 가정하고, 이를 반대로 뒤집는 훼방 기계 D(M)을 만듭니다: "H(M, M)이 정지라 답하면 무한 루프를 돌고, 무한 루프라 답하면 즉시 정지한다." 이제 D에게 자기 자신 D를 입력으로 넣으면(D(D)) "정지하면 무한 루프, 무한 루프면 정지"라는 모순에 빠져 H의 존재 자체가 붕괴합니다.

원리 ② · 라이스 정리 & 차이틴 상수

"무엇을 하는 코드인지" 보편 판별도 불가

라이스 정리(Rice's Theorem)는 정지 문제를 일반화하여 "임의의 프로그램이 계산하는 함수의 비자명한 의미적 성질(예: 0을 출력하는가? 보안 취약점이 없는가?)을 100% 자동 판별하는 것 역시 결정 불가능"함을 보입니다. 또한 차이틴의 정지 확률(Ω)은 정지 문제가 정보이론적 무작위성과 맞닿아 있음을 보여줍니다.

원리 ③ · 유한 경계와의 결정적 차이

"100 스텝 내 정지"와 유한 메모리는 풀린다!

정지 문제의 불가능성은 '무제한 시간 · 무한 메모리'를 전제합니다. 원전 해설에서 짚듯이 "100 스텝(유한 단계) 이내에 멈추는가?"나 엄격한 유한 메모리 기계는 직접 실행해 보거나 상태 재방문을 검사함으로써 100% 판별 가능(Decidable)합니다. 이것이 AI 에이전트에 횟수 제한을 두는 이유입니다.

INFOGRAPHIC 01 · 튜링의 정지 문제 귀류법(D(D) 역설) & 파생 정리 계보 왜 보편적 정지 판별 알고리즘이 논리적으로 모순을 일으키는지 한눈에 이해하기
정지 문제 (Halting Problem) : 대각화 모순 증명과 결정 불가능 계보 "만능 정지 판별기 H(P, I)가 존재한다고 가정하면, 자기 자신을 입력으로 넣는 순간 논리 모순 폭발!" 튜링의 귀류법 (1936) : 반례 프로그램 D(M)의 자기 참조 모순 가정 : 만능 판별기 H(P, I) 항상 유한 시간 내 정답 출력: [정지(Halt)] 또는 [무한루프(Loop)] 훼방 기계 D(M) 구성 • H(M, M) == Halt 이면 ➔ 무한 루프! • H(M, M) == Loop 이면 ➔ 즉시 정지! 치명적 대각화 호출 : D 자신에게 자기 코드 D를 입력 ➔ D(D) 경우 ① H(D, D) = "정지" 판별기는 D(D)가 멈춘다 했으나, D 규칙상 오히려 무한 루프 진입! (모순) 경우 ② H(D, D) = "무한 루프" 판별기는 영원히 돈다 했으나, D 규칙상 오히려 즉시 정지! (모순) 결론 : 모든 경우를 해결하는 보편 알고리즘 H(P, I)는 존재 불가능! (개별 프로그램 증명이나 '100스텝 내 정지' 같은 유한 경계 판정은 예외적으로 가능) 정지 문제에서 파생된 결정 불가 계보 1. 판정문제 (Entscheidungsproblem) 일차 술어논리 명제의 참/거짓 보편 판별 불가 (힐베르트 프로그램 불가능 증명 · 1936) 2. 라이스 정리 (Rice's Theorem) 정지 문제뿐 아니라 코드의 모든 비자명한 의미적 성질 (버그 없음 · 보안 무결성 · AI 유해행위) 사전 판별 불가 3. 차이틴 상수 Ω (Halting Probability) 무작위 프로그램이 정지할 확률 Ω 는 수학적으로 실재하나 어떤 알고리즘으로도 자릿수를 계산할 수 없음(비계산 수) 새로운 문제의 결정 불가능 증명 공식 : "그 문제가 풀리면 정지문제도 풀린다" ➔ 환원 증명!
SECTION 02 · DEEP RESEARCH

AI와 LLM에서 Halting Problem이 가지는 5대 심층 의미

과거 정지 문제는 컴파일러나 프로그램 검증 이론가의 고민이었으나, 오늘날 스스로 생각의 사슬(CoT)을 뻗어가고, 코드를 생성·실행하며, 다른 서브에이전트를 호출하는 자율 AI·LLM 시대에 들어서면서 정지 문제는 가장 현실적인 시스템 장애·보안·안전성 이슈로 부활했습니다.

심층 분석 01 · 추론 LLM의 EOS/종료 불확실성

CoT · <think> 추론 루프는 언제 멈추는가? (Overthinking & 반복 퇴화)

OpenAI o1/o3나 DeepSeek-R1 같은 추론형 LLM은 최종 답을 내놓기 전 스스로 <think>...</think> 블록 안에서 수천~수만 토큰의 추론을 반복합니다. 이때 모델이 스스로 종료 토큰(EOS / </think>)을 출력할지, 아니면 풀리지 않는 논리적 궤도를 빙빙 도는 무한 반복 퇴화(Repetition Degeneration / Overthinking Loop)에 빠질지는 입력 프롬프트를 보기 전엔 완벽히 예측할 수 없습니다. 즉 LLM의 자기회귀 추론 종료 여부 자체가 정지 문제의 현대적 변주입니다.

심층 분석 02 · 코딩 에이전트 검증 한계

AI 생성 코드의 버그 · 무한루프 100% 정적 판별 불가 (라이스 정리)

AI 코딩 에이전트가 작성한 Python/C++/JS 코드가 임의의 사용자 입력을 받았을 때 "절대 무한 루프나 데드락에 빠지지 않는가?", "숨은 메모리 누수나 보안 백도어가 없는가?"를 실행 전 정적 분석기나 또 다른 감시 LLM만으로 100% 정확하게 판별하는 것은 정지 문제와 라이스 정리(Rice's Theorem)에 의해 수학적으로 불가능합니다. 따라서 정적 AI 코드 리뷰는 언제나 근사 보조 수단이며, 반드시 격리된 실행 테스트가 뒤따라야 합니다.

심층 분석 03 · AI 안전성(AI Safety)의 근본 벽

"탈옥 · 악성 행위 제로(0%) 보편 감시 AI"가 존재할 수 없는 이유

만약 초거대 에이전트 M과 상호작용 프롬프트 P가 주어졌을 때 "이 AI가 미래 어느 스텝에서든 위험한 행위 B를 절대 실행하지 않는다"고 100% 사전 보장하는 또 다른 감시 AI G(M, P)를 만들 수 있다면, 이는 사실상 임의의 튜링 완전 에이전트가 특정 상태(정지/위험 상태)에 도달하는지 판별하는 정지 문제를 푸는 것과 같습니다. 이 이론적 장벽 때문에 AI 정렬(Alignment) 연구는 완벽한 단일 필터가 아닌 다층 방어(Defense-in-Depth)와 권한 최소화를 원칙으로 삼습니다.

심층 분석 04 · 공학적 해법 : Bounded Halting

무한 정지 문제를 결정 가능한 '유한 경계 문제(Bounded Halting)'로 전환

원전 아카이브 마지막 문단이 강조하듯, "유한 메모리 · 유한 스텝(예: 100 스텝 내 정지)"으로 범위를 좁히면 정지 문제는 결정 가능(Decidable)해집니다. 현대 LLM 서빙과 에이전트 런타임은 이 원리를 그대로 구현합니다: ① max_tokens로 생성 길이 상한을 고정하고, ② max_turns · wall_clock_timeout으로 도구 루프를 강제 종료하며, ③ 해시 기반 반복 감지(Cycle Detection)와 Context Compaction으로 유한 상태 공간 내 안전 종료를 보장합니다.

심층 분석 05 · 프로그램 합성 · 적응형 계산(ACT)

Adaptive Computation Time(ACT) · Pondering · AIXI의 한계

신경망이 입력 난이도에 따라 스스로 계산 루프 횟수를 동적으로 결정해 정지하는 기법(Graves의 Adaptive Computation Time, PonderNet, Universal Transformer) 역시 정지 신호(Halting Probability Unit)를 학습합니다. 또한 이상적 초지능 수학 모델 AIXI에서 최적 프로그램 탐색과 차이틴 상수 Ω가 비계산 가능한 근본 이유 역시 정지 문제에 뿌리를 두고 있어, 현실 AI는 학습 가능한 유한 중단 임계값(Learned Halting Threshold)으로 타협합니다.

INFOGRAPHIC 02 · LLM · AI 에이전트의 정지 문제 리스크 ➔ 유한 경계(Bounded Engineering) 해법 무제한 자율 AI가 정지 문제 함정에 빠지는 지점과 현대 엔지니어링 제어 장치 매핑
AI · LLM에서의 정지 문제 : 4대 위기와 유한 경계(Bounded) 엔지니어링 "무제한 루프 = 결정 불가능(Undecidable) ➔ Max Tokens · Max Turns · Sandbox = 결정 가능한 유한 제어" ① 추론 LLM (<think>) : 무한 사고 루프 리스크 • 위험: CoT 중 EOS(종료 토큰) 미생성 시 반복 퇴화 · 비용 폭발 • 이론: 자유 추론 길이의 수렴 여부는 사전 보장 불가 공학 해법 ➔ max_reasoning_tokens & Repetition Penalty ➔ Adaptive Halting (ACT/PonderNet) 확률 임계치 도달 시 강제 출력 ② 자율 에이전트 툴 루프 : 순환 호출 정지 불가 • 위험: Agent A ⇄ Tool / Subagent B 간 무한 재시도 고리 • 이론: 도구 호출 + 메모리 기록 = 튜링 완전(정지 문제 노출) 공학 해법 ➔ Bounded Halting (Max Turns = N 상한 고정) ➔ 상태 해시 기반 순환 탐지(Cycle Detector) & 토큰 예산 차단기 ③ AI 생성 코드 · 라이스 정리 : 정적 검증의 한계 • 위험: AI가 짠 코드의 무한루프·런타임 버그 사전 100% 탐지 불가 • 이론: 라이스 정리(Rice's Theorem)에 의한 원리적 결정 불가 공학 해법 ➔ 격리 컨테이너(Docker/E2B) + Wall-Clock Timeout ➔ 실행 후 단위 테스트(P-검증)로 경험적 신뢰성 확보 ④ AI 안전성 · 정렬(Alignment) : 보편 필터 부재 • 위험: "모든 미래 입력에 안전한가"를 판정할 단일 감시 AI 없음 • 원인: 감시 AI 자기 참조 시 튜링 대각화 역설 발생 가능 공학 해법 ➔ 최소 권한 원칙(Least Privilege) & 다층 가드레일 ➔ 고위험 액션 전 Human-in-the-Loop(HITL) 승인 게이트 배치
SECTION 03 · FOR AI ENGINEERS

AI 개발자들에게 Halting Problem이 가지는 5대 실무 의미

에이전트 루프, 코딩 어시스턴트, RAG 워크플로우를 구축하는 현업 AI 개발자에게 정지 문제는 가장 먼저 방어해야 할 프로덕션 생존 수칙 5가지로 직결됩니다.

실무 수칙 01

모든 에이전트 루프에 max_turns · 예산 상한 하드코딩

"모델이 알아서 DONE을 외칠 것"이라 믿고 while True: 에이전트 루프를 돌리면 API 과금 폭탄과 무한 루프를 피할 수 없습니다. 유한 스텝(Bounded Halting)만이 정지 문제를 결정 가능하게 만듭니다.

실무 수칙 02

AI 생성 코드 정적 맹신 금지 ➔ 샌드박스 + 타임아웃

라이스 정리상 AI 코드의 무결성과 종료 여부를 정적으로 완벽 검증할 수 없습니다. AI가 짠 코드는 반드시 CPU·메모리·시간이 제한된 컨테이너 샌드박스(Docker/Wasm) 안에서 실행 검증하세요.

실무 수칙 03

반복 실패 탐지(Cycle & Repetition Detection) 구현

에이전트가 동일한 에러를 3회 이상 반복하거나 같은 툴 호출 인자를 되풀이할 때, 강제로 루프를 중단하고 다른 전략(Fallback)이나 사용자 질문으로 전환하는 순환 탐지기가 필수입니다.

실무 수칙 04

완벽한 단일 감시 필터 대신 다층 안전망 설계

만능 가드레일 AI 하나로 모든 탈옥과 오작동을 100% 차단하려는 시도는 정지 문제에 부딪힙니다. 입력 검증 + 최소 권한 API + 출력 스키마 강제 + HITL 승인의 다층 방어가 정답입니다.

실무 수칙 05

"특수 인스턴스 증명 가능성" 활용: 단계별 체크포인트 & 상태 머신(FSM)

원전 아카이브가 말하듯 일반 프로그램의 정지는 풀 수 없지만, 특정 구조로 제한된 프로그램(예: DAG 워크플로우, 유한 상태 머신 FSM)은 정지가 보장됩니다. AI 개발자는 꼭 필요한 구간 외에는 무제한 자유 루프보다 **DAG / 명시적 상태 전이(LangGraph 등)**로 워크플로우를 제한해 종료성과 예측성을 확보해야 합니다.

SECTION 04 · ARCHIVE PRESERVATION

원전 해설 및 라이스 정리·유한 메모리 단서 아카이브 (원본 보존)

유한한 수의 단계 후에 특정한 프로그램이 멈출 것이라고 (문제가 풀릴것이라고) 우리에게 미리 말해줄 수 있는 어떤 일반적인 절차 (알고리듬) 가 있는가? 달리 말하면, 어떤 주어진 튜링기계 (Turing Machine) 프로그램 P 와 입력 자료들의 집합 I 에 대해서, P 와 I 를 받아들인 다음에 자료 I 를 처리할 때 P 가 유한한 수의 단계 후에 멈출 것인지의 여부를 우리에게 말해줄 수 있는 어떤 단일한 프로그램이 있는가? 이때 우리가 문제삼는 것이 모든 경우에 작동할 어떤 단일한 프로그램이라는 것을 주목하라. 바로 이것이 그 유명한 멈춤문제 (Halting Problem) 다.

...... 실제 프로그램에 대한 멈춤 규칙은 대개 "만일 이런저건 조건을 만족하는 그러그러한 값이 나오면 멈춰라. 그렇지 않으면 계속해서 계산하라" 와 같이 말하는, 앞에서 제시된 것과 종류가 같은 암묵적인 규칙이다. 멈춤문제에서 핵심적인 것은 프로그램의 멈춤 조건이 만족될 것이냐의 여부를 미리 말해주기 위해 그 프로그램과 입력자료들에 적용될 수 있는 어떤 효과적인 절차가 존재하느냐 하는 물음이다. 1936 년에 Alan Turing 은 이 문제를 일거에 부정적으로 해결했다. 즉 주어진 프로그램 P 와 입력자료 집합 I 에 대해서, P 가 입력 I 를 처리하는 것을 끝낼지의 여부를 말해주는 어떤 일반적인 방법도 없다는 것이다.

튜링 기계라는 개념은 결국 계산이라는 생각을 견고한 수학적 토대 위에 올려놓았으며, 우리로 하여금 효과적 (effective) 절차라는 모호하고 직관적인 생각에서 알고리듬이라는 정확하고 수학적으로 잘 정의된 개념으로 나아가게 했다 ..... (John Casti 2000)

정지문제는 비공식적으로 다음과 같이 묘사할 수 있는 판정문제 (Entscheidungsproblem) 이다.

"하나의 알고리즘과 초기 인수들이 주어졌을 때, 주어진 인수로서 수행되는 알고리즘 (Algorithm) 이 정지되는지, 정지하지 않고 영원히 수행되는지를 결정한다"

Alan Turing 은 1936 년에 모든 가능한 입력에 대해 정지문제를 해결할 수 있는 일반적인 방법이나 알고리즘은 없다는 것을 증명했다. 정지문제가 중요한 이유는 그것이 결정불가능성 (undecidable)을 증명하는 최초의 문제였다는 사실이다. 계속해서 많은 다른 문제들이 다루어졌으며, 결정불가능성인 문제를 증명하는 전형적인 방법은 그것을 정지문제로 축소시키는 것이다.

정지문제의 결정불가능성에 대한 결과는 판정문제 (Entscheidungsproblem) 가 해결될 수 없으며, 특히 자연수에 대한 어떤 문장이 참인지 거짓인지를 결정하는 일반적인 알고리즘은 있을 수 없다는 것이다. 그 이유는 어떤 알고리즘이 어떤 입력이 주어졌을 때 멈출 것이라고 진술하는 명제는 수에 관한 문장으로 자동적으로 다시 공식화할 수 있다는 것 때문이다. 즉 알고리즘에 관한 원래의 문장이 참인지 거짓인지 결정할 수 있는 알고리즘은 없기 때문에, 수에 관한 동등한 문장이 참인지 거짓인지 결정할 수 있는 알고리즘은 없다는 것이다.

그러나 정지문제의 결정불가능성에 관한 아주 놀라운 또다른 결과는, 알고리즘으로 정의되는 함수에 대한 어떤 중요한 (non-trivial) 문장의 진리여부는 결정될 수 없다는 Rice's theorem 이다. 예를들면, "이 알고리즘은 0 이 입력되면 멈출 것이다" 라는 결정문제는 이미 결정불가능하다. 이 정리는 알고리즘 그 자체가 아니라 알고리즘에 의해 정의된 함수를 가지고 있다는 것을 주목하라. 예를들면 어떤 알고리즘이 100 step 이내에 멈출 것인지를 결정하는 것은 가능하지만, 그러나 이것은 알고리즘에 의해 정의된 함수에 대한 문장이 아니다. ......

Gregory Chaitin 는 정지문제에 의존하지 않는 algorithmic information theory 에 관한 결정불가능 문제를 제시했다. 그는 임의로 만들어진 프로그램이 정지할 확률을 표현하는 halting probability 의 흥미로운 정의를 제시했다.

튜링의 정리가 알고리즘이 멈추는 지를 결정할 일반적인 방법이나 알고리즘이 있을 수 없다는 것을 보여주는 반면에, 개별 프로그램의 경우에는 공격에 매우 민감할 수 있다 (individual instances of that problem may very well be susceptible to attack). 특별한 알고리즘이 주어졌을 때, 어떤 입력일 경우에 그것이 멈춰야하는 지를 보일 수 있다. 그러나 사실 컴퓨터과학자는 하나의 correctness proof 의 부분으로서만 그것을 수행한다. 그러나 모든 그런 증명은, "알고리즘이 멈추는 지를 결정하는 mechanical, general way 가 없다" 는 새로운 추론을 요구한다.

또다른 경고가 있다. 정지문제의 결정불가능성은 알고리즘이 아마도 무한의 저장장치를 가진다고 가정한다는 사실이다. 어느 한순간에는 유한한 것들을 저장할 수 있지만, 그것은 항상 더 많은 것을 저장하고 결코 메모리를 초과하지 않는다. 만일 기계의 메모리와 외부 저장장치가 유한하다면, 그것은 실제로 존재하는 컴퓨터에 대한 것이고, 따라서 기계상에서 작동하는 프로그램에 대한 정지문제는 일반 알고리즘으로 해결될 수 있다 (비록 극히 비효율적인 것이지만). .............. (Wikipedia : Halting problem)

SECTION 05 · TERMS, PAPERS & VIDEOS

관련 용어 · 학술 논문 · 동영상 강의 (원본 보존)

paper :

멈춤문제 (halting problem) : John Casti. Werner De Pauli

video :

Proof That Computers Can't Do Everything (The Halting Problem) : 2013/09/27
Turing & The Halting Problem - Computerphile : 2014/08/21