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

途中から面倒になって途絶えていましたが、最後までやろうと思います。
今日は、チューリングマシンのコード化についての話。
チューリングマシンは、状態と記号から、次の状態と書き込む記号と移動パターンへの関数と考えることができます。
今、記号は簡単のため 0 と 1 のみとし、さらにチューリングマシンはテープに記号を書き込んだあとは必ず右か左に動くものとします。
右と左をそれぞれ 0 と 1 で表すことにすると、結局、状態数が n のチューリングマシンの種類は になります。
そんなわけで、各 n について、状態数が n のチューリングマシンそれぞれに適当にナンバリングすると、状態数が n のチューリングマシンのうちで k 番目のチューリングマシンのインデックス e を次のように定義できることが分かります。

このようにして、各チューリングマシンに対して、一意に自然数を割り当てることができ、逆に任意の自然数に対して対応するチューリングマシンがあることも明らかです。
さて、次はチューリングマシンのインデックスたる自然数 e が与えられたとして、そこから上記の n と k を求める数式を構成したいと思います。
それぞれ 、 とおきます。
x > y のときに 1、そうでないときに 0 を返す関数を (x>y) と書くことにすると、次が得られます。

実際には和を i = 1 〜 e まで考えなくても充分ですが、厳密な上限を求めるのは大変なのでこのようにしました。
すると

となります。
各種関数について詳しくは解説していませんが、興味があってちゃんと読む方ならばすぐに理解可能だと思います。
関数 (x>y) については前の記事を参照のこと。
次回は、n と k と記号から実際に、次の状態と書き込む記号と移動パターンを得るための方法について述べます。