算法の全域性局所性

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

算法の全域性・局所性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/02/17 04:37 UTC 版)

「代数的構造」の記事における「算法の全域性・局所性」の解説

実数すべてから成る集合とそこでの四則（加減乗除の算法、すなわち足し算・引き算・掛け算・割り算）との組は、典型的な代数系である。この例では、足し算・引き算・掛け算は任意の二つの数の組について実行可能であるが、割り算は、0での割り算ができないという意味で局所的（あるいは非全域的）である。代数系の算法には一般には、こういうような局所的（あるいは非全域的）算法も含まれる。たとえば行列の足し算・掛け算も、あらゆるサイズの行列から成る集合での算法とみなせば、局所的である。 こういう局所的算法を含む代数系の理論は複雑であるので、数学の分野では避けられる傾向がある。たとえば行列の足し算・掛け算も、数学者の間でさえ、上記のような意味での局所的算法と捉えて説明されることは稀である。また、上記の実数と四則とから成る代数系は体の典型であるが、体の概念も環の概念も、局所的算法である除法を用いないで説明するのが通例である。 一方で、数理論理学では、研究対象として形式言語を代数系の一種と捉えるが、形式言語における算法は局所的のものが一般的である。たとえば、述語論理学における形式言語である述語言語（論理式と項とから成る）では、論理記号 ∧, ∨, ￢, ⇒, ∀x, ∃x は論理式に対してのみ実行可能な局所算法を表し、関数記号や述語記号は、項のみに対して実行可能な局所算法を表すと解される。また、推論規則も局所的算法と解される。たとえば三段論法は、二つの論理式 A と A ⇒ B とから第三の論理式 B を導き出す推論規則であるが、これは、第二の論理式が A ⇒ B という特別な形のときだけ実行可能な局所算法と解される。