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

前回の記事では、チューリングマシンのインデックス e が与えられたとき、その状態数 n と、状態数が n のチューリングマシンの中での順番 k を求める関数をそれぞれ構成しました。
今回は、n と k とチューリングマシンの状態 q とテープに書き込まれた記号 s から、テープに書き込む記号 Symbol(e,q,s) とチューリングマシンの次の動作 Move(e,q,s) とチューリングマシンの次の状態 State(e,q,s) を求める関数を構成したいと思います。
今、記号と動作と状態はそれぞれ 2 通り、2 通り、n 通りあるので、それらの組合せは 4n 通りです。
そこで、まずは e と q と s から組合せの順番を求める関数を次のように構成します。

ここで、、 かつ です。
q(s+1)は全部で 2n 通りあり、それぞれが状態と記号の組に対応しています。
そして、k を 2n 桁の 4n 真数で表された数だと考えているわけなのです。
この C を使うと、あとは次のように構成できます。
テープに書き込む記号：

チューリングマシンの次の動作：

チューリングマシンの次の状態：

ここで、 です。
ちゃんと説明するのはめんどいので省略っ！
次回は、いよいよ、今まで作ってきた関数を組み合わせて、チューリングマシンの動作を表現してみたいと思います。