AI Study
튜링·처치·촘스키·쿡이 정립한 컴퓨터 과학의 최상위 이론 — 추상 기계와 복잡도에서 최신 AI·LLM 추론 원리까지

계산 이론 (Theory of Computation)

계산 이론(Theory of Computation) 은 컴퓨터가 문제를 효율적으로 풀 수 있는 원리와 한계를 수학적으로 탐구하는 학문이자, 현대 인공지능(AI) 의 수학적 토대와 한계를 규정하는 핵심 기반입니다.
AI 관점에서 계산 이론은 크게 세 가지 핵심 영역으로 나뉘어 AI 의 작동 방식과 가능성을 결정합니다.

1. 오토마타 이론 (Automata Theory): AI 의 추론과 패턴 인식 기초

오토마타는 추상적인 기계 모델과 이들이 처리할 수 있는 형식 언어(Formal Languages) 를 다룹니다.

  • 초기 AI 와 자연어 처리(NLP): 초기 AI 의 구문 분석(Parsing)과 음성 인식은 유한 상태 기계(FSM) 나 문맥 자유 문법(CFG) 같은 오토마타 모델에 직접적으로 기반을 두었습니다.
  • 현대 딥러닝과의 연결: 최근의 순환 신경망(RNN) 이나 트랜스포머(Transformer) 모델이 인간의 언어나 복잡한 규칙을 얼마나 정확히 학습하고 일반화할 수 있는지 분석할 때 오토마타 이론이 기준점이 됩니다.
2. 계산 가능성 이론 (Computability Theory): AI가 할 수 없는 것의 경계

앨런 튜링(Alan Turing) 의 튜링 기계(Turing Machine) 를 중심으로, 어떤 문제가 알고리즘적으로 '해결 가능한지(Decidable)' 아니면 '불가능한지(Undecidable)' 를 다룹니다.

  • AI 능력의 근본적 한계: 현대의 모든 AI는 결국 튜링 기계 위에서 돌아가는 프로그램입니다. 따라서 정지 문제(Halting Problem) 처럼 튜링 기계로 풀 수 없는 문제는 AI 가 아무리 발전해도 완벽하게 해결할 수 없습니다.
  • AI 안전성과 정렬(Alignment): 특정 AI 모델이 절대 해로운 행동을 하지 않을 것인지 수학적으로 완벽히 검증하는 문제는 종종 '계산 불가능(Undecidable)' 한 영역에 속하며, 이는 AI 안전성 연구의 중요한 난제입니다.
3. 계산 복잡도 이론 (Computational Complexity Theory): AI 의 현실적 비용과 한계

문제를 풀 수 있더라도, 얼마나 많은 시간(Time) 과 메모리(Space) 가 필요한지를 분석하는 분야입니다. (예: P vs NP 문제)

  • 학습과 추론의 난이도: 신경망의 가중치를 최적화하거나 완벽한 추론을 수행하는 많은 AI 문제는 수학적으로 NP-난해(NP-Hard) 에 속합니다. 이는 데이터의 크기가 커질수록 완벽한 해답을 찾는 데 우주의 나이보다 긴 시간이 걸릴 수 있음을 의미합니다.
  • 근사 알고리즘과 휴리스틱의 탄생: 계산 복잡도 이론 덕분에 AI 연구자들은 "완벽한 정답" 대신, 현실적인 시간 안에 "충분히 좋은 정답"을 찾는 경사 하강법(Gradient Descent), 휴리스틱 탐색, 근사 추론(Approximate Inference) 기법을 발전시켰습니다.
요약

AI에게 계산 이론이란 "무엇을 배울 수 있는가(오토마타)", "무엇이 원리적으로 불가능한가(계산 가능성)", 그리고 "현실적인 시간 안에 감당할 수 있는가(계산 복잡도)" 를 알려주는 나침반이자 설계도입니다.

계산이론(Theory of Computation)은 "컴퓨터와 추상 기계가 어떤 문제를 해결할 수 있는가(계산가능성)", "어떤 형식 규칙으로 언어를 표현할 수 있는가(오토마타)", 그리고 "얼마나 적은 시간과 메모리로 문제를 풀 수 있는가(복잡도)"를 수학적으로 탐구하는 학문입니다. 현대 AI와 대규모 언어 모델(LLM)의 표현력 한계, CoT 추론의 위력, 문법 기반 디코딩, 테스트 타임 컴퓨트(Test-Time Compute)의 원리가 모두 계산이론 위에서 설계·분석됩니다.

SECTION 01

Theory of Computation의 개념과 3대 핵심 기둥

전자 컴퓨터가 실제로 발명되기도 전인 20세기 초반, 힐베르트·괴델·처치·튜링·클리니 등의 수리논리학자들은 "기계적이고 단순한 방법(알고리즘)으로 해결 가능한 수학 문제의 범위는 어디까지인가?"를 묻기 시작했습니다. 여기서 출발한 계산이론(Theory of Computation)은 오늘날 다음 3가지 상호 연결된 핵심 축으로 구성됩니다.

제1기둥 · 구조와 언어

오토마타 & 형식언어 이론
(Automata & Formal Languages)

메모리 제약에 따라 추상 기계가 인식할 수 있는 형식언어의 등급을 분류합니다. 유한 상태 기계(FSM · 정규표현식)에서 스택을 추가한 푸시다운 오토마타(PDA · 문맥자유문법), 선형 유계 오토마타(LBA · 문맥의존문법), 그리고 무한 테이프를 가진 튜링 기계로 이어지는 촘스키 계층(Chomsky Hierarchy)을 다룹니다.

제2기둥 · 가능성과 한계

계산가능성 이론
(Computability Theory)

"이 문제를 푸는 알고리즘이 아예 존재하는가?"를 연구합니다. 튜링 기계, 재귀함수, 람다 계산법, 마르코프 알고리즘, 포스트 시스템이 계산 능력 면에서 완벽히 동등하다는 처치-튜링 명제를 토대로 결정 가능(Decidable) vs 결정 불가능(Undecidable, 예: 정지 문제)의 절대 경계를 증명합니다.

제3기둥 · 시간과 메모리 효율

계산복잡도 이론
(Computational Complexity Theory)

이론적으로 풀 수 있는(Decidable) 문제라도 우주의 수명보다 오래 걸린다면 무용지물입니다. 입력 크기 N에 대해 필요한 시간·공간 자원에 따라 P(다항 시간 해결), NP(다항 시간 검증), NP-complete, PSPACE, EXPTIME, 병렬 부류 NC, 확률 부류 BPP, 양자 부류 BQP 등으로 난이도 지도를 그립니다.

INFOGRAPHIC 01 · 계산이론 3대 기둥 & 계층 통합 다이어그램 좌우로 스크롤하여 상세 계층 관계를 확인하세요 (모바일 대응)
Theory of Computation : 3대 핵심 기둥과 추상 기계 · 복잡도 통합 계층 "기계가 인식할 수 있는 언어(Automata) ➔ 풀 수 있는 문제(Computability) ➔ 효율적 자원 한계(Complexity)" 처치-튜링 명제 (Church-Turing Thesis) : 알고리즘적 계산 가능성의 보편적 동치성 튜링 기계 (Turing Machine) ≡ 재귀함수 (Recursive Function) ≡ 람다 계산법 (λ-Calculus) ≡ 마르코프 알고리즘 ≡ 포스트 시스템 1. 오토마타 & 촘스키 계층 Type 0 · 무제한 문법 (Turing Machine) 무한 테이프(R/W) · 범용 컴퓨터 · 정지 문제 포함 Type 1 · 문맥의존문법 (LBA) 입력 길이 비례 유한 테이프 · 항상 정지 판별 Type 2 · 문맥자유문법 (PDA) 스택(Stack) 1개 · 중첩 괄호 · 컴파일러/JSON Type 3 · 정규문법 (FSM) 유한 상태만 기억 · 정규표현식(Regex) 2. 계산가능성 경계 (Computability) 결정 불가능 (Undecidable) • 정지 문제 (Halting Problem) • 라이스 정리(Rice's) · 포스트 대응 문제 반결정 가능 (RE / Type 0) "예(Yes)"일 때는 멈추나 "아니오"면 무한 루프 가능 결정 가능 (Decidable / Recursive) 모든 입력에 대해 유한 시간 내 반드시 정지 Type 1 · Type 2 · Type 3 및 모든 실제 알고리즘 ➔ 이후 '효율성' 여부에 따라 복잡도 이론으로 분기 3. 계산복잡도 계층 (Complexity) EXPSPACE / EXPTIME 지수 자원 필요 (체스 일반화 · Presburger 산술) PSPACE / PSPACE-Complete 다항 메모리 · QBF · 게임 트리 완전 탐색 NP / NP-Complete / BQP(양자) 해답 검증은 빠름(P) · 탐색은 조합 폭발 (SAT 등) BQP: 소인수분해(쇼어) 등 양자 다항 시간 P / NC / TC⁰ (현실적 효율 연산) P: 다항 시간 해결 · NC/TC⁰: 초고속 병렬 회로
SECTION 02 · DEEP RESEARCH

AI와 LLM에서 Theory of Computation이 중요한 5대 이유

과거에는 계산이론이 컴파일러나 암호학의 기초로만 여겨졌으나, 오늘날 대규모 언어 모델(LLM)과 추론형 AI(Reasoning Models) 시대에 들어서면서 계산이론은 "트랜스포머가 본질적으로 무엇을 계산할 수 있고 무엇을 못 하는가", "왜 생각의 사슬(CoT)이 AI 지능을 도약시키는가", "왜 검증이 생성보다 쉬운가"를 규명하는 가장 강력한 설계 나침반이 되었습니다.

핵심 원리 01

단일 패스 트랜스포머의 회로 복잡도 한계 (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) 등으로 극복하는 시도 역시 오토마타 상태 압축과 복잡도 이론의 직접적 성과입니다.

핵심 원리 02

유한 오토마타(FSM) & 문맥자유문법(CFG) 기반 LLM 구조화 출력 제어

LLM은 본질적으로 어휘 사전 전체에 대한 확률 분포를 계산하는 통계적 모델이므로, 자유롭게 텍스트를 생성하면 JSON 닫는 괄호를 빠뜨리거나 SQL 구문 오류, 존재하지 않는 API 파라미터를 출력할 위험이 상존합니다.

이를 해결하기 위해 최신 AI 추론 엔진(Outlines, vLLM, Guidance, llama.cpp GBNF 등)은 촘스키 계층의 형식언어·오토마타 이론을 디코더 단계에 직접 이식합니다. JSON Schema는 결정적 유한 오토마타(DFA)로, 프로그래밍 언어 AST나 복잡한 중첩 수식은 문맥자유문법(CFG) 및 푸시다운 오토마타(PDA)로 컴파일한 뒤, 매 토큰 샘플링 직전에 현재 오토마타 상태에서 전이가 불가능한 토큰들의 로짓(Logit)을 음의 무한대(-∞)로 마스킹하는 제약 디코딩(Constrained Decoding)을 수행하여 100% 문법 무결성을 보장합니다.

핵심 원리 03

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)을 수행함으로써 단일 순전파 한계를 뛰어넘는 추론 성능을 달성했습니다.

핵심 원리 04

정지 문제(Halting Problem) · 라이스 정리와 AI 안전성 · 자율 에이전트 통제

자율 AI 코딩 에이전트가 생성한 소프트웨어, 혹은 에이전트 자신이 다른 에이전트를 호출하며 실행하는 워크플로우에 대해 "이 AI 코드가 무한 루프에 빠지지 않고 반드시 정지하는가?", "악의적 프롬프트 인젝션이나 치명적 보안 결함을 절대 유발하지 않는가?"를 100% 완벽하게 판별할 수 있을까요?

계산가능성 이론의 튜링 정지 문제(Halting Problem)와 이를 모든 비자명한 의미적 성질로 일반화한 라이스 정리(Rice's Theorem)는 튜링 완전한 프로그램의 동작 성질을 보편적·완전 자동으로 판별하는 알고리즘은 수학적으로 존재 불가능함(Undecidable)을 엄밀히 증명합니다. 따라서 현대 AI 안전성(AI Safety) 설계는 불가능한 "100% 정적 완벽 필터링"에만 의존하지 않고, 실행 스텝 상한(Max Tokens / Timeout), 샌드박스 격리, 권한 최소화, 휴먼-인-더-루프(HITL) 같은 유한 자원 경계와 다층 방어를 필수 원칙으로 삼습니다.

핵심 원리 05

병렬 복잡도(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 가속 탐색
INFOGRAPHIC 02 · Theory of Computation ➔ 현대 AI · LLM 추론 연결 지도 계산이론이 LLM의 내부 병목·구조화 출력·추론·안전성을 지배하는 구조
왜 계산이론이 AI와 LLM을 지배하는가? : 4대 아키텍처 매핑 회로 복잡도(TC⁰) → CoT 튜링 확장 | 오토마타(DFA/PDA) → 구조화 디코딩 | NP 검증 → Test-Time 추론 | 정지문제 → 안전 경계 ① 표현력 도약 : 1-Pass (TC⁰) vs Chain-of-Thought (튜링 확장) 단일 순전파 (1-Pass) 복잡도 한계 : TC⁰ 고정 깊이 어텐션 장기 상태 추적·패리티 실패 직관적 빠른 응답 (System 1) CoT 중간 토큰 루프 (CoT) P 시간 / 튜링 기계 에뮬레이션 컨텍스트 = 무한 테이프 역할 다단계 산술·추론 정밀 해결 깊은 숙고 추론 (System 2) ② 형식언어 · 오토마타 제어 : Constrained Decoding LLM 로짓 출력 확률적 토큰 후보 P(w₁), P(w₂)... 문법 오류 위험 존재 DFA / PDA 마스크 Regex → DFA CFG → PDA 위반 토큰 Logit = -∞ 100% 무결 구조화 출력 JSON · SQL Tool Call ③ P vs NP 비대칭 활용 : 생성 탐색 + 다항 시간 검증 해답 생성 (Generator) 탐색 공간이 지수적(NP-성격) Test-Time Compute를 투입해 다수의 후보 해답·증명 트리 생성 (o1/o3 · DeepSeek-R1 · MCTS) 형식 검증 (P Verifier) 검증은 다항 시간(P) 내 확정 • Lean 4 수학 증명 검사 (AlphaProof) • 컴파일러/유닛 테스트 (RLVR) ➔ 검증 보상 통한 자가 강화 ④ 계산 불가능성 경계 : 정지 문제 · 라이스 정리 & AI 안전성 이론적 절대 한계 증명 정지 문제 & 라이스 정리 임의 AI 생성 코드·에이전트의 무한루프·위험 행위 여부를 100% 사전 정적 판별하는 알고리즘 불가 AI 엔지니어링 방어선 • 스텝 / 토큰 타임아웃 상한 • 컨테이너·샌드박스 격리 • 권한 제한 및 HITL 승인 ➔ 유한 자원 내 안전 확보
SECTION 03 · ARCHIVE PRESERVATION

원전 해설 및 계산·언어·복잡도 분류표 (원본 보존)

계산이론 (Theory of Computation) 은 컴퓨터과학의 한 분야로, 어떤 문제를 컴퓨터로 풀수 있는지, 또 얼마나 효율적으로 풀수 있는지를 탐구한다. 이 분야는 크게 계산가능성 이론 (Computability Theory) 과 계산복잡도이론 (Computational Complexity Theory) 으로 나뉘어 있는데, 두 분야 모두 추상 기계를 다룬다.... 위키백과 : 계산이론

Computation 은 주어진 입력으로부터 문제의 해법을 찾는 것으로 정의될 수 있다. 그것이 컴퓨터과학과 수학의 하위과목인 계산이론 (Theory of Computation) 에서 다루는 것이다. 그것은 현대적인 전자컴퓨터가 발명되기 전인 20 세기에 처음 등장했다. 그때 수학자들은 수학문제들이 간단한 방법으로 해결가능한지 아닌지를 알려고 노력했다. 첫째 단계가 문제를 풀기위한 "간단한 방법 (simple method)" 이 의미하는 바를 정의하는 것이었다. 달리말하면, 계산의 형식모델 (formal model of computation) 을 필요로 했다.

term

초기의 연구자들에 의해 여러개의 계산모델이 만들어졌다. 그중 하나가 튜링기계 (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)

원본 계층 분류표 (SolidLine.png · DottedLine.png & 원본 표기 유지) 모바일 환경에서는 표 내부를 좌우로 스크롤하여 전체 도식을 보실 수 있습니다.
 

 

Decision Problem

 

 

 

SolidLine.png

 

SolidLine.png

 

 

Type 0 (Recursively enumerable)

 

Undecidable

SolidLine.png

 

 

 

 

 

Decidable

 

 

 

 

 

SolidLine.png

 

 

 

 

 

EXPSPACE

 

 

 

 

 

DottedLine.png

 

 

 

 

 

EXPTIME

 

 

 

 

 

DottedLine.png

 

 

 

 

 

PSPACE

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

Type 1 (Context-sensitive)

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

PSPACE-Complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

Co-NP

DottedLine.png

 

NP

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

DottedLine.png

SolidLine.png

SolidLine.png

DottedLine.png

BPP

 

BQP

 

NP-complete

SolidLine.png

SolidLine.png

DottedLine.png

DottedLine.png

 

DottedLine.png

 

 

SolidLine.png

SolidLine.png

P

SolidLine.png

SolidLine.png

DottedLine.png

 

DottedLine.png

SolidLine.png

NC

 

P-Complete

SolidLine.png

SolidLine.png

 

 

 

 

 

Type 2 (Context-free)

 

 

 

 

 

SolidLine.png

 

 

 

 

 

Type 3 (Regular)

 

 

 

 

 

SECTION 04 · REFERENCES & LECTURES

참고 웹 사이트 · 학술 논문 · 대학 강의 영상

video : 계산이론 대학 공개 강의

컴퓨테이션 이론, 2014년 2학기 : 건국대학교 : 남원홍 ... 동영상 23개
Theory of Computation - Fall 2011 (Course) : UCDavis : Dan Gusfield, 2012/12/11 .... Playlist 22 : text ... Introduction to the Theory of Computation (Michael Sipser)
Introduction to the Theory of Computation : Coderisland : Shai Simonson, 2010/05/07 .... Playlist 129