2.0 계산 이론 — 도구가 풀 수 있는 문제에는 경계가 있다

정규식, 설정 검증기, 정적 분석기, 스케줄러는 모두 "이 문제를 풀어 달라"는 요청에 답하는 도구다. 이 인트로는 같은 스프린트에서 세 도구가 각자 다른 방식으로 기대를 배신한 사례에서 출발해, 그 배신이 버그가 아니라 서로 다른 세 가지 원리적 경계 — 표현 가능성, 계산 가능성, 계산 비용 — 때문이라는 것을 세우고, 챕터 2의 네 문서가 각 경계를 어떻게 다루는지 안내한다.

학습 목표

• 실무 도구의 실패를 "버그"로 뭉뚱그리지 않고 표현 가능성·계산 가능성·계산 비용 중 어느 경계에서 생겼는지 구분한다.
• "만족 가능하다", "결정 불가능하다", "NP-난해하다"는 말이 각각 무엇을 보장하고 무엇을 보장하지 않는지 설명한다.
• 챕터 2의 네 문서(논리 → 형식 언어 → 계산 가능성 → 복잡도)가 이 세 경계를 어떤 순서로 세우는지 파악하고 학습 순서를 정한다.

출발점: 같은 주에 벌어진 세 번의 배신

한 결제 플랫폼 팀이 한 스프린트 안에서 세 가지 사건을 겪었다.

월요일. 배포 파이프라인의 설정 검증기가 "이번 배포의 피처 플래그 조합은 일관적입니다(satisfiable)"라고 승인했다. 그런데 프로덕션에 올라가자 신규 인증과 레거시 인증이 동시에 활성화되어 있었다 — 검증기가 확인한 규칙 안에는 "신규 인증이 켜지면 레거시 인증은 꺼져야 한다"는 조건 자체가 빠져 있었다.

수요일. 정적 분석기가 어떤 함수 하나를 몇 분째 붙잡고 있다가 결국 "분석 시간 초과"를 반환했다. 팀은 "분석기가 멈췄다, 버그를 고쳐야 한다"고 결론지었다. 나중에야 그 함수가 실제로 종료하는지 자체가 일반적으로 답할 수 없는 질문일 수 있다는 것을 알게 됐다.

금요일. 사용자 입력을 검증하던 정규식 하나가 특정 입력에서 CPU 코어 하나를 몇 초씩 물고 응답을 멈췄다. 롤백 후 원인을 보니 알고리즘 로직에는 버그가 없었다 — 정규식 자체는 올바르게 패턴을 표현하고 있었다.

세 사건 모두 "도구가 기대만큼 일하지 못했다"는 점은 같다. 하지만 원인은 전혀 다르다.

사건	실제로 무너진 경계
월요일: satisfiable인데 틀렸다	검증기가 확인한 것은 명시된 규칙끼리의 무모순성이었지, 실제 배포 요구사항과의 일치가 아니었다
수요일: 분석이 멈추지 않는다	"이 함수는 항상 종료하는가"라는 질문 자체가 일반적으로 알고리즘이 존재하지 않는 질문일 수 있다
금요일: 정규식이 입력을 물고 늘어진다	패턴은 올바르지만 그것을 실행하는 알고리즘의 시간 비용이 입력에 따라 지수적으로 늘어난다

세 경계에 이름을 붙이면 챕터 2의 지도가 된다.

1. 표현 가능성(expressibility)의 경계 — 요구사항을 애초에 정확하게 표현할 언어가 있는가? 표현했다면 그 표현이 참으로 강제하는 것과 하지 않는 것은 무엇인가?
2. 계산 가능성(decidability)의 경계 — 그 표현에 대해 항상 멈추고 정답을 내는 알고리즘이 원리적으로 존재하는가?
3. 계산 비용(tractability)의 경계 — 알고리즘이 존재해도, 현실적인 시간 안에 끝나는가?

세 경계는 독립적이다. 표현은 정확했는데 계산이 불가능할 수도 있고(수요일), 계산은 가능한데 비용이 감당 안 될 수도 있고(금요일), 계산도 비용도 문제없는데 애초에 표현한 명제 자체가 현실을 반영하지 못했을 수도 있다(월요일). "도구가 왜 실패했는가"라는 질문에 정확히 답하려면 이 세 경계 중 어디에서 문제가 생겼는지부터 가려야 한다.

익숙한 표현과 확인해야 할 계약

경력 개발자가 정규식·SAT 솔버·정적 분석기·스케줄러를 이미 써 봤다는 사실은 이 경계들을 안다는 뜻이 아니다. 익숙한 말투 아래에 실제로 확인해야 할 계약이 있다.

익숙한 표현	확인해야 할 계약
"이 논리식이 만족 가능(satisfiable)하니 요구사항은 문제없다"	만족 가능성은 명시된 제약끼리 모순이 없다는 뜻일 뿐, 현실의 숨은 전제까지 검증한다는 뜻이 아니다 — 2.1
"정규식이면 이 정도 구조는 다 잡아낼 수 있다"	정규식이라는 표기, 정규 언어라는 수학적 대상, 실제 엔진의 실행 방식은 서로 다른 것이고 표현력의 한계가 있다 — 2.2
"분석기 성능만 더 개선하면 언젠가 모든 경우를 정확히 판정한다"	결정 불가능성은 계산 자원을 아무리 늘려도 사라지지 않는 원리적 한계다 — 2.3
"느린 건 구현이 미숙해서고, 더 최적화하면 빨라진다"	문제 자체에 다항 시간 알고리즘이 없을 수 있다(NP-난해) — 최적화로 없어지지 않는 비용이다 — 2.4

이 표의 오른쪽 칸이 이 챕터가 세우려는 판단 기준이다. 정의를 암기하는 게 아니라, 눈앞의 도구가 실패했을 때 "이건 표현의 문제인가, 계산 가능성의 문제인가, 비용의 문제인가"를 스스로 구분할 수 있게 되는 것이 목표다.

챕터 2가 세우는 네 가지 질문

2.1 수리논리 — 프로그램을 명세하고 추론하는 언어

자연어 요구사항을 기계가 검사할 수 있는 명세로 바꾸면 무엇을 얻고 무엇을 잃는가?

명제·술어 논리의 구문과 의미를 구분하고, 만족 가능성·타당성·논리적 함의를 서로 다른 질문으로 세운다. 건전성(soundness)과 완전성(completeness)이 증명 체계와 분석 도구의 신뢰성을 어떻게 규정하는지, SQL의 3값 논리가 고전 논리와 어디서 갈라지는지까지 다룬다. 여기서 세운 CNF와 만족 가능성 개념은 2.4의 SAT·NP-완전성 논의로 곧장 이어진다.

2.2 형식 언어와 오토마타 — 언어의 구조와 인식기의 경계

입력의 어떤 구조는 유한한 상태만으로 인식할 수 있고, 어떤 구조는 왜 스택이나 더 강한 계산 모델을 요구하는가?

촘스키 계층 위에서 정규 언어와 문맥 자유 언어의 위치를 확인하고, DFA·NFA·Thompson construction으로 정규식과 오토마타를 연결한다. "정규식은 모두 정규 언어이며 모든 엔진이 같은 방식으로 실행한다"는 통념을 정면으로 반박하고, 수학적 대상(정규 언어)과 표면 문법(정규식 표기)과 실행 전략(lockstep 시뮬레이션 대 백트래킹)을 분리한다.

2.3 계산 가능성 — 계산할 수 없는 문제와 분석 도구의 한계

모든 프로그램에 대해 항상 끝나면서 정답을 주는 완벽한 분석기를 만들 수 없는 이유는 무엇인가?

튜링 기계와 처치-튜링 논제로 계산 가능성의 모델을 세우고, 정지 문제의 대각선 논증으로 결정 불가능성을 직접 구성한다. Rice의 정리가 "프로그램의 의미 있는 성질은 일반적으로 자동 판정할 수 없다"는 결론으로 이어지는 과정을 확인하고, 이것이 정적 분석기가 건전성·완전성·항상 종료 중 하나를 반드시 포기해야 하는 이유임을 보인다.

2.4 복잡도 클래스 — 풀 수 있지만 감당하기 어려운 문제

문제를 정확히 푸는 비용이 감당할 수 없을 때, 어떤 근거로 exact·근사·휴리스틱·솔버 중 하나를 선택하는가?

P와 NP를 인증서 검증 가능성으로 정의하고, 다항 시간 환원으로 NP-완전·NP-난해가 퍼져 나가는 방식을 확인한다. "지수 시간으로 동작하면 그 문제는 NP-난해하다"는 통념을 반박하는 대표 반례로 백트래킹 정규식 엔진의 ReDoS를 다시 가져와, 알고리즘의 비효율과 문제 자체의 하한을 구분한다.

네 문서는 독립된 지식이 아니라 하나의 판단 경로다. 2.1의 구문·의미 구분은 2.2의 언어·문법·인식기 구분에 그대로 재사용되고, 2.1의 만족 가능성은 2.4의 SAT·NP-완전성 논의로 이어진다. 2.2의 인식 가능성은 2.3의 결정 가능성 논의로, 2.3이 확인한 "알고리즘의 존재 여부"는 2.4가 다루는 "존재하는 알고리즘의 자원 비용"과 짝을 이룬다. 이 챕터를 마치면 정규식 엔진을 NFA 기반으로 직접 구현하고 백트래킹 엔진과 성능을 비교하는 실습으로 네 질문을 한 번에 확인한다.

정리

• 도구의 실패는 표현 가능성, 계산 가능성, 계산 비용이라는 서로 다른 경계에서 생길 수 있고, 세 경계는 서로 독립적이다.
• "만족 가능하다"는 명시된 제약의 무모순성일 뿐 현실과의 일치를 보장하지 않고, "결정 불가능하다"는 자원을 늘려도 사라지지 않으며, "NP-난해하다"는 알고리즘의 미숙함과 다른 문제 자체의 하한이다.
• 챕터 2는 논리(2.1) → 형식 언어(2.2) → 계산 가능성(2.3) → 복잡도(2.4) 순서로, 표현에서 시작해 계산의 존재 여부를 거쳐 계산의 비용으로 판단 범위를 좁혀 간다.

확인 문제

1. 동료가 "SAT 솔버가 이 배포 설정이 satisfiable하다고 확인했으니 이 설정에는 문제가 없다"고 주장한다. 월요일 사건과 같은 구조의 반박을 제시하라.

정답과 해설

satisfiable은 솔버에게 입력된 제약식들 사이에 모순이 없다는 뜻일 뿐이다. 실제 요구사항 중 제약식으로 옮기지 못했거나 아예 명시되지 않은 전제(예: "신규 인증이 켜지면 레거시 인증은 꺼져야 한다")가 있다면, 그 전제를 위반하는 배정도 "만족 모델"에 포함될 수 있다. 즉 솔버는 모델링된 세계 안에서만 정확하고, 모델링이 현실을 빠짐없이 반영했는지는 솔버가 검증해 주지 않는다. 자세한 논증은 2.1에서 다룬다.

2. 수요일 사건에서 "분석 시간 초과"를 팀이 "고쳐야 할 버그"로 취급한 판단의 어디가 성급했는지, 이 문서의 세 경계 구분으로 설명하라.

정답과 해설

시간 초과는 구현 결함(계산 비용 최적화 부족)일 수도 있지만, 애초에 그 질문 — "이 함수가 모든 입력에서 항상 종료하는가" 같은 비자명한 의미적 성질 — 이 일반적으로 결정 불가능할 수 있다. 후자라면 아무리 성능을 개선해도 "항상 종료하고 항상 정확한" 분석기는 원리적으로 만들 수 없고, 분석기가 택할 수 있는 것은 시간 제한을 두고 "unknown"을 반환하는 설계뿐이다. 버그인지 원리적 한계인지를 가르지 않으면 팀은 존재하지 않는 최적화를 무한히 찾아 헤매게 된다. 자세한 논증은 2.3에서 다룬다.

참고 자료

• Michael Sipser, Introduction to the Theory of Computation 3rd ed. (Cengage, 2012) — 논리·오토마타·계산 가능성·복잡도를 한 권으로 잇는 표준 교재. 챕터 2 전체의 배경 지도로 활용한다.
• John Hopcroft, Rajeev Motwani, Jeffrey Ullman, Introduction to Automata Theory, Languages, and Computation 3rd ed. (Pearson, 2006) — 형식 언어와 오토마타를 더 깊이 파고드는 표준 교재. 2.2의 촘스키 계층과 pumping lemma를 보완 자료로 확인할 때 사용한다.
• CWE-1333, Inefficient Regular Expression Complexity — 금요일 사건 같은 ReDoS를 공식적으로 분류한 항목. 표현·계산 가능성·비용 중 어디에 해당하는 결함인지는 2.2와 2.4에서 구분해 다룬다.