チューリングマシンに番号付け

チューリングマシンは可算無限個あり、しかも洩れなく列挙することが可能なので、各チューリングマシンに適当にナンバリングをすることができます。
要するに、ゲーデル数を割り当てることができます。
しかしながら、普通にコード化すると、ある自然数には対応するチューリングマシンがないという状況もしばしば起こり得ます。
そんなわけで、チューリングマシンと自然数との1対1対応を与える規則を作ってみました。

チューリングマシンには様々な同値な定義が知られていますが、ここではそのうちでもっとも簡単なものを採用することにします。
まず、記号集合は $\Omega=\{0,1\}$ とします。
それから、状態数が $n$ の状態集合を $Q_n=\{q_0,q_1,\cdots,q_{n-1}\}$ とおきます。
初期状態および終了状態は $q_0$ と決めます。
また、ヘッドが左に動くことを $-1$ 、右に動くことを $1$ で表すことにします。
このとき、次のような関数 $\delta$ をチューリングマシンと呼びます。
$\delta:\Omega \times Q \rightarrow \Omega \times Q \times \{-1,1\}$

さて、ここから各チューリングマシンに自然数を割り当てることを考えます。
そのため、最初に $n$ を固定して考えます。
まず、 $\Omega \times Q \times \{-1,1\}$ の各元に、 $0$ から $4n-1$ までの非負整数を割り当てる関数
$\alpha_n : \Omega \times Q \times \{-1,1\} \rightarrow \{0,1,...,4n-1\}$
を次のように定義します。
$\alpha_n(0,q_k,-1) = k-1$
$\alpha_n(0,q_k,1) = k+n-1$
$\alpha_n(1,q_k,-1) = k+2n-1$
$\alpha_n(1,q_k,1) = k+3n-1$
次に、 $\Omega \times Q$ の各元には $1$ から $2n$ までの自然数を割り当てる関数
$\beta_n : \Omega \times Q \rightarrow \{1,2,...,2n\}$
を次のように定義します。
$\beta_n(0,q_k) = k$
$\beta_n(1,q_k) = k+n$
このとき、
$\displaystyle e_{\{n,\delta\}} = \sum_{k=1}^{2n}{\alpha_n}(\delta({\beta_n}^{-1}(k))) \cdot (4n)^{k-1}$
なる自然数が、状態数が $n$ のチューリングマシン毎に一意に定まります。
何故かというと、これによって $4n$ 進数 $2n$ 桁で表された $0$ 〜 $(4n)^{2n}-1$ までの $(4n)^{2n}$ 個の非負整数と、 $(4n)^{2n}$ 通りあるチューリングマシンを同一視することができるからです。
したがって、
$\displaystyle e = 1 + e_{\{n,\delta\}} + \sum_{k=1}^{n-1}(4k)^{2k}$
とおけば、これによって各チューリングマシンに対して、自然数が一意に定まることが分かります。
逆に、自然数 $e$ が任意に与えられたとき、インデックスが $e$ のチューリングマシンがただ一つ存在することも明らかです。

めでたしめでたし。