07/06/30 05:40:21
----BB以上の関数----
M[順序数](n) の関数を作るには、
>>233 の基本命令に
test ** という命令を加えればよい。
これは、ラベル ** へジャンプした場合に halt で停止する場合はポインタ位置を1にセット、
無限ループする場合はポインタ位置に0をセットする命令。
この命令は引数として順序数を取る。
ジャンプ先に、引数以上の test ** 命令が出現する場合には停止問題は解決できない為、
ジャンプ先で、halt より前に、引数以上の test ** 命令が出現する場合は halt と同じ動作をする。
引数の順序数の与え方は、
たとえばM[ω](n)を定義するマシンの場合には、
ポインタ位置から１が続く個数を数え、これを引数nとする。
M[C(a, b, c) の極限](n) を定義するマシンの場合は、 ...(Cは>>278のもの)
順序数を 0 , C ( ) の５個の文字で表し、
0 には 1 を、
, には 11 を、
C( には 111 を、
) には 1111 を、
割り振り、
文字の境目を 0 としてエンコードしたものを引数とすればよい。
たとえば、ポインタ位置から 111 0 1 0 11 0 1 0 11 0 1 0 1111 となっている場合は
引数は C(0,0,0) と解釈する。
※ C(a, b, c) は0とCのみでCの極限未満のすべての順序数を表現可能