Minskyのレジスタ機械

$q=0,1,\dots,a$ について、$q$ 回目に $M_0$ に来たときの様相が $(M_0;a-q,cq)$ であることを $q$ についての帰納法で示す。$q=0$ は仮定である。$q< a$ のとき $M_0$ で $1$ を引いて $M_1$ へ進み、$M_1,\dots,M_c$ で $R_1$ に $c$ を足して $M_0$ へ戻るので、$(M_0;a-q-1,c(q+1))$ になる。$q=a$ では $R_0=0$ なので $N_0$ へ進む。同様に、$N_0$ と $N_1$ の繰り返しは $R_1$ の中身を $1$ ずつ $R_0$ へ移し、$(N_0;u,ca-u)$（$u=0,1,\dots,ca$）を経て $(e;ca,0)$ に達する。$\square$

$a=qc+s$（$0\le s< c$）と割り算する。$D_0$ から $D_c$ までの 1 周は $R_0$ から $c$ を引いて $R_1$ に $1$ を足すので、帰納法により、$t\le q$ 回目に $D_0$ に来たときは $(D_0;a-tc,t)$ であり、周回 $q$ の中で $D_i$ に来たときは $(D_i;s-i,q)$ である（$0\le i\le s$）。$D_s$ で $R_0=0$ となり、0 の側へ進む。
$s=0$ なら $Y_0$ へ進む。$Y_0,Y_1$ の繰り返しは $R_1=q$ を $R_0$ へ移すので $(e_{\mathrm{y}};q,0)=(e_{\mathrm{y}};a/c,0)$ に達する。$s\ge1$ なら $Z_s$ へ進み、$Z_s,\dots,Z_1$ で $R_0$ に $s$ を足して $(W_0;s,q)$ になる。$W_0$ から $W_c$ までの 1 周は $R_1$ から $1$ を引いて $R_0$ に $c$ を足すので、$q$ 周の後 $(W_0;s+qc,0)$ となり、$(e_{\mathrm{n}};a,0)$ に達する。$\square$

構成． $P$ の各命令 $I_\ell$（$\ell< n$）に対し、部品 $B_\ell$ を次のように定める。$I_\ell=\mathrm{INC}(r,j)$ なら $B_\ell:=\mathrm{MUL}_{p_r}$、$I_\ell=\mathrm{DEC}(r,j,j')$ なら $B_\ell:=\mathrm{DIV}_{p_r}$ とする。$B_0,\dots,B_{n-1}$ をこの順に並べ、$B_\ell$ の最初の命令の番号を $b_\ell$ とし（$b_0=0$）、$b_n:=\widehat n$（全体の長さ、すなわち停止）とおく。そのうえで、$\mathrm{MUL}$ の出口 $e$ を $b_j$ に、$\mathrm{DIV}$ の出口 $e_{\mathrm{y}}$ を $b_j$ に、$e_{\mathrm{n}}$ を $b_{j'}$ に替える。命令は $R_0,R_1$ しか使わないので、$\widehat P$ は 2 レジスタのプログラムである。
1 段の模倣． $(\ell,\rho)$ が $P$ の停止様相でない様相で、その次の様相を $(\ell_1,\rho_1)$ とする。$\widehat P$ を $(b_\ell;\gamma(\rho),0)$ から動かすと、ほかの $b_{\ell''}$ を通らずに有限回で $(b_{\ell_1};\gamma(\rho_1),0)$ に達することを示す。部品 $B_\ell$ は、部品の命令の行き先の番号を $b_\ell$ だけずらし、出口だけを替えた番号にして置いたものである。Church–Turingのテーゼ の記事の補題「連結と付け替え」の 3 と同じ段数についての帰納法（出口が 2 つの $\mathrm{DIV}$ でも同じ）により、部品 $B_\ell$ は単独で動かしたのと同じ変化をし、出口に当たる段で替えた番号へ進む。$I_\ell=\mathrm{INC}(r,j)$ なら、lem-mrm-mul により $(b_j;p_r\gamma(\rho),0)$ に達し、$p_r\gamma(\rho)=\gamma(\rho+\mathbf{e}_r)=\gamma(\rho_1)$、$j=\ell_1$ である。$I_\ell=\mathrm{DEC}(r,j,j')$ なら、lem-mrm-div を使う。$\rho(r)>0$ のときは $p_r\mid\gamma(\rho)$ なので $(b_j;\gamma(\rho)/p_r,0)=(b_j;\gamma(\rho-\mathbf{e}_r),0)$ に、$\rho(r)=0$ のときは $p_r\nmid\gamma(\rho)$ なので $(b_{j'};\gamma(\rho),0)$ に達する。どちらも $(b_{\ell_1};\gamma(\rho_1),0)$ である。
全体． $P$ の $(0,\rho)$ からの計算を $(\ell_t,\rho_t)$ とする。1 段の模倣を繰り返すと、$\widehat P$ の $(0;\gamma(\rho),0)$ からの計算は $(b_{\ell_t};\gamma(\rho_t),0)$ を順に通る。$P$ が $t$ 段目で初めて停止様相 $(n,\rho')$ に達するなら、$\widehat P$ は $(b_n;\gamma(\rho'),0)=(\widehat n;\gamma(\rho'),0)$ に達して停止する。それまでの途中の様相の番号は $\widehat n$ でないので、それより前には停止しない。$P$ が停止しないなら、$\widehat P$ は番号 $b_{\ell_t}$（$\ell_t< n$）を無限回通り、そのどれも停止の番号ではないので停止しない。$\square$

Church–Turingのテーゼ の記事の定理「μ再帰関数のレジスタ機械による計算」により、$f$ を整った形で計算するプログラム $P$ がある。同記事の部品 $\mathrm{MOV}(0,1)$（$R_0$ の中身を $R_1$ へ移す）と $\mathrm{CLR}(1)$（$R_1$ を空にする）を使い、$Q:=\mathrm{MOV}(0,1);P;\mathrm{CLR}(1)$ とおく。$R_0=x$、ほかが $0$ の様相から $Q$ を動かすと、$\mathrm{MOV}(0,1)$ の後は $R_1=x$、ほかが $0$ で、これは $P$ の入力 $x$ の初期様相である。同記事の補題「連結と付け替え」の 1 により、$Q$ が停止するのは $P$ が停止するとき、すなわち $f(x)$ が定義されるときちょうどである。このとき整った形の定義により $P$ の停止様相は $R_0=f(x)$、$R_1=x$、ほかが $0$ であり、$\mathrm{CLR}(1)$ の後は $R_0=f(x)$、ほかが $0$ になる。$Q$ に thm-mrm-two-register を当てはめて得る 2 レジスタのプログラムを $\widehat Q$ とすると、初期の符号は $\gamma(x\mathbf{e}_0)=2^x$、停止したときの符号は $\gamma(f(x)\mathbf{e}_0)=2^{f(x)}$ である。$\square$

$K$ を 停止問題 の記事の定義「停止問題」の自己停止集合とする。同記事の定理「停止集合は半決定可能」により、$K=\operatorname{dom}g$ となる Turing 計算可能な部分関数 $g$ があり、Church–Turingのテーゼ の記事の系「計算のモデルの一致」により $g$ は μ再帰関数である。$g$ に cor-mrm-minsky を当てはめて得る 2 レジスタのプログラムを $P$ とすると、すべての $x$ について
$$ x\in K\iff 2^x\in H_P $$
である。$H_P$ が決定可能なら、$\chi_K(x)=\chi_{H_P}(2^x)$ は計算可能な関数の合成になる（$\chi_{H_P}$ は計算のモデルの一致により μ再帰関数、$x\mapsto2^x$ は原始再帰関数であり、μ再帰関数は合成で閉じている）。これは同記事の定理「停止問題の決定不能性」に反する。後半は、前半の $P$ を固定すれば判定の手順が $H_P$ の判定になることから従う。$\square$

要点：レジスタが正である間は、命令の進み方は中身によらず決まる。その道筋は最終的に周期的になり、1 周での中身の増減の符号で場合が分かれる。