Rewriting Systems on Arbitrary Monoids

あなたは、あるルールに従って一つのものを別のものへと変えていくパズルを解こうとしているところだと想像してください。コンピュータサイエンスや数学の世界では、これは通常、文字の列（辞書にある単語のようなもの）を使って行われます。もし「cat」という単語があり、「cat」は「dog」になるというルールがあるなら、それらを入れ替えることができます。これは、文字列の書き換え（String Rewriting）と呼ばれる、伝統的な手法です。

しかし、この論文の著者であるエドゥアルド・マガリャンイス（Eduardo Magalhães）は、シンプルながらも深遠な問いを投げかけます。「もし、私たちが単なる『言葉』を扱っているのではないとしたらどうだろうか？」 もし、私たちが言葉とは全く見えない数字や図形、あるいは抽象的な概念を扱っているとしたらどうなるのでしょうか？

以下に、日常的な比喩を用いたこの論文の主要なアイデアの解説をまとめます。

1. 問題点：「言葉」にこだわりすぎること

伝統的な書き換えシステムは、**自由モノイド（Free Monoids）**の上でしか機能しません。自由モノイドとは、巨大で空っぽの倉庫のようなもので、そこでは箱（文字）を一直線に積み重ねることしかできません。組み合わせ方は、それらを繋ぎ合わせることだけです。

• 問題点： 論文は、これが制限されすぎていると主張しています。それは、壁のない倉庫の中でしか家具の配置換えができないと言っているようなものです。現実の世界（そして論理学）では、独自の内部ルールを持つ構造（例えば、「12 + 1 = 1」となる時計や、「アリス + ボブ」が単なる「グループ」となる友人関係など）を扱うことがよくあります。
• 論理のギャップ： 著者は、「自由な倉庫であること」というのは、論理学の言語において非常に特殊で定義が難しいルールであることを指摘しています。標準的な論理ツールを用いてこれらのシステムを研究しようとすると、「自由（free）」という概念をシステム内部で簡単に定義できないため、行き詰まってしまうのです。

2. 解決策：モノイダル書き換えシステム (MRS)

著者はモノイダル書き換えシステム (Monoidal Rewriting Systems: MRS) を導入します。

• 比喩： 単に文字を列に並べるのではなく、**道具箱（モノイド）**を持っていると考えてください。この道具箱には、道具を組み合わせるための特定の方法（乗法）があります。
  • 文字列システムでは、「A」と「B」を繋げて「AB」にすることしかできません。
  • MRSでは、道具箱のルールに従う限り、道具箱内のあらゆる二つの要素を組み合わせることができます。例えば、あなたの道具箱が「足し算をする数字の集合」であったり、「重なり合う図形の集合」であったりするかもしれません。
• 転換： 論文はこう言っています。「すべてを『言葉』であると決めつけるのはやめよう。ルールが対象そのものに対して直接機能するようにしよう」。これにより、システムはより柔軟になり、記述される構造に対して「内部的」なものになります。

3. 「完璧な」状態：ノイター（停止性）と合流性

どのような書き換えゲームにおいても、達成したいことが二つあります。

1. ノイター（Noetherian / 停止性）： ゲームは最終的に終わらなければなりません。ループの中で永遠に変化し続けてはいけません。（例：「A」を「B」に変え、「B」を「A」に戻すというルールが永遠に繰り返されるような状態はダメです）。
2. 合流性（Confluent / 一貫性）： どの順番でルールを適用したとしても、最終的には同じ結果に辿り着かなければなりません。（例：散らかった部屋を片付ける際、靴下を先に片付けるか本を先に片付けるかに関わらず、部屋は同じように綺麗になるべきです）。

システムがこれら両方を備えているとき、どんなに乱雑な入力であっても、それを一意の「正規形（Normal Form）」（その対象の最もクリーンで単純なバージョン）へと還元することができます。

4. 大きな繋がり： 「翻訳機」 (Biadjunction)

この論文は、二つの世界の間にある架け橋を築きます。

• 世界 A： 乱雑でルールが多い、書き換えシステム（MRS）の世界。
• 世界 B： 清潔で単純な、モノイド（最終的な構造）の世界。

著者は、双方向に機能する**「翻訳機」**（数学的な道具である「双随伴/biadjunction」）を作成しました。

• ルールから構造へ： ルールが手元にあれば、翻訳機はその中に隠された「クリーンな」構造（既約なモノイド）を見つけ出します。
• 構造からルールへ： クリーンな構造（例えば数字の「5」）があれば、翻訳機はその構造を生成する「標準的な」ルールセットを構築できます。

メタファー： 彫刻（モノイド）を想像してください。

• 一つの説明方法は、「これは粘土で作られている」と言うことです（構造）。
• もう一つの説明方法は、指示書を与えることです：「塊を取り、平らにし、円形に切り取り、縁を滑らかにする」（書き換えシステム）。
• この論文は、これら二つの記述が完璧に結びついていることを証明しています。指示書から彫刻へ、そして彫刻から「最高の指示書」へと、情報を失うことなく行き来することができるのです。

5. 「ティッツェ（Tietze）」変換： 魔法の杖

最後に、この論文はトリッキーな問いに答えます。「もし、同じ彫刻を作るための二つの異なるルールセットがあった場合、それらはどのように関連しているのか？」

かつての文字列書き換えの世界には、一つのルールセットを別のルールセットへと変えることができる、**ティッツェ変換（Tietze Transformations）**と呼ばれる有名な操作がありました。著者は、このより広い世界のために、**一般化された基本ティッツェ変換（Generalized Elementary Tietze Transformations: GETTs）**を考案しました。

• 比喩： 同じケーキを作るための二つの異なるレシピがあるとします。
  • レシピ A：「小麦粉、砂糖、卵を混ぜる」。
  • レシピ B：「乾燥した材料を混ぜ、次に濡れた材料を混ぜ、それから焼く」。
  • 見た目の手順は違っても、出来上がるケーキは同じです。
• 結果： 論文は、有効なレシピ（ノイターかつ合流的なMRS）であれば、どのようなものであっても、一連の「GETT操作」を用いることで、同じ結果を生む他の有効なレシピへと変換できることを証明しています。
  • 操作 1： すでに成立しているルールを追加する（冗長なルール）。
  • 操作 2： 他のルールによって既にカバーされているルールを取り除く。
  • 操作 3： ステップを説明するために、新しい材料（記号）を導入する。
  • 操作 4： 特定の部分に焦点を当てることで、システム全体を簡略化する複雑な操作。

まとめ

この論文は、「書き換え（ルールに基づいて何かを変えること）」という概念を、「言葉」という制約から解放します。それは以下のことを示しています。

1. これは単なる文字列だけでなく、あらゆる数学的構造に対して行うことができる。
2. ルールと結果の間には、完璧な論理的架け橋が存在する。
3. 同じ結果を生み出す二つのルールセットは、特定の普遍的な操作を用いて、互いに変換可能である。

これは、家を「レンガのリスト（文字列）」として記述することもできれば、「設計図（モノイド）」として記述することもできることに気づくようなものです。そして、あらゆる設計図にはそれを建てるための唯一無二の完璧な指示書が存在し、あらゆる指示書は唯一の設計図へと導かれるということを、数学的に証明しているのです。