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

ちょいと訂正の回です。
以前の記事で、チューリングマシンの動作を表現するには、チューリングマシンとチューリングマシンの状態とテープの状態のそれぞれをコード化したものがあれば良いと書きましたが、テープヘッドの場所も必要なのを忘れていました。
というわけで、4つの自然数の組が必要になるのですが、以前に定義した N×N から N への全単射関数を Code(x,y) と書くことにすると、4つの自然数 a, b, c, d の組は Code(a,Code(b,Code(c,d))) で表すことができます。
これを単に Code(a,b,c,d) で表すことにします。
それから、テープは左方向にのみ無限に伸びているものとすると書きましたが、そうすると一番右に移動したときにそれから右に移動することができなくなって面倒なので、テープは左右に無限に伸びているものとします。
また、テープの各マス目に次のように番号付けします。
…6,4,2,1,3,5,…
1 が書き込まれたマスが有限個なのは一緒です。
そして、1 が書き込まれたマスの中で一番マス目の番号が大きいものから順に下っていったときにできるビット列を、二進数で表された自然数と同一視します。
次回は、チューリングマシンのコード化について書く予定。