非専門的シンギュラリティー研究所

無限に動き続けるシステムを表す方法を AI なども使って考えていきます。

モノイド的項書き換え(2)

モノイド的項書き換え ChatGPT

「モノイド的単一化アルゴリズム(2) - エレファント・ビジュアライザー調査記録」と同様にやってみます。

$f: P(S) \to P(S)$ ( $P(S)$ は集合 $S$ の冪集合)に対して $f$ を $n$ 回繰り返したものを $f^n$ 、すべての $f^n(X)$ の和集合を $f^(X)$ とします。 $x \in S$ に対して $f^(\{x\})$ は何と呼べば良いですか

と入力すると以下の結果となりました。

このような構造では、 $f^*(\{x\})$ は関数 $f$ の作用を繰り返し適用して得られる元 $x$ に関連するすべての元を含む集合です。この集合には次のような名前が使われることがあります：
1. 軌道 (Orbit):
$x$ を出発点として $f$ を繰り返し適用して得られる要素全体の集合を指すとき、「軌道」という用語がよく用いられます。特に、関数 $f$ が写像の場合、これは「 $x$ の $f$ -軌道 (the $f$ -orbit of $x$ )」と呼ばれることがあります。
2. 到達可能集合 (Reachable Set):
$x$ を始点として $f$ を繰り返し適用することで到達可能な全要素の集合という観点から、「到達可能集合」という呼び方も適切です。
3. 閉包 (Closure):
$x$ を始点として $f$ によって生成される集合を $f$ の作用による閉包という文脈で表現することもあります。
適切な用語は、対象となる数学的文脈（例えば、集合論、離散数学、グラフ理論など）によって異なりますが、ここでは「軌道 (Orbit)」が最も一般的かつ簡潔な表現であると言えるでしょう。

項書き換えの場合を考えます。 $S$ を項全体の集合、 $f(X)$ は書き換え規則で変換された先の項すべての集合とします。このとき $x \in S$ に対して $f^*(\{x\})$ は何と呼べば良いですか

と入力すると以下の結果となりました。

項書き換えの場合において、 $f^*(\{x\})$ は、項 $x$ を出発点として書き換え規則 $f$ を繰り返し適用することで生成されるすべての項の集合を表します。このような集合には、以下のような名前が適切です：

1. 誘導閉包 (Derivation Closure)

項 $x$ から始まるすべての書き換え可能な項を含む集合という観点から、「誘導閉包」と呼ばれることがあります。これは、書き換え規則の反復適用による生成された項全体を強調する表現です。

2. 到達可能集合 (Reachable Set)

$x$ を始点とし、書き換え規則 $f$ によって到達可能なすべての項の集合という意味で、「到達可能集合」と呼ぶことも一般的です。この用語はグラフ理論やオートマトン理論と密接に関連します。

3. 書き換え閉包 (Rewrite Closure)

項書き換え規則の適用による閉包として、「書き換え閉包」という表現も適切です。これは特に書き換え規則の適用による生成集合であることを強調する場合に用いられます。

4. 項の生成系 (Generated Set of Terms)

項 $x$ を始点として書き換え規則によって生成される項の集合を、「生成系」とみなす表現です。特に形式言語やグラフ理論の文脈では、このような用語が用いられることがあります。
結論として、文脈に応じて「誘導閉包」や「到達可能集合」が特に適切である場合が多いですが、場合によっては「書き換え閉包」や「生成系」という言葉も自然に受け入れられるでしょう。

「群の語の問題」に関する項書き換えの場合を考えます。二項演算と単項演算と単位元をもつ代数的構造に最小限の群の書き換え規則を加えたシステムで、 $x \in S$ に対して $f^*(\{x\})$ は何を表していますか

と入力すると以下の結果となりました。

「群の語の問題」における項書き換えの設定では、項書き換え規則 $f$ は群の公理（結合法則、単位元の存在、逆元の存在）を表現したもので、これを用いて項の簡約や変形を行います。この場合、 $f^*(\{x\})$ は次のように解釈できます。

$f^*(\{x\})$ の意味

$x \in S$ から出発し、群の書き換え規則（簡約規則）を反復的に適用して生成可能なすべての項の集合を表します。具体的には、次の性質を持ちます：
1. $x$ と同値な項の集合:
項 $y$ が $f^*(\{x\})$ に含まれるのは、 $x$ と $y$ が群の公理の範囲内で同値（つまり同じ群の元を表している）である場合です。
2. $x$ が表す元の「語」全体:
群の元を特定の生成系で表したときに、 $x$ が表す群の元と同じ元を表すすべての語が含まれます。

具体例

群 $G$ の生成系 $\{a, b\}$ を考え、次の書き換え規則を与えるとします：
1. 単位元の規則: $e \cdot x \to x$ , $x \cdot e \to x$
2. 逆元の規則: $a \cdot a^{-1} \to e$ , $a^{-1} \cdot a \to e$
3. 結合法則の適用可能性（ただし明示的に書き換え規則としては指定しない）。
このとき、語 $x = a \cdot b \cdot a^{-1}$ に対して $f^*(\{x\})$ は、以下を含むすべての語になります：

書き換え後の語 $b$ （ $a \cdot a^{-1} = e$ により簡約）

他の等価な語 $a^{-1} \cdot b^{-1} \cdot (a \cdot b)$ など。

$f^*(\{x\})$ の意味論的解釈

項書き換えの視点での $f^*(\{x\})$ は、群論の文脈では以下の概念に対応します：

同値類 (Equivalence Class):

項 $x$ を出発点として、書き換え規則によって変換可能なすべての項を含む集合。

語の正規形 (Normal Form):

$f^*(\{x\})$ の中で最も簡約された形を取り出すことで、群の元を一意的に表現できる語が得られる場合があります。この場合、正規形に基づいて語の同値性が判断されます。

群の元:

結果として $f^*(\{x\})$ が表すのは、群 $G$ のある元（ $x$ によって表現される元）に他なりません。

まとめ

「群の語の問題」における項書き換えで $f^*(\{x\})$ は、群の元を表す語の同値類を表します。この同値類は、書き換え規則を反復適用することで得られるすべての項（語）から構成されます。その結果、これは群の元とその表現の全体像を示す重要な数学的対象になります。

【電子復刻版】bit 1988年04月号(通巻230号)

【電子復刻版】bit 1988年04月号(通巻230号)

共立出版

【電子復刻版】bit 1989年04月号(通巻242号)

【電子復刻版】bit 1989年04月号(通巻242号)

共立出版

新しいプログラミング・パラダイム

新しいプログラミング・パラダイム

共立出版

岩波講座ソフトウェア科学〈〔理論〕12〉計算モデルの基礎理論

岩波講座ソフトウェア科学〈〔理論〕12〉計算モデルの基礎理論

作者:井田哲雄
岩波書店