利用者:NGiraffe/作業中の記事/語の問題

数学とコンピュータ・サイエンスにおいて、集合 S とその元を有限の長さで符号化する体系に対する語の問題(word problem)とは、符号化された二つの元が S の中で同じ元を定めるかどうかを決定する手続きについての問題である。一般に、この問題には構造を生成元と関係式による表示で与える抽象代数の分野で遭遇する(特に群に対する語の問題)。若干非形式的にいうと代数における語の問題は、「等式の集合 E と二つの元 x、y に対して、E の等式を項書き換え規則として使用し、 x を y に変形できるか？」と表される。

In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements is the algorithmic problem of deciding whether two given representatives represent the same element of the set. The problem is commonly encountered in abstract algebra, where given a presentation of an algebraic structure by generators and relators, the problem is to determine if two expressions represent the same element; a prototypical example is the word problem for groups. Less formally, the word problem in an algebra is: given a set of identities E, and two expressions x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions?

背景と動機[編集]

Background and motivation[編集]

数学においては、有限個の情報の集積で、ある集合の特定の元を記述したいことがしばしば起こる。集合が無限集合の場合が典型的である。この問題は特に計算数学に現れる。チューリングマシンのような、伝統的な計算モデルは非有界な格納領域を持ち、よって原理的には無限集合の元の関わる計算を実行できる。一方で、使用中の格納領域は個々の瞬間で有限であり、扱われる個々の元も有限の表示を持たなければならない。

Many occasions arise in mathematics where one wishes to use a finite amount of information to describe an element of a (typically infinite) set. This issue is particularly apparent in computational mathematics. Traditional models of computation (such as the Turing machine) have storage capacity which is unbounded, so it is in principle possible to perform computations with the elements of infinite sets. On the other hand, since the amount of storage space in use at any one time is finite, we need each element to have a finite representation.

諸般の事情から、個々の元を一意に符号化できるような記述体系がつねに可能もしくは期待できるとは限らない。このような一意性をもたない符号化体系を用いる際、二つの符号が同一の元を表しているかどうかを判定するアルゴリズムの存在性に疑問が起こるのは自然である。このようなアルゴリズムは符号化体系に対する「語の問題の解」と呼ばれる。

For various reasons, it is not always possible or desirable to use a system of unique encodings, that is, one in which every element has a single encoding. When using an encoding system without uniqueness, the question naturally arises of whether there is an algorithm which, given as input two encodings, decides whether they represent the same element. Such an algorithm is called a solution to the word problem for the encoding system.

The word problem in universal algebra[編集]

普遍代数における語の問題[編集]

代数においては、演算子の引数が有限であるとの仮定のもと、有限個の元から生成される無限代数を扱うことがある。この代数は生成元と演算による有限な符号化体系を自然にもつ。この場合「語の問題」は与えられた二つの表示に対してそれらが同一の元を表すか否かを決定する問題である。

In algebra, one often studies infinite algebras which are generated (under the finitary operations of the algebra) by finitely many elements. In this case, the elements of the algebra have a natural system of finite encoding as expressions in terms of the generators and operations. The word problem here is thus to determine, given two such expressions, whether they represent the same element of the algebra.

大雑把に言って、代数における語の問題は、等式の集合 E、式 x と y に対して、E の元を書き換え規則として x を y に、或いは逆方向に変形できるか？という問題になる^[1]。

Roughly speaking, the word problem in an algebra is: given a set of identities E, and two terms x and y, is it possible to transform x into y using the identities in E as rewriting rules in both directions?^[2]

語の問題は束にも現れる。この場合、同値な語の集合が自由束をなす、という形で語の問題の解が示されるかもしれない。

The word problem occurs in the study of lattices; there it may be shown that the word problem has a solution, namely, the set of all equivalent words is the free lattice.

最も重要で深く研究されたのは半群あるいは群に対する語の問題である。語の問題が解けない群は多数あることが判っており、二つの元の同値性を有限時間で判定するチューリングマシンはない(与えられた語の同値性を判定するアルゴリズムは存在するが、全ての同値性を発見するためには無限個のアルゴリズムが必要かもしれない)。

The most important and deeply studied case of the word problem is in the theory of semigroups and groups. There are many groups for which the word problem is not solvable, in that there is no Turing machine that can determine the equivalence of any two words in a finite time. (There do exist, however, algorithms to determine the equivalence of given words; it is just that one might require an infinite number of algorithms to find all equivalences).

自由ハイティング代数に対する語の問題は難しい^[3]。唯一知られているのは、一元生成の自由ハイティング代数は無限であり、一元生成の自由な完備ハイティング代数は存在して、自由ハイティング代数に一点を追加したものになる。

The word problem on free Heyting algebras is difficult^[4]. The only known results are that the free Heyting algebra on one generator is infinite, and that the free complete Heyting algebra on one generator exists (and has one more element than the free Heyting algebra).

References[編集]

^ Franz Baader and Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1998, p. 5
^ Franz Baader and Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1998, p. 5
^ Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)
^ Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)

[1] Franz Baader and Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1998, p. 5

[2] Franz Baader and Tobias Nipkow, Term Rewriting and All That, Cambridge University Press, 1998, p. 5

[3] Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)

[4] Peter T. Johnstone, Stone Spaces, (1982) Cambridge University Press, Cambridge, ISBN 0-521-23893-5. (See chapter 1, paragraph 4.11)

[1]

[2]

[3]

[4]