베타 정규 형태

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "정상적인 형태" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2021년 5월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

람다 미적분학에서 항은 베타 축소가 불가능할 경우 베타 정규 형식이다.^[1]베타 감소와 에타 감소가 모두 불가능한 경우 용어는 베타-에타 정규 형식이다.머리 위치에 베타 레덱스가 없을 경우 용어는 머리 정규 형식이다.

베타절감소

람다 미적분학에서 베타 레덱스는 다음과 같은 형태의 용어다.

${\displaystyle (\mathbf {\lambda$$x$$A)M}$.

readx $r{\displaystyle }$ ${\displaystyle r}$이$($가) $t{\displaystyle }$ ${\displaystyle t}$이라는 용어의 머리 위치에 있는 경우$$(애플리케이션의 우선 순위가 추상화보다 높으며 아래 공식은 애플리케이션이 아닌 람다 압착이라는 점에 유의하십시오.

${\$$\underbrace {(\boda x)$$A)M_{1} _{\text${{\$text{{}r}M_{2}\ldots M_{m$ 여기서 $n{\displaystyle }$ ${\displaystyle \ge }$ ${\displaystyle n\geq 0}$ 및 $m$ m ${\displaystyle 1}$ ${\displaystyle m\geq$ 1$\}.$

베타 축소는 용어에 포함된 베타 레덱스에 다음과 같은 재작성 규칙을 적용하는 것이다.

$(\displaystyle)(\mathbf {\batda } x).A)M\longrightarrow A[x:=M]}$

${\displaystyle \mathrm{여기}}$서 $A{\displaystyle }$[ x $:=$ ${\displaystyle M}$ ] {\$displaystyle A[x:=M]}$은(는) $A{\displaystyle }$ ${\displaystyle A}$이라는 용어의$$ $변수{\displaystyle }$ x$${\$displaystyle x}$에 $대해{\displaystyle }$ M ${\displaystystyle M}$을(를) 대신한 결과물이다$.$

헤드 베타 감소란 헤드 포지션에 적용되는 베타 감소, 즉 다음 형태의 감소를 말한다.

$\lambda x_{1}\ldots \lambda x_{n}$$(\cHBDA x)$$A)M_{1}M_{2}\ldots M_{m}\longrightarrow \lambda x_{1}\ldots \lambda x_{n}.$$A[x:=M_{1}]$${\displaystyle \mathrm{M\_}}$${2}\ldots M_{m$ 여기서 $n{\displaystyle }$ ${\displaystyle \ge }$ 0 ${\displaystyle n\geq 0}$ 및$$ ${\displaystyle \mathrm{m}}$ ${\displaystyle \ge }$ 1 ${\displaystyle m\geq$ 1$\}.$

다른 모든 감소는 내부 베타 감소다.

정상형식은 베타 리덱스를 포함하지 않는 용어, 즉 더 이상 줄일 수 없는 용어다.머리 정상형식은 머리 위치에 베타 리덱스를 포함하지 않는 용어, 즉 머리 축소로 더 이상 줄일 수 없다.단순한 람다 미적분(상수 또는 함수 기호를 추가하지 않은 viz. 추가 델타 규칙에 의해 감소되는 것을 의미함)을 고려할 때, 머리 정상 형태는 다음 모양의 용어다.

${\$$xM_{1}M_{2}\ldots M_{m},$여기서 $x{\displaystyle }$ ${\displaystyle$ x$}$은 변수$$, n${\displaystyle \mathrm{n}}$ 0 ${\displaystyle n\geq 0}$ 및$$ ${\displaystyle \mathrm{m}}$ ${\displaystyle \ge }$ 0 ${\displaystyle m\geq 0$

적용된 인수 $M{\displaystyle {}_{}}$ ${\displaystyle j_{}}$ ${\$이(가) 정규일 필요는$$ 없기 때문에 헤드 정규 형식이 항상 정규 형식은 아니다.그러나, 그 반대는 사실이다: 어떤 정상적인 형태도 정상형이다.${\displaystyle {사실}_{}}$ 정상적인 형태는 정확히 M j ${\$ 하위 용어 $자체$가 정상적인$$ 형태인 머리 정상 형태다.이것은 정상적인 형태에 대한 귀납적 통사적 설명을 제공한다.

또한 약한 머리 정상 형태의 개념도 있다: 약한 머리 정상 형태의 용어는 머리 정상 형태의 용어나 람다 추상화 중 하나이다.^[2]이것은 레덱스가 람다 몸 안에 나타날 수 있다는 것을 의미한다.

감축전략

일반적으로 특정 용어는 여러 개의 리덱스를 포함할 수 있으므로, 여러 가지 다른 베타 감소를 적용할 수 있다.우리는 어떤 리덱스를 줄일 것인지 선택하는 전략을 지정할 수 있다.

• 정상질서 축소는 더 이상 그러한 축소가 불가능할 때까지 헤드 포지션의 베타 축소를 위한 규칙을 지속적으로 적용하는 전략이다.그 시점에서, 그 결과 용어는 머리 정상형이다.그런 다음 왼쪽에서 오른쪽으로$$M ${\displaystyle j_{}}$ ${\$ 하위 단자에 머리 축소를 계속 적용한다.달리 말하면, 정상 주문 감소는 항상 가장 바깥쪽 가장 바깥쪽 가장 먼저 리덱스를 줄이는 전략이다.
• 이와는 대조적으로 적용 오더 감소에서는 내부 감소를 먼저 적용한 후 더 이상 내부 감소가 불가능할 때만 머리 감소를 적용한다.

용어의 머리 모양이 정상이면 정상 순서 감소는 결국 도달한다는 점에서 정상 순서 감소는 완전하다.위의 정규 형식에 대한 통사적 설명에 의해, 이것은 "완전히" 정규 형식에 대해 같은 문구를 수반한다(이것이 표준화 정리다).이와는 대조적으로, 적용 가능한 주문 축소는 용어의 형식이 정상인 경우에도 종료되지 않을 수 있다.예를 들어 적용 오더 감소를 이용하여 다음과 같은 감산 순서가 가능하다.

${\displaystyle {\displaysty}&(\mathbf {\data } x.z)((\data w.csw)(\data w.cf)\\\오른쪽 화살표 &(\whiteda x.z)((\wwww)(\wwda w.ww)(\wwda w.w.)(\www))\\\오른쪽 화살표 &(\lambda x.z)((\(da w.www)(\lambda w.www)(\lambda w.www)(\dada w.ww)))\\\오른쪽 화살표 &(\\da x.z)((\lambda w.www)(\lambda w.www)(\dada w.ww)(\dada w.ww))(\lambda w.www))\&\ldots \end{aigned}}$

그러나 정상 순서 축소를 사용하면 동일한 시작점이 빠르게 정상 형태로 감소한다.

${\displaystyle(\mathbf {\batda } x.z)((\batda w.cdw)(\batda w.cdw)})}$

$\displaystyle \rightarrow z}$

시노트의 이사 문자열은 베타 감소의 계산 복잡성을 최적화할 수 있는 한 가지 방법이다.

참고 항목

• 람다 미적분학
• 일반 형태(동음이의)

참조