日記 (2026 年 1 月 14 日)

前回までは、 「計算できる」 ことを定式化するためのアプローチとして、 限られた操作で閉じた関数のクラスを考え、 結果的に一般再帰関数のクラスを得た。 今回からは、 より直接的に 「計算」 というプロセスを扱う形式的な機械を考えることにする。 形式的な機械というと Turing マシンを導入するのが伝統的だが、 ここでは Enderton†1 に倣って、 より現代のコンピュータに近く動作が直感的なレジスタマシンを導入することにする。

レジスタマシンとは、 名前の通りレジスタを備えた抽象的な機械のことで、 このレジスタを特定の手続きに従って書き換えていくことで計算を行う。 まずはレジスタを定義しよう。

定義上、 メモリは自然数で添字付けられており、 すなわちレジスタは無限個ある。 しかし、 「有限個を除いて 0 であるような」 という条件を課していることからも分かるように、 これはあくまで 「計算をするのに十分な個数のレジスタが常に確保されている」 という意味である。 計算の途中で真に無限個のレジスタを使うことはなく、 十分大きな番号以降のレジスタを触ることはない。

さて、 レジスタマシンはこのレジスタを操作することで計算を行うが、 その操作としては次の 4 種類を考える。

レジスタマシンはプログラムを渡されると、 まずプログラムの最初 (0 番目) の命令を見る。 以降は、 そのときに見た命令に従って、 必要であればレジスタの数を書き換えた後に次に見る命令を決めることを繰り返す。 各命令の意味は次の通りである。

• incr を見た場合、 r 番目のレジスタの値を 1 だけ増やし、 プログラム上の次の命令を見る。
• decr を見た場合、 r 番目のレジスタの値が 0 であれば、 何もせずにプログラム上の次の命令を見る。 r 番目のレジスタの値が正であれば、 その値を 1 だけ減らし、 プログラム上の次の次の命令を見る。 すなわち、 この命令は場合分けも兼ねている。
• forwardq を見た場合、 何もせずに、 プログラム上の q 個先の命令を見る。
• backwardq を見た場合、 何もせずに、 プログラム上の q 個前の命令を見る。

各命令には実行後にどの命令を見るべきかが明示されている。 この際、 次に見るべき命令が存在しない場合がある。 例えば、 inc0 だけから成るプログラムを実行すると、 レジスタマシンはまず 0 番目のレジスタの値を増やした後、 その次の命令を見ようとするが、 次にはもう命令はない。 また、 backward5 だけから成るプログラムを実行すると、 レジスタマシンは次にこの 5 個前の命令を見ようとするが、 そもそもこれが最初の命令なので 5 個前の命令など存在しない。 このように次に見るべき命令がなかったら、 プログラムの実行は終了したということにする。 これが唯一の終了条件である。

しかし、 一概に 「次に見るべき命令がない」 と言っても、 inc0 と backward5 とでは意味合いが異なる。 inc0 の実行では、 命令の定義に従って直後の命令を見ようとしたわけだが、 これが最後の命令であるがために見るべき命令が存在しない状況になった。 つまり、 プログラム全体の実行が最後まで辿り着いた結果として次に見るべき命令が存在しない状況になったと考えられるため、 これは正常な終了と見なせるだろう。 しかし、 backward5 の実行では、 この 5 個前 (つまり −5 番目) という異常な場所を見ようとして、 命令が存在しない状況になった。 これは、 そのような変な場所を見させようとしたプログラムが異常だったと言えるため、 この場合はエラーによる終了と見なすのが自然に思える。 この違いを明確にしておこう。

ちなみに、 プログラムの末尾には end のような特殊な命令を常に追加することにして、 レジスタマシンが end を見たらそこで正常終了と見なし、 end を含めても存在しない命令を見ようとしたら異常終了と見なす、 と考えても同じことである。 こちらの解釈の方が直感的かもしれない。

なお、 プログラムの実行は永遠に (正常にも異常にも) 終了しない可能性もあることにも注意したい。 例えば、 forward0 だけから成るプログラムを実行すると、 レジスタマシンは次に 0 個先の命令を見ることになるが、 それは forward0 自身なので、 永遠に forward0 を見続けることになる。 すなわち、 次に見るべき命令が存在しない状況にはならないため、 このプログラムの実行は永遠に終了しない。

さて、 ここまでレジスタマシンの動作を自然言語で述べてきたが、 もう少し数学的に厳密な見方もしておこう。 レジスタマシンはレジスタをもっており、 このレジスタはプログラムの実行中に内容が書き換わる。 一方で、 レジスタマシンは 「プログラム上の何番目の命令を見るか」 という情報も保持しており、 これもプログラムの実行中に変化する。 これを 「ポインタ」 と呼ぶことにしよう。 すると、 レジスタマシンの状態はメモリとポインタの対で完全に決定する。 これを 「状況」 と呼ぶことにしよう。

すると、 プログラムの命令とはこの状況を別の状況に変化させるものと見なすことができる。 したがって、 プログラム 󰒝:=(c0,⋯,cl−1) を実行するレジスタマシンの動作は、 メモリ 󰒩:=(xr)r とポインタ p の対である状況 (󰒩,p) を受け取って、 それを 1 ステップ実行した後の状況 (󰒩󰎘,p󰎘) を返す写像 next󰒝 として定式化できる。 ここで便宜上、 すでに実行が終了している (すなわちポインタが指す命令が存在しない) 場合でもさらに 1 ステップの実行が可能であると見なし、 その場合は状況は変化しないものとする。 すると next󰒝 は、 next󰒝(󰒩,p) := { ((x0,⋯,xr−1,xr+1,xr+1,⋯),p+1) (cp=incr) (󰒩,p+1) (cp=decr,xr=0) ((x0,⋯,xr−1,xr−1,xr+1,⋯),p+2) (cp=decr,xr>0) (󰒩,p+q) (cp=forwardq) (󰒩,p−q) (cp=backwardq) (󰒩,p) (cp が存在しない) と書ける。 さて、 初期のメモリを 󰒩 として、 n ステップ後のレジスタマシンの状況を configat󰒝(󰒩,n) と書くことにしよう。 するとこれは、 next󰒝 を再帰的に呼び出すことで、 configat󰒝(󰒩,0) = (󰒩,0) configat󰒝(󰒩,n+1) = next󰒝(configat󰒝(󰒩,n)) と定めることができる。 これを使えば、 プログラムが n ステップで終了することは、 configat󰒝(󰒩,n) の右側成分が負になるか l 以上になることだと言える。 特に、 n ステップで正常終了することは、 configat󰒝(󰒩,n)=l が成り立つことだと言える。 したがって、 この正常終了するときのステップ数を n󰒝∞(󰒩) と書けば、 正常終了時の状況は configat󰒝(󰒩,n󰒝∞(󰒩)) として取り出せる。

このようにレジスタマシンの動作は数学的に厳密に述べられるとはいえ、 形式化しすぎても直感的に理解しにくくなってしまうので、 以降はレジスタマシンの動作は自然言語で説明することにする。 もし厳密性が恋しくなったら、 適宜ここで述べた表現に戻ってきて議論を書き直そうとしてみてほしい。

さて、 形式化についてはこの辺りにしておいて、 具体的なプログラムを 1 つ見てみよう。 最初のレジスタを (5,0,0,⋯) として、 次のプログラムを実行することを考える。 dec0 forward3 inc1 backward3 まず初めに dec0 が実行されるが、 0 番目のレジスタの値は現在 5 であるため、 これが減って 4 になり、 この後は次の次の命令を見ることになる。 その命令とは inc1 であるから、 これにより 1 番目のレジスタの値が増えて 1 になる。 次の命令は backward3 であるから、 これによりポインタは 3 つの前の命令すなわち dec0 に戻る。 すると最初と同様に、 0 番目のレジスタがまた減って 3 になり、 次に 1 番目のレジスタがさらに増えて 2 になり、 また最初に戻る。 これが何回か繰り替えされると、 0 番目のレジスタが 0 になり 1 番目のレジスタが 5 になった状態で、 最初に戻るときが訪れる。 すると今回は、 dec0 が実行される際に 0 番目のレジスタが 0 になっているので、 レジスタの数の減少は起こらずに、 すぐ次の命令に進むことになる。 その命令とは forward3 であるから、 ポインタは 3 つ後に進むが、 その場所は最後の命令の直後である。 したがって、 ここでレジスタマシンは正常終了し、 このときレジスタは (0,5,0,⋯) となっている。 つまり、 このプログラムは 0 番目のレジスタの値を 1 番目のレジスタに移すという操作を表しているわけである。

では、 レジスタマシンを用いて、 自然数上の関数が 「計算できる」 ことを定義しよう。

例を挙げよう。 定義の直前に見たプログラム dec0 forward3 inc1 backward3 は、 0 番目のレジスタの値をそのまま 1 番目に移すものであった。 定義に従えば、 これは恒等関数 id:󱀍→󱀍 を計算するプログラムと言える。 したがって、 恒等関数は計算可能であることが分かった。

もちろん、 より複雑な関数も計算可能である。 次回は、 どのような関数が計算可能になるかをより詳しく見ることにする。

参考文献

1. H. B. Enderton (2011) 『Computability Theory』 Academic Press