처치-로서 정리

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 역사
3. 순수 무형 람다 계산 (Pure untyped lambda calculus)
- 3.1. 증명
4. 정규화 (Normalisation)
5. 변형 (Variants)
6. 같이 보기
참조

1. 개요

처치-로서 정리는 람다 계산에서 항의 축약에 관한 정리로, 1936년 앨런조 처치와 J. 바클리 로서에 의해 증명되었다. 이 정리는 순수 무형 람다 계산에서 β-축약과 같은 특정 축약 규칙에 적용되며, 축약된 두 항이 공통 항으로 축약되어야 함을 의미한다. 처치-로서 정리는 다이아몬드 속성을 만족하는 관계를 이용하여 증명되며, 정규화를 통해 항이 최대 하나의 정규형을 갖도록 한다. 또한, 단순 타입 람다 계산과 같은 람다 계산의 변형에도 적용되며, 함수형 프로그래밍 평가의 특성을 증명하는 데 사용되기도 한다.

더 읽어볼만한 페이지

재작성 시스템 - 합류성
합류성은 재작성 시스템 이론에서 초기 상태에서 여러 재작성 규칙을 적용했을 때 최종 결과가 동일함을 보장하는 속성으로, 시스템의 동작 예측 가능성과 관련되며 항 재작성 시스템에서 규칙 적용 순서에 관계없이 동일한 정규형으로 수렴하는 것을 의미한다.
재작성 시스템 - 항 (논리학)
항(논리학)은 변수, 상수, 함수 기호로 재귀적으로 정의되는 구문 요소로서, 담론 영역에서 수학적 객체를 나타내며 트리 구조, 구조적 동일성, 기저항, 선형항 등의 속성을 가지고, 항 연산을 통해 부분항 대체, 깊이 측정, 패턴 매칭 등이 가능하다.
람다 대수 - 익명 함수
익명 함수는 이름이 없는 함수로, 람다 추상, 람다 함수, 람다 표현식, 화살표 함수 등으로 불리며, 함수형 프로그래밍 언어에서 람다식 형태로 많이 사용되고 고차 함수의 인수, 클로저, 커링 등에 활용되지만, 재귀 호출의 어려움이나 기능 제한과 같은 단점도 존재한다.
람다 대수 - 커링
커링은 다수의 인수를 취하는 함수를 단일 인수를 취하는 함수들의 연속으로 변환하는 기법으로, 함수형 프로그래밍에서 다인수 함수를 분해하여 적용하는 방식이며, 논리학과 컴퓨터 과학에서 널리 활용되는 중요한 개념이다.
수학기초론 정리 - 괴델의 불완전성 정리
괴델의 불완전성 정리는 산술을 표현할 수 있는 무모순적 공리계는 그 안에서 증명하거나 반증할 수 없는 명제가 존재하며, 특히 체계 스스로의 무모순성을 증명할 수 없다는 수학적 논리 분야의 핵심 정리이다.
수학기초론 정리 - 칸토어의 정리
칸토어의 정리는 집합 X의 멱집합의 크기가 X의 크기보다 항상 크다는 것을 나타내며, 임의의 기수 κ에 대해 2^κ > κ가 성립한다는 내용으로, 칸토어의 대각선 논법으로 증명되고 집합론의 역설과 관련되어 전체 집합의 존재를 가정할 때 칸토어의 역설을 유발한다.

처치-로서 정리
개요
분야	수학, 논리학, 전산학
유형	정리
이름	처치-로서 정리
다른 이름
영어	Church–Rosser theorem
일본어	チャーチ・ロッサーの定理
내용
설명	추상 환원 시스템에서 환원의 합류성 속성을 제공하는 정리임.
람다 대수에서의 의미	람다 대수에서 임의의 항이 두 개의 다른 항으로 환원될 수 있다면, 이 두 항 모두 공통 항으로 환원될 수 있음을 의미함.
중요성
응용	프로그래밍 언어의 의미론, 형식적 사양, 병행 시스템과 같은 분야에서 중요한 역할 수행.
의미	계산 결과가 평가 순서에 관계없이 동일함을 보장하는 데 사용됨.
관련 개념
관련 개념	합류성 정규화 속성 추상 환원 시스템
추가 정보
참고	계산 순서에 상관없이 결과가 동일함을 보장하는 중요한 정리임.

2. 역사

1936년, 앨런조 처치와 J. 바클리 로서는 β-축약에 대해 처치-로서 정리가 성립함을 증명하였다. 이 증명 방법은 "전개 유한성"으로 알려져 있다. 1965년 D. E. 슈로어는 순수 비형식 람다 계산에 대한 결과를 증명하였다.

3. 순수 무형 람다 계산 (Pure untyped lambda calculus)

순수 무형 람다 계산에서 처치-로서 정리가 적용되는 한 유형의 축약은 β-축약이며, 이는 $( \lambda x . t) s$ 형태의 하위 항을 $t [ x := s]$ 로 치환하여 축약하는 것이다. β-축약을 $\rightarrow_\beta$ 로, 그리고 그 반사적, 전이적 폐쇄를 $\twoheadrightarrow_\beta$ 로 나타내면 처치-로서 정리는 다음과 같다:

: $\forall M, N_1, N_2 \in \Lambda: \text{if}\ M\twoheadrightarrow_\beta N_1 \ \text{and}\ M\twoheadrightarrow_\beta N_2 \ \text{then}\ \exists X\in \Lambda: N_1\twoheadrightarrow_\beta X \ \text{and}\ N_2\twoheadrightarrow_\beta X$

이 속성의 결과는 $\lambda\beta$ 에서 같은 두 항은 공통 항으로 축약되어야 한다는 것이다.

: $\forall M, N\in \Lambda: \text{if}\ \lambda\beta \vdash M=N \ \text{then}\ \exists X: M \twoheadrightarrow_\beta X \ \text{and}\ N\twoheadrightarrow_\beta X$

이 정리는 $\lambda x.Sx$ 하위 항을 $S$ 로 대체하는 η-축약에도 적용된다. 또한 두 축약 규칙의 합집합인 βη-축약에도 적용된다.

3. 1. 증명

윌리엄 W. 테이트와 페르 마틴-뢰프는 β-축약을 위한 증명 방법을 제시했다. 이 방법은 다이아몬드 속성을 만족하는 관계를 통해 처치-로서 속성을 증명한다. η-축약 규칙은 직접 처치-로서 속성을 갖는 것으로 증명될 수 있다.

먼저, 이항 관계

\rightarrow

가 다음 다이아몬드 속성을 만족한다고 가정한다.

:

\forall M, N_1, N_2 \in \Lambda: \text{if}\ M\rightarrow N_1 \ \text{and}\ M\rightarrow N_2 \ \text{then}\ \exists X\in \Lambda: N_1\rightarrow X \ \text{and}\ N_2\rightarrow X

그러면 처치-로서 속성은

\twoheadrightarrow_\beta

가 다이아몬드 속성을 만족한다는 명제이다. 이를 증명하기 위해 반사적 추이적 폐쇄가

\twoheadrightarrow_\beta

이고 다이아몬드 속성을 만족하는 새로운 축약

\rightarrow_{\|}

를 도입한다. 축약 단계 수에 대한 귀납법을 통해

\twoheadrightarrow_\beta

가 다이아몬드 속성을 만족한다는 결론을 얻는다.

관계

\rightarrow_{\|}

는 다음 규칙을 따른다.

$M \rightarrow_{\|} M$
만약 $M \rightarrow_{\|} M'$ 이고 $N \rightarrow_{\|} N'$ 이면, $\lambda x.M \rightarrow_{\|} \lambda x.M'$ 이고 $MN \rightarrow_{\|} M'N'$ 이며 $(\lambda x. M)N \rightarrow_{\|} M'[x:=N']$ 이다.

또한, β-축약과 η-축약은 서로 교환 가능하다. 즉, 만약

M \rightarrow_\beta N_1

이고

M \rightarrow_\eta N_2

이면,

N_1 \rightarrow_\eta X

이고

N_2\rightarrow_\beta X

를 만족하는 항

X

가 존재한다.

따라서 βη-축약은 처치-로서 속성을 갖는다고 결론 내릴 수 있다.

4. 정규화 (Normalisation)

처치-로서 성질을 만족하는 축약 규칙은 모든 항 ''M''이 최대 하나의 서로 다른 정규형을 가질 수 있다는 성질을 갖는다. 만약 ''X''와 ''Y''가 ''M''의 정규형이라면, 처치-로서 성질에 의해 둘 다 동일한 항 ''Z''로 축약된다. 두 항 모두 이미 정규형이므로 $X=Z=Y$ 이다.

축약이 강하게 정규화되면(무한한 축약 경로는 없음) 처치-로서 성질의 약한 형태가 전체 성질을 함축한다(뉴먼의 보조정리 참조). 관계 $\rightarrow$ 에 대한 약한 성질은 다음과 같다.

: $\forall M, N_1, N_2\in \Lambda:$ 만약 $M\rightarrow N_1$ 이고 $M\rightarrow N_2$ 라면, $N_1\twoheadrightarrow X$ 이고 $N_2 \twoheadrightarrow X$ 를 만족하는 항 $X$ 가 존재한다.

5. 변형 (Variants)

처치-로서 정리는 단순 타입 람다 계산, 고급 타입 시스템을 갖춘 계산법, 그리고 고든 플롯킨의 베타-값 계산법과 같은 람다 계산법의 많은 변형에도 적용된다. 고든 플롯킨은 처치-로서 정리를 사용하여 함수형 프로그래밍의 평가가 ( 느긋한 계산법과 조급한 계산법 모두에 대해) 프로그램에서 값으로의 함수(람다 항의 부분 집합)임을 증명했다.

과거 연구 논문에서는, 재작성 시스템이 합류할 때 처치-로서라고 하거나 처치-로서 속성을 갖는다고 말한다.

6. 같이 보기

합류

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com