コンピュータシステムはすべて状態機械として理解できます。単純なコンピュータシステム（オペレーティングシステムなしでプログラムがCPU上で直接実行されるシステム）でさえ、三つの抽象化レベル（プログラム、命令セット、CPU）はすべて状態機械として解釈できます。
プログラムは状態機械である
C言語の構成要素：
- 変数：計算の対象
- 文：計算の操作フロー
- 入出力関数：変数と外部環境の相互作用
Cプログラムの状態機械モデル
状態集合：S={<V,PC>}
V = {v1,v2,v3,...} = プログラム内のすべての変数の値（グローバル変数とローカル変数を含む）
PC = プログラムカウンタ = 現在実行中の文の位置
励起イベント E={文}
PCが指す文を実行
状態遷移規則：
next:S×E→S
文のセマンティクス（意味論）
初期状態 S0=<V0, main関数の最初の文>
/* 1 */ int main() {
/* 2 */ int a = 1;
/* 3 */ int b = 2;
/* 4 */ int c = a + b;
/* 5 */ printf("c = %d\n", c);
/* 6 */ return 0;
/* 7 */ }
対応する状態遷移：
S = <a, b, c, PC>
S0 = <?, ?, ?, 2> // '?' は初期化されていないことを示す
S1 = <1, ?, ?, 3>
S2 = <1, 2, ?, 4>
S3 = <1, 2, 3, 5>
S4 = <1, 2, 3, 6> // "c = 3" を出力
S5 = <1, 2, 3, 終了>
Cプログラムは本当にmain()関数の最初の文から実行を開始するのでしょうか？
プログラムの動的挙動を理解するためにtraceツールを使用してみましょう。
int main(){return 0;}
straceツールを使用：
gcc a.c
strace ./a.out
この単純なプログラムが多くの操作を実行することがわかります。実際、このコードは単純な一行であり、直接return 0;するだけです。もし本当にmain関数から実行が開始されるなら、プログラムはすぐに終了するはずです。したがって、これらの操作はmain関数の実行前か、return後のいずれかで行われていると推測できます。
検証のために、無限ループを追加したプログラムを試してみましょう。
int main(){while(1); return 0;}
プログラムがここで停止することがわかります。これは、main関数の前に出力が行われていることを示しています。つまり、プログラムはmain()関数の最初の文から実行を開始するわけではないのです。
gdbデバッガを使用してさらに調査しましょう。
gdb a.out
starti
プログラムは即座に_start()関数で停止します。この_start()関数はソースコード内にはなく、別の場所に定義されています。これもmain()から実行が開始されないことを示しています。
ISO/IEC 9899:201x規格を参照すると：
実行環境は特別なC関数を呼び出す。
実行環境には2種類あります：スタンドアロン環境（freestanding）とホスト環境（hosted）
スタンドアロン環境
スタンドアロン環境では、この特別なC関数は実装によって決定されます。この関数がmain関数を呼び出します。
ホスト環境
ホスト環境では、この特別なC関数の名前はmainです。
規格は、ホスト環境でのこの関数をmainと定義しています。
プログラム実行に関する規格の記述から、一部の文の実行が副作用を引き起こし、実行環境の状態変化を招くことがわかります。これにより、Cプログラムが確かに状態機械であることが示されます。
CPUは状態機械である
CPU = デジタル論理回路 = 状態機械
デジタル論理回路 = 組合せ論理回路 + 順序論理回路
状態集合：S={<順序論理素子の値>}
具体的にはレジスタ、メモリ、フリップフロップなど
励起イベント E={組合せ論理}
状態遷移規則：
next:S×E→S
設計における組合せ論理回路によって決定
根拠：アーキテクトの設計文書
初期状態 S0=<リセット時の順序論理素子の値>
命令セットは状態機械である
命令セットはソフトウェアとハードウェアの間のインターフェースです。
命令セットはCPUが命令を実行する動作を定義するマニュアル仕様です。
状態集合：S={<R,M>}
R={PC,r0,r1,r2,...}
PC = プログラムカウンタ = 現在実行中の命令の位置
M = メモリ
励起イベント E={命令}
PCが指す命令を実行
状態遷移規則：
next:S×E→S
命令のセマンティクス（意味論）
初期状態 S0=<R0,M0>
Cプログラムによる命令の理解
1から100までの合計を計算する命令シーケンス：
// PC: 命令 | ラベル: 文
0: li r1,0 | pc0: r1 = 0;
1: li r2,0 | pc1: r2 = 0;
2: li r3,100 | pc2: r3 = 100;
3: addi r2,r2,1 | pc3: r2 = r2+1;
4: add r1,r1,r2 | pc4: r1 = r1+r2;
5: blt r2,r3,3 | pc5: if(r2 < r3) goto pc3; // より小さい場合に分岐
6: j 6 | pc6: goto pc6;
命令は状態機械の状態を変更するための励起イベントです。
命令の二つの表現
- 記号表現 - プログラマ向け
- 符号化表現 - 回路設計者向け
命令セットマニュアルは、状態機械の状態遷移規則を定義することによって、概念的に抽象的なコンピュータが持つプログラム利用可能な機能を記述しています。
コンピュータ上でのプログラムの実行
アセンブリ
アセンブリ命令 = 命令の記号表現
アセンブリプログラム = 命令セット状態機械を駆動する入力
アセンブリプログラムの実行 = 命令セット状態機械の状態遷移