계산 이론
- 2026년 3월 21일 Classes — 계산 가능성 클래스 D, E, co-E
결정 가능한 문제의 집합 D, 열거 가능한 문제의 집합 E, 그리고 co-E를 정의하고, D = E ∩ co-E를 증명한다. 정지 문제를 통해 E ≠ D임을 확인한다.
- 2026년 3월 21일 Turing Machine — 계산의 극한
현대 컴퓨터의 이론적 모델인 튜링 머신의 구조를 살펴보고, 2-Tape DTM, Universal Turing Machine, 그리고 DTM과 NTM의 계산 능력이 동일함을 정리한다.
- 2026년 3월 21일 DPDA와 NPDA — 스택을 가진 오토마타
DFA에 스택을 추가한 DPDA가 해결할 수 있는 문제와 없는 문제를 살펴보고, NPDA와의 계산 능력 차이를 분석한다. 스택 2개로 튜링 머신을 시뮬레이션하는 원리까지 다룬다.
- 2026년 3월 20일 NFA — 비결정론적 유한 오토마타
DFA를 확장한 계산 모델인 NFA의 구조와 accept 조건을 살펴보고, Powerset Construction을 통해 NFA와 DFA의 계산 능력이 동일함을 설명한다.
- 2026년 3월 20일 DFA — 결정론적 유한 오토마타
튜링 머신을 단순화한 계산 모델인 DFA의 구조와 동작 원리를 살펴보고, Pumping Lemma를 통해 DFA로 풀 수 없는 문제가 존재함을 증명한다.
- 2026년 3월 19일 Problem & Solution — Complexity Theory의 수학적 정의
Complexity Theory에서 '문제'와 '풀이'는 어떻게 정의될까? Decision Problem, Language, 튜링 머신을 통해 풀리지 않는 문제가 왜 대부분인지를 살펴본다.
- 2026년 3월 18일 집합의 크기(Cardinality) — 무한의 크기를 비교하다
무한집합에도 크기가 있을까? 자연수, 정수, 유리수, 실수의 크기를 비교하고, 칸토어의 대각선 논법을 통해 무한에도 '더 큰 무한'이 있음을 증명한다.
- 2026년 3월 16일 Interesting Number Paradox
수학적 증명에서 '정의(definition)'의 엄밀함이 왜 중요한지를 보여주는 패러독스. 암호학 Complexity Theory 도입부.