算法
出典: フリー百科事典『ウィキペディア（Wikipedia）』
算法（さんぽう）には主に次の二通りの用法がある。
n 項算法（エヌこうさんぽう）とは、最も広義には、集合 A の直積集合 An の部分集合 D から A への写像 f のことをいい、D をこの算法の定義域という。n は任意の順序数でよい。 これを（仮に）f の項数とよぶ。 An は i < n をみたす順序数 i を添数とする A の元の族 (ai)i<n すべてからなる集合を表す。 集合 A とそこにおける算法の族 R との組み (A, R) を代数系という。
目次 |
[編集] 全域的算法
通常は、D = An の場合を考えることが多く、そういう算法 f を（仮に）全域的算法とよぶ。 また、n が有限順序数の場合を考えることが多い。 その場合、An は A の n 個の元の組み (a0, a1, ..., an-1) の全体であって、f によってこれをうつしたものは f(a0, a1, ..., an-1) と書くことができる。 しかしさらに、n = 2 の場合を考えることが多く、この場合、 f(a0, a1) を a0 f a1 とか a0 a1 f とか書くことが多い。
従って、全域的な 2 項算法とは、A の元の二つ組み (a, b) の各々に A の何らかの元を対応させる写像のことである。
例えば、二つの実数 a, b にその和 a + b を対応させる写像は、実数すべての集合における全域的 2 項算法であって、和の記号 + はこの算法（すなわち加法）の上記二番目の記法 a0 f a1 の f に当たるものと解される。 加法は普通の中置記法では a + b と書くが、逆ポーランド記法では a b + と書く。 これは、上記の a0 a1 f という記法に当たるものと解される。 実数の減法・乗法・除法についても同様である。 ただし除法は、0 で割ることができないから、全域的ではない。
1 項算法も珍しくはない。 例えば、複素数にその共役複素数を対応させる写像は 1 項算法である。 また、体 K 上の線型空間 V においては、 K の任意の元 a と V の任意の元 v に対して V の元 av が存在するが、これは、K を添数集合とする V の 1 項算法族 (fa)a∈K があって fav を av で表していると解される。 こう考えれば、例えば環 R 上の加群 M における R の元の M への作用のような「外的算法」は、すべて 1 項算法とみなされる。 なお、1 項算法は単項算法とよぶ方が語呂がいい。
[編集] 非全域的算法
非全域的（あるいは局所的）な算法も珍しくはない。 例えば、あらゆるサイズの行列の全体を M で表すとき、M の二元 A, B にその和 A + B を対応させる写像は M における 2 項算法であるが、A, B が同サイズのときにしか A + B が定義されないから、非全域的算法である。 A, B にその積 AB を対応させる写像も M における 2 項算法であるが、A の列の個数と B の行の個数が等しいときにしか AB が定義されないから、やはり非全域的算法である。
形式言語における算法は、非全域的のものが一般的である。 例えば、述語言語（論理式と項とから成る）における論理記号は、論理式に対してのみ適用可能な 2 項または 1 項の非全域的算法を表すと解される。
項数が 2 より多い非全域的算法も珍しくはない。 例えば、述語言語における n 変数関数記号や n 変数述語記号は、項に対してのみ適用可能な n 項算法を表すと解される。
[編集] 超限的な項数を持つ算法
超限順序数を項数とする算法もある。 例えば、最小の超限順序数（非負整数の全体の順序型）を ω で表し、実数の全体を R で表すと、直積 Rω は実数列 a0, a1, ... の全体であるが、収束する実数列にその極限を対応させる写像は、非全域的の ω 項算法である。 数列の極限をこのように ω 項算法とみなすことには効用もある。 たとえば、数列の極限の ε-n 式定義を ω 項算法の代数的条件によって書き換えて、極限を公理化することができる。 つまり、R における次の六条件をみたす ω 項算法 L が極限に他ならない。
- L(a, a, ...) = a
- L(a1, a2, ...) = a, L(b1, b2, ...) = b, an ≤ bn (n=1,2,...) なら a ≤ b
- L(a1, a2, ...) = a なら a1, a2, ... の任意の部分列 b1, b2, ... に対して L(b1, b2, ...) = a
- （はさみうちの原理）L(a1, a2, ...) = L(b1, b2, ...) = a, an ≤ cn ≤ bn (n=1,2,...) なら L(c1, c2, ...) = a
- （アルキメデスの原理）L(a±(1/1), a±(1/2), a±(1/3), ...) = a （複号同順）
- a1, a2, ... の任意の部分列 b1, b2, ... に L(c1, c2, ...) = a なる部分列 c1, c2, ... があれば L(a1, a2, ...) = a
大学 1, 2 年次の学生や高校生に「行列の算法は非全域的算法である」とか「極限は ω 項算法である」とか教えるのは勧められないが、数理科学者がそういうことを認識するのは、視野が広がるので好ましいであろう。
[編集] 算法概念の拡張
冒頭に定義したとおり、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 で表せば、これは上記の意味での広義の算法・関係である。
このように算法の概念と関係の概念をともに拡張して統合すると、算法と関係とを統一的に扱うことができて極めて有効である。
[編集] 命名について
算法を「演算」とよぶことも多い。 しかし、ここで考えた「算法の概念」の名前としては、「算法」も「演算」も相応しくはないであろう。 「算法」は「計算の規則」あるいは「計算の方法」を連想させ、「演算」は「計算を演ずるという行為」を連想させ、ともに「写像」としての「算法の概念」を連想させにくい。 一つの写像に対しても、それの「計算の方法」は一般に複数あり、「計算する方法」も「計算の規則」も具体的に記述できない場合さえあり、人や機械が「計算を演ずるという行為」はもちろん写像とは異なるからである。 「写像」という概念が未発達で「計算」と「計算の仕方」の違いも曖昧であった時代に生まれた「算法」とか「演算」とかの言葉を用いるのが間違っているのであろう。
冒頭に記したとおり、計算機科学の分野ではアルゴリズムを「算法」とよぶこともあり、その場合には上記の意味での「算法」は「演算」とよぶ方がよいかもしれない。 しかし数学の分野では、上記の意味での「算法」という術語も昔から定着している。 むしろアルゴリズムを「算法」ではなく「計算手順」とする方が、意味からいっても先例を尊ぶ点でも、好ましいであろう。
