Chapter 4. 처치-튜링 명제와 계산 가능성 이론의 성립 Chapter 4. 처치-튜링 명제와 계산 가능성 이론의 성립 4.1계산 가능성 이론의 역사적 배경과 문제 의식 4.2알론조 처치의 학문적 배경과 형식 체계 연�� 4.3람다 대수(Lambda Calculus)의 구문론적 정의 4.4람다 항(Lambda Term)의 구조: 변수, 추상화, 적용 4.5자유 변수와 묶인 변수의 구분 및 알파 변환(α-conversion) 4.6베타 축약(β-reduction)의 정의와 계산 규칙 4.7에타 변환(η-conversion)과 함수 외연성 4.8정규형(Normal Form)과 처치-로서 정리(Church-Rosser Theorem) 4.9람다 대수의 고정점 조합자(Fixed-Point Combinator) 4.10재귀 함수의 람다 대수적 표현과 Y 조합자 4.11처치 수(Church Numerals)를 통한 자연수 인코딩 4.12람다 대수에서의 산술 연산 정의 4.13처치의 결정 불가능성 증명: 람다 정의 가능성의 한계 4.14쿠르트 괴델의 일반 재귀 함수(General Recursive Functions) 4.15원시 재귀 함수(Primitive Recursive Functions)의 정의와 구성 4.16μ-재귀 함수(μ-recursive Functions)와 최소화 연산자 4.17클레이니의 재귀 정리(Recursion Theorem)와 자기 참조 4.18처치-튜링 명제(Church-Turing Thesis)의 정식화 4.19튜링 기계, 람다 대수, 재귀 함수 간의 동치성 증명 4.20계산 가능 함수(Computable Function)의 정의와 범위 4.21열거 가능성(Enumerability)과 결정 가능성(Decidability)의 구분 4.22라이스 정리(Rice’s Theorem)와 의미론적 속성의 결정 불가능성 4.23계산 복잡도 이론의 기초: P 클래스와 NP 클래스 4.24처치-튜링 명제가 인공지능 이론에 부여하는 계산적 경계