Normal form (abstract rewriting)

ウィキペディア

正規化 (項書き換え)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/21 15:36 UTC 版)

項書き換えなどにおいて正規化（せいきか、英: normalization）とは、項をそれ以上書き換えられなくなるまで書き換えることや、あるいはこのような操作が可能だという性質のことである。ある項がそのような性質を持つこと指して「項が正規化する」(normalizing) あるいは「項が正規化可能である」(normalizable) ともいう。また、そのような操作の末に辿り着いたそれ以上書き換えできない項のことを正規形 (normal form) とよぶ。

概要

正規化と呼ばれる性質には、一般に弱正規化 (weak normalization, WN) と強正規化 (strong normalization, SN) と呼ばれる2つがあり、単に正規化と言った場合にどちらを意味するかは分野の慣習によって異なる。弱正規化とは、ある項が与えられたときに、うまく書き換えの手順を選べば何度かの書き換えの末にある正規形に辿り着くことができるような性質を表し、一方、強正規化は、どのように書き換えたとしてもいつかは正規形に到達するという性質を表す。明らかに、項が強正規化するなら弱正規化するが、逆は必ずしも成り立たない。

項書き換え系を計算として見たときには、強正規化は計算の停止性に対応し、ある種の「よい」性質とみなされることがある。例えば、型無しラムダ計算は強正規化しないが、単純型付きラムダ計算は強正規化する。

定義

項の集合 $T$ この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。