チューリングマシンの動作を数式で表現しようプロジェクト3

今回は、テープの状態を非負整数を使って表現することを考えます。
簡単のため、記号は 0 と 1 のみとし、テープに書き込まれている 1 は有限個で、1 が書き込まれていない全てのマス目は 0 で埋まっているものとします。
また、テープは左方向にのみ無限に伸びていると考え、一番左の 1 から最初のマス目までを二進数で表された一つの自然数と同一視します。
そうすると、テープの状態と非負整数が一対一に対応します。
というわけで、まずは自然数 x に対し、x を二進数に直したときの $2^{i-1}$ の位の数を返す関数を次のように構成します。
$\rm{Digit}(x,i) = \rm{Mod}(\rm{Quotient}(x,2^{i-1}),2)$
これが正しいことの証明は省略。まあ、少し考えれば明らかですね。
次に、状態が x であるテープの i 番目のマス目に記号を書き込む関数を構成します。
これは、次のようになります。
$\rm{Write}(x,i,1) = x + 2^{i-1}(\rm{Digit}(x,i)=0)$
$\rm{Write}(x,i,0) = x - 2^{i-1}(\rm{Digit}(x,i)=1)$
厳密に言うと、この関数の値を二進数に直すと、x を二進数に直したときの $2^{i-1}$ の位の数を変換したものが得られる、ということです。