오토마타 이론은 계산 가능성의 경계를 정의한다

요약

• 오토마타 이론은 "이 문제가 계산 가능한가?"와 "풀려면 최소 어떤 수준의 계산 능력이 필요한가?"를 분류하는 프레임워크
• 튜링 머신을 기준으로 계산 가능성을 정의하고, 오토마타 계층으로 필요한 계산 능력을 분류

본문

오토마타 계층과 표현력

유한 오토마타 ⊂ 푸시다운 오토마타 ⊂ 튜링 머신
   (정규 언어)    (문맥 자유 언어)    (재귀 열거 언어)

오토마타	메모리	인식 가능한 언어	한계
유한 오토마타 (FA)	없음 (상태만)	정규 언어	개수를 셀 수 없음
푸시다운 오토마타 (PDA)	스택	문맥 자유 언어	중첩 구조만 처리
튜링 머신 (TM)	무한 테이프	재귀 열거 언어	정지 문제 불가

유한 오토마타의 한계

유한 오토마타는 상태만 기억할 수 있어서, aⁿbⁿ (a가 n개, b가 n개) 같은 패턴을 인식하지 못한다. 정규표현식이 유한 오토마타와 동치이기 때문에, 정규표현식으로 HTML 태그의 짝을 검증할 수 없다.

• <div><div></div></div> 같은 중첩 구조에서 첫 번째 <div>가 열린 것을 기억하면서 두 번째도 추적하는 게 불가능
• 실제 HTML 파서는 스택 기반(푸시다운 오토마타 수준)을 사용

계산 가능성의 정의

Church-Turing Thesis: 효과적으로 계산 가능한 모든 것은 튜링 머신으로 계산 가능하다.

튜링 머신으로 풀 수 있으면 계산 가능, 못 풀면 계산 불가능. 정지 문제(Halting Problem)는 대표적인 계산 불가능 문제다.

정지 문제의 증명 (대각선 논법)

1. 정지 문제를 푸는 프로그램 H(P, I)가 있다고 가정
2. 새 프로그램 D(P) 정의: H(P, P)가 true면 무한루프, false면 멈춤
3. D(D) 실행 시 → 멈추면 무한루프해야 하고, 무한루프면 멈춰야 함 → 모순

Automaton vs Transducer

	Automaton	Transducer
출력	Yes/No (수락/거부)	변환된 문자열/값
목적	언어 인식	입력→출력 변환
예시	정규표현식 매칭	컴파일러 (코드→기계어)

참고

• 유한 오토마타는 현재 상태만 기억한다
• 정규 언어는 유한 오토마타로 인식 가능한 언어다