ソフトウェアシステムを状態遷移機械（state transition machine）によってモデル化することは、やっぱり非常に大事なことだなー、と感じたりする今日この頃。んで、状態遷移の話をしようかな、という気分になりました。続き物にはしませんが、散発的に何回か書くと思います（たぶん）。
内容：
- 空間と運動
- アルファベットと遷移
- 実例：カウンター
- 非決定性遷移
- 非決定性の事情
●空間と運動
あるシステムが取り得るすべての状態の集合を状態空間と呼びます。「空間」という言葉を使ったいきがかり上、個々の状態のことを状態点と呼ぶこともあります。例えば、onとoffのスイッチなら{on, off}が状態空間です。
「取り得るすべての状態」は、現実的というよりは“概念的に”取り得るすべての値のことです。例えば、理想的な温度計を考えて、摂氏により計った実数値を“状態”と考えれば、S = {x∈R | x ≧ -273.15} （Rは実数全体）が状態空間です。この例は、現実的ではなく概念的（理想的）ですね -- それでもいいのです。
状態空間が有限離散的である例がよく引き合いに出されますが、状態空間の有限性を今回は仮定しません。すごく大きな有限は無限として扱ったほうがいいときもあるし、実際に無限の状態空間もあります。例えば、力学（運動学）の質点の運動も状態遷移の枠組みで取り扱えますが、そのときの状態空間（相空間）は連続的に無限です。理想的温度計も無限状態空間ですね。
ある時点で、システムは特定の状態を持つので、状態空間の1点を指定できます。この現時点で特定された状態点を現状態（current state）と呼びます。現状態は時刻によって決まるので、時間の流れに沿って現状態も変化します。つまり、状態空間において運動の軌跡が描かれます。
この運動を取り扱う力学が、状態遷移機械の理論ってことになります。ただし、時間の概念は表だっては出てきません。外部からの刺激（stimulus）と、その刺激に対する内部的な反応（response, reaction）という形で定式化します。
●アルファベットと遷移
外部からの刺激は記号として表現します。刺激、つまり記号の集まりをアルファベットと呼びます。例えば、2つの記号turnOn, turnOffからなる{turnOn, turnOff}はアルファベットの例です。状態空間同様、アルファベットも有限性を仮定しません。
状態空間とアルファベットが与えられているとき、反応を記述する(状態点1, 記号, 状態点2)の3つ組を遷移（transition）と呼びます。状態空間={on, off}、アルファベット={turnOn, turnOff}として、遷移を列挙してみましょう。
- (on, turnOn, on)
- (on, turnOff, off)
- (off, turnOn, on)
- (off, turnOff, off)
これですべてです。見やすいように、(状態点1, 記号, 状態点2)の代わりに、状態点1 -(記号)→ 状態点2も使うことにします。この書き方では：
- on -(turnOn)→ on
- on -(turnOff)→ off
- off -(turnOn)→ on
- off -(turnOff)→ off
いまの例と同じ状態空間={on, off}に、アルファベットは{toggle}として、次の遷移を考えることもできます。
- on -(toggle)→ off
- off -(toggle)→ on
課題： 上の2つの例に対して、状態点をマル、遷移を矢印で描いた図を描いてみてください。こんな図を状態遷移のグラフ／ダイヤグラム／チャートなどと呼びます。
●実例：カウンター
状態空間がN = {0, 1, 2, 3, ...}、アルファベットが{up, down, reset}であって、次の遷移を持つ状態遷移機械を考えましょう。
- n -(up)→ n + 1
- n -(down)→ n - 1 （n > 0 のとき）
- 0 -(down)→ 0
- n -(rese)→ 0
これをカウンターと呼ぶのは自然でしょう。
課題： カウンターに対して、状態点を{0, 1, 2, 3}に制限した状態遷移グラフを描いてください。グラフに多重辺（同じノード間に複数の辺）、ループ（1つのノードから出て戻る辺）が現れますね。
さて、up, up, down, up とか、down, reset, up とかの記号の列を考えます。これは、時間に沿った刺激の履歴と考えられます。記号列が現状態の変化を引き起こします。“現状態の変化＝運動”を駆動する要因ですから、質点の運動でいえば、力＝加速度に相当します。初期値（例えば0）と記号列（例えばup, up, down, up）から軌跡や到達点を求めることは運動の解析にあたりますね。
●非決定性遷移
状態遷移機械では、遷移が未定義であるとか、非決定性であるとかの状況を扱います。例えば、0 -(down)→ 0 という遷移はなんか人為的・無理矢理な印象があります。むしろ、状態点0と記号downの遷移先は未定義としたほうが自然でしょう*1。
非決定性とは、遷移先に複数の可能性を許すものです。例えば、カウンターのupが、
- n -(up)→ m ただし、n < m ≦ n + 3
というようなルールで決まっているとしましょう。具体的には、
- 5 -(up)→ 6
- 5 -(up)→ 7
- 5 -(up)→ 8
のどれも起こりえるし、どれが起こるかは分からないということです。先に出した“遷移先が未定義”も、遷移先の可能性が0個という解釈もできます。
なぜ、非決定性遷移を考えるのでしょうか？ 次のような理由が挙げられるでしょう。
- 実際に遷移先が不確定である。
- 仕様としての許容範囲を示す。
- アルファベットの集約の結果。
●非決定性の事情
「実際に遷移先が不確定である」例としては、例えばupの実行が宇宙からの微弱な放射線の影響を受けているとか（ナンジャソリャ？）。あるいは、upがとてもとても複雑なプログラムで実装されていて、誰も正確な動作を知らない、とか。
「仕様としての許容範囲を示す」とは、up, down, resetをこれからプログラムで実装するとして、
- upは、状態点の値を1以上3以下の範囲で増加させる。
のように指定することです。実際のところ、仕様というのは許容範囲とか、実装者に任せる部分があるので、決定的／確定的には記述しない（できない）ことも多いのです。
「アルファベットの集約の結果」とは、ほんとはup1, up2, up3という3つの記号と決定性の遷移があったのだけど、up1, up2, up3をまとめてupという1つの記号で代表させる、というような状況です。upの遷移は、up1, up2, up3の遷移を寄せ集めたものなので、その結果として非決定性が生じます。アルファベットや状態点を集約（グループ化）して規模を縮小させるテクニックは実際にもよく使います。規模縮小の代償として非決定性を許容しなくてはならないのです。
*1:実は、「未定義」の定義が問題になるのですが、いまは触れません。
