このブログの更新は Twitterアカウント @m_hiyama で通知されます。
Follow @m_hiyama

メールでのご連絡は hiyama{at}chimaira{dot}org まで。

はじめてのメールはスパムと判定されることがあります。最初は、信頼されているドメインから差し障りのない文面を送っていただけると、スパムと判定されにくいと思います。

参照用 記事

デジタルなモノイド

最近、オートマトン(状態遷移系)を加群とみなす話をしてます(コレとかアレとか)。オートマトンと加群を完全に並行に論じられるか?というと、そうでもないのですが、おおざっぱなアナロジーをたどるのは意味があるような気がします。

このアナロジーにおいて、多元環(可換とは限らない代数)に相当するのがモノイドで、多元環上の加群に相当するのが“モノイドが作用する状態空間”、つまりオートマトンです。コンピュータと計算への応用では、任意のモノイドを考えるより、ある程度の制限を付けたほうが議論が簡単になります(当たり前のことだが)。

それ以上分解できないモノがあること

有限生成や自由モノイドに拘るのは得策とは思えないのですが、有限アルファベットから生成された自由モノイドと似た感じは欲しいです。「似た感じ」がどうにも曖昧ですが、なんつーか「デジタルっぽい」モノイドですね。いくつかの条件を考えてみました。

  1. 0(吸収元)を持つ。これは必須ではないですし、デジタルっぽいとは関係ないのですが、システムが壊れることを表現するのに0があると便利だと思います。
  2. 零因子を持たない。「xy = 0 ⇒ x = 0 または y = 0」のことです。対偶を取ると「x ≠ 0 かつ y ≠ 0 ⇒ xy ≠ 0」で、正常処理を逐次実行しても正常処理であることなので、割と自然かな、と。
  3. 単位は分解できない。「xy = 1 ⇒ x = 1 かつ y = 1」のことです。これはかなり強い条件ですが、デジタルっぽい気がします。

モノイドの要素aが、「a = xy ⇒ x = 1 または y = 1」を満たすとき原子的またはと呼びましょう。「単位は分解できない」は1が原子的であることと同じです。原子的な要素の全体が、モノイドの生成系になっていると扱いがラクチンそうです。

  • Mは原子的な要素の全体から生成される。

Mがすぐ上の条件を満たすなら、M内で原子的な要素は十分あるわけですが、原子的な要素の絶対数はあまり多くないほうがいいでしょう。次の条件も入れたほうがいい時もあるかな。

  • Mの原子的な要素は高々可算個である。

Mの“大きさ”に関する制約は、ときに足枷になるときもあるので、採用するかどうかは場合によりけりでしょうがね。

基礎可換モノイド

非可換な代数上の加群を考える場合でも、基礎となる可換環を固定する場合は多いので、オートマトンのときも基礎となる可換モノイドを固定したほうが都合がいいかもしれませんね。

一番簡単な可換モノイドは、自明なモノイド {1} です。簡単すぎて、あまり意味がないですが、コレ。可換モノイド {0, 1} は一元体F1の実体です。0をシステムが壊れることに対応させると、{0, 1} を基礎の係数域にするのは意味があるでしょう。

実際によく使うのは、ττ = τ というベキ等な要素を入れた {1, τ} です。τは無音記号(silent symbol)とかタイムフィラーと呼ばれるものです。入力も出力もないことを表す記号ですが、τにより遷移が引き起こされることもあります。これに0も入れた {0, 1, τ} が基礎可換モノイドにふさわしいような。

Kを、いま述べた基礎可換モノイド {0, 1, τ} だとして、K-モノイドMとは、j:K→M というモノイド射を持ったモノイドMです。jをモノ射に限れば、K⊆M だと(気分としては)思えます。モノ射の条件を付けたほうがいいのかどうか? よくワカラナイのですが、モノ射のほうが無難な感じです。

MとNがK-モノイドのとき、f:M→N が、j;f = j ならK-モノイド射です。集合圏内の可換モノイドKを固定して、K-モノイドの圏を定義できます。


あまり条件を付けると、直積や直和のような構成がやりにくくなるのですが、具体例との対応をとるために、ある程度の条件はあってもいいと思っています。