Minskyマシン

Minskyマシンは,1967年に Marvin Minsky によって著された著書『Computation: Finite and Infinite Machines』にて提案された.彼はこの中で,たった2つの自然数レジスタと非常に単純な命令構文のみで,チューリングマシンと同等の計算能力を有することを示した.これは計算可能性理論において,計算の最小要件の研究に大きな影響を与えた.

また,このモデルは後に counter machine[カウンターマシン]とも呼ばれ,形式意味論や計算論,または形式検証の研究で多用されることになる.

レジスタと状態空間

ミンスキー機械は,有限個の自然数レジスタをもつ.もっとも簡素な構成では2つのレジスタでチューリング完全性を持つことが知られている.

• レジスタ集合を $\mathcal{R} = \{R_1, R_2\}$ とする
• 各レジスタ $R_k$ の値は自然数：$R_k \in \mathbb{N}$
• プログラムカウンタ[命令位置] $i \in \mathbb{N}$ を導入する

したがって,機械の状態は以下のように定義される.\[S = (i, r_1, r_2) \in \mathbb{N} \times \mathbb{N} \times \mathbb{N}\]

ここで $i$ は現在実行中の命令のインデックス,$r_1, r_2$ はそれぞれのレジスタの値である.

命令集合

命令は以下の3種類から構成される.全体としてのプログラムは,命令の有限列 $P = (P[0], P[1], \dots, P[n])$ である.

インクリメント命令

$\text{INC}(R_k, j)$

• レジスタ $R_k$ の値を1増加させ、命令位置を $j$ に変更する
• 形式的定義：$R_k \mapsto R_k + 1$, $i \mapsto j$

デクリメント命令

$\text{DEC}(R_k, j_1, j_2)$

• $R_k = 0$ なら命令位置を $j_2$ に変更する
• $R_k > 0$ なら $R_k$ を1減らし,命令位置を $j_1$ に変更する
• 形式的定義\[\begin{eqnarray}R_k = 0 &\Rightarrow& i \mapsto j_2 \\ R_k > 0 &\Rightarrow& R_k \mapsto R_k - 1,\ i \mapsto j_1 \end{eqnarray}\]

停止命令[任意]

$\text{HALT}$

• マシンの実行を停止させる
• 停止状態への遷移：$S \mapsto $停止

状態遷移関数

命令 $P[i]$ に対して,状態 $S = (i, r_1, r_2)$ からの状態遷移関数 $\delta$ は以下のように定義される.\[\begin{cases}(j, r_1 + 1, r_2) & \text{if } P[i] = \text{INC}(R_1, j) \\(j, r_1, r_2 + 1) & \text{if } P[i] = \text{INC}(R_2, j) \\(j_1, r_1 - 1, r_2) & \text{if } P[i] = \text{DEC}(R_1, j_1, j_2),\ r_1 > 0 \\(j_2, r_1, r_2) & \text{if } P[i] = \text{DEC}(R_1, j_1, j_2),\ r_1 = 0 \\(j_1, r_1, r_2 - 1) & \text{if } P[i] = \text{DEC}(R_2, j_1, j_2),\ r_2 > 0 \\(j_2, r_1, r_2) & \text{if } P[i] = \text{DEC}(R_2, j_1, j_2),\ r_2 = 0 \\\text{停止} & \text{if } P[i] = \text{HALT}\end{cases}\]

この関数 $\delta$ を反復適用することにより,ミンスキー機械の実行を定義する.

Mathematics is the language with which God has written the universe.