算法概念の拡張
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/06 04:04 UTC 版)
冒頭に定義したとおり、f が集合 A における n 項算法であるとは、f が An のある部分集合 D から A への写像であることをいう。そうすると f は、An×A の部分集合 {((x1, ... , xn), y) | (x1, ... , xn)∈D, f(x1, ... , xn) = y } と同一視される。従って、もしも f, g, ... が n 項算法なら、それらの集合としての和を考えることができる。しかし一般には、f を動かせば、それに応じて n も動く。そこで、より一般に、An (n = 0, 1, 2, ... < ω) の集合としての直和を A* で表し、A* × A の部分集合 R のことまでも算法とよぶことにする。ただしこういう広義 の算法については、α ∈ A* と y ∈ A とが (α, y) ∈ R をみたすことを通常の算法のように R(α) = y と書き表すことはできず、α R y と書かなければならない。一つの α ∈ A* に対して (α, y) ∈ R をみたす y が唯一つとは限らないからである。この意味でこれは、もはや算法ではなく（やはり広義の ）関係とよぶべきかもしれない。 こういう広義の算法・関係は、数理論理学にしばしば現れる。例えば述語言語 A において、意味写像 f * の下で inf {f *(a1), ... , f *(an)} ≤ f *(b) をみたす論理式 a1, ... , an, b （n は任意）から出来る A*×A の元 ((a1, ... , an), b) の全体を R で表せば、これは上記の意味での広義の算法・関係である。 このように算法の概念と関係の概念をともに拡張して統合すると、算法と関係とを統一的に扱うことができて極めて有効である。
※この「算法概念の拡張」の解説は、「算法」の解説の一部です。
「算法概念の拡張」を含む「算法」の記事については、「算法」の概要を参照ください。
- 算法概念の拡張のページへのリンク
