領域理論の意図と直観的意味

ウィキペディア小見出し辞書

領域理論の意図と直観的意味

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 07:55 UTC 版)

「領域理論」の記事における「領域理論の意図と直観的意味」の解説

1960年代末にデイナ・スコットが領域についての研究を開始したそもそもの動機は、ラムダ計算の表示的意味論について研究するためであった。 ラムダ計算においては、この言語が定めている記法で記される「関数」について考察する。 このラムダ計算では純粋に文法的に、単なる関数から入力引数として別の関数をとるような関数を作ることが可能である。 このラムダ計算には、不動点コンビネータ（英: fixed point combinator、Y コンビネータとも）Y といわれるものが存在することが知られている。 これは定義により、ラムダ計算で定められた文法的な変換を施すことで、任意の関数 f に対して f(Y(f)) = Y(f) となる性質をもつものである。 はじめに、このラムダ計算の表示的意味論を作り上げるために、各ラムダ式が通常の（全）関数を表すものとして、両者を対応づけるようなラムダ計算に対する「モデル」を作ることができたのだとしよう。 このようなモデルは純粋に文法的なシステムとしてのラムダ計算と、具体的な数学的関数を扱うための表記上のシステムとしてのラムダ計算との間を結びつけてくれるだろう。 しかし、こうしたモデルは存在しない。 もし存在したとするなら、コンビネータ Y に対応する真の全関数、すなわち任意の入力関数 f の不動点を計算するような関数を含まなければならなくなるからである。 いくつかの関数（例えば「次者関数」）にはこのような不動点は存在しないので、Y に対応するような関数は存在しえない。 よってよくても、Y に対応する通常の関数は、いくつかの入力に対して必ずしも値が定義されていないような部分関数でなければならない。 スコットは、この困難を回避するため、結果を返さない計算を表現するための「部分」もしくは「不完全」な情報という概念を形式化した。 これは、計算の各領域（例えば自然数）に対して「未定義」出力、つまり決して終わらない計算の「結果」を表す新しい要素を付け加えることによりモデル化される。 さらに、この計算の領域には「未定義の結果」が最小元となるような「順序関係」が与えられている。 ラムダ計算のモデルを見つける上で大切なことは、（半順序集合上で）これらの関数のみを考慮することである。 こうした関数は、最小不動点をもつことが知られている。 これらの関数の集合に適切な順序が与えられたものもこの理論の意味で「領域」ではあるが、あらゆる可能な関数ではなく、その部分集合へ制限することにも別の大きな利点がある。 そうした場合、それ自体の関数空間を含むような領域、すなわち関数自身を適用することのできる関数が得られる。 こうした望ましい特性に加えて、領域理論は直観的な解釈に訴えることも可能にしている。 上述のように、計算の領域は常に半順序が与えられている。 この順序は情報あるいは知識の階層を表現している。 この順序でより大きな要素は、より詳しく定められており、より多い情報を含んでいる。 より小さな要素は、不完全な知識、あるいは途中結果を表現している。 このとき計算は、結果を改善するために領域の要素に繰り返し単調関数を適用することとしてモデル化される。 不動点に達することとは計算が完了することである。 領域が、こうした概念に対する優れた枠組みを与えているのは、それに単調関数の不動点が存在することが保証されており、制限を追加すれば、下側から近似できるからである。