Loading article…
記述数とは、チューリングマシンの理論において現れる数です。これらはゲーデル数と非常によく似ており、文献によっては「ゲーデル数」と呼ばれることもあります。ある普遍チューリングマシン（UTM）が与えられた場合、そのマシン上での符号化が与えられれば、すべてのチューリングマシンに番号を割り当てることができます。これがマシンの記述数です。これらの数は、アラン・チューリングによる停止問題の決定不能性の証明において重要な役割を果たしており、チューリングマシンに関する推論においても非常に有用です。
チューリングマシンMがあり、状態q 1、 ... q R 、記号s 1、 ...、s mのテープ アルファベットがあり、空白はs 0で表され、遷移によって現在の状態、現在の記号、実行されたアクション (現在のテープ 記号を上書きしてテープ ヘッドを左右に移動させるか、まったく移動させないなど)、および次の状態が示されるとします。アラン チューリングが記述したオリジナルのユニバーサル マシンでは、このマシンは次のように入力としてエンコードされます。
UTMの入力はセミコロンで区切られた遷移で構成され、入力アルファベットは「D」、「A」、「C」、「L」、「R」、「N」、「;」の7つの記号で構成されます。たとえば、テープに0と1を交互に永久に出力する非常に単純なチューリングマシンの場合：
空白をs 0、'0'をs 1、'1'をs 2とすると、この機械はUTMによって次のようにエンコードされます。
DADDCCRDAA;DAADDCRDA;
しかし、7 つの記号「A」を 1、「C」を 2、「D」を 3、「L」を 4、「R」を 5、「N」を 6、「;」を 7 に置き換えると、チューリング マシンを自然数として符号化したものが得られます。これが、チューリングの万能マシンにおけるそのチューリング マシンの記述番号です。上記の単純なチューリング マシンは、記述番号 313322531173113325317 を持ちます。他のすべてのタイプの万能チューリング マシンについても同様のプロセスがあります。通常、このように記述番号を実際に計算する必要はありません。重要なのは、すべての自然数は最大で 1 つのチューリング マシンのコードとして解釈できるということです。ただし、多くの自然数はどのチューリング マシンのコードにもならない場合があります (言い換えれば、状態を持たないチューリング マシンを表します)。このような番号が常にどのチューリング マシンにも存在するという事実が、一般的に重要な点です。
記述数は、停止問題が決定不能であることの証明など、多くの決定不能性の証明において重要な役割を果たします。まず、自然数とチューリングマシンの間にこのような直接的な対応関係が存在することは、すべてのチューリングマシンの集合が可算であることを示しており、すべての部分関数の集合は非可算無限であるため、チューリングマシンで計算できない関数が多数存在することは間違いありません。
カントールの対角線論法に似た手法を用いることで、例えば停止問題が決定不能であるといった計算不能な関数を示すことができる。まず、記述番号eと入力xが与えられたときの普遍チューリングマシンの動作をU ( e , x ) と表し、 eが有効なチューリングマシンの記述番号でない場合は 0 を返すとする。ここで、停止問題を解決できるアルゴリズム、すなわち、あるチューリングマシンの記述番号が与えられたときに、そのチューリングマシンがすべての入力で停止する場合は 1 を返し、永遠に実行され続けるような入力がある場合は 0 を返すチューリングマシン TEST( e ) が存在すると仮定する。これらのマシンの出力を組み合わせることで、TEST(k)が1の場合はU(k, k) + 1を返し、TEST( k )が0の場合は0を返す別のマシンδ ( k )を構築できるはずです。この定義から、δはすべての入力に対して定義され、当然ながら全再帰的でなければなりません。δもまた、我々がチューリングマシンであると仮定したものから構築されているため、 δにも記述番号eがなければなりません。そこで、記述番号eを再びUTMに入力すると、定義によりδ ( k ) = U ( e , k )となるので、δ ( e ) = U ( e , e )となります。しかし、TEST( e )は1なので、別の定義によりδ ( e ) = U ( e , e ) + 1となり、矛盾が生じます。したがって、TEST( e )は存在できず、このようにして停止問題は決定不能であることが解決されました。