24

アマゾンでスティーブン・ウルフラムの「新しい種類の科学」のレビューを読んでいるときに、私は次の声明に出くわしました。

すべてのコンピュータサイエンス（CS）の学生は、チューリングマシン（TM）などのユニバーサルコンピュータで可能なすべてのプログラムを体系的に一覧表示して実行する非常に単純な2行のプログラムであるdovetailerを知っています。

誰かが「dovetaling」を説明する「単純な2行のプログラム」を与えることができますか？

4

2 に答える 2

29

CSの学生は通常、チューリングマシンの整数へのエンコードを手元に持っています。これは、チューリングマシンを入力として受け取り、指定されたマシンの出力を出力として書き込むソフトウェアチューリングマシンエミュレーターを作成するときに必要です。このエンコーディングに、すべての整数が異なる有効なプログラムであるという特性を持たせるように調整することができます。

したがって、すべてのプログラムを一覧表示して実行するための単純な2つのライナーは次のようになります。

for (int i = 0; ; ++i) 
    printf("%d: %d\n", i, universal_turing_machine(i));

これはCではそれを無視してint、固定幅タイプです。

さて、明らかにそのプログラムはそれほど遠くには行きません。なぜなら、すぐにi対応するチューリングマシンが停止しないプログラムにヒットするからです。したがって、「ダブテール」のトリックは、最初のマシンから1つの命令を実行し、次に2番目のマシンから命令を実行し、次に1番目のマシンから別の命令を実行し、次に3番目、2番目、1番目のマシンからそれぞれ1つずつ実行することです。各マシンが停止すると（停止した場合）、もちろん、処理を停止するか、「タイムスライス」で何もしないで座ることができます。

各ステップでチューリングマシン間で必要なコンテキストスイッチを考えると、それがどのように「2ライナー」であるかはよくわかりません。しかし、ダブテールプログラムには理論的な用途があります（おそらく実際には使用されません）。それについての1つの興味深い点は、それが次の特性を持っているということです：

問題Xを多項式時間で解く（そして解を証明するために必要な情報を提供する）プログラムが存在する場合P、ダブテールプログラムはXを多項式時間で解きます。

P*(P-1)/2証明はかなり単純です（正しいプログラムの開始に到達するためにTuring命令を実行するのと同等の一定の時間がかかりP、[*]、それを実行するのに、そのプログラムを単独で実行するよりも多項式的に悪い時間しかかかりません）。私が最も面白いと思うプロパティの言い換えは次のとおりです。

P = NPの場合、すべてのNP完全問題の多項式解はすでにわかっています。

それらが多項式であることをまだ証明していません。P = NPの証明は、問題を解決するのがどのサブプログラムであるかを実際に示すことなく、その証明を完了します。ダブテールプログラム自体は、それが進むにつれてそれを理解することができます-各マシンが停止するとき、多項式時間を使用します-「これは元の入力のXの解決策ですか？」XがNPであることによって暗示されるアルゴリズム。それが解決策である場合は、出力して停止します。そうでない場合は、続けてください。

[*]ええと、おそらく線形時間です。新しい仮想チューリングマシンを作成するたびに、作業する入力のコピーを与える必要があるからです。また、実際には、コンテキストスイッチはおそらく一定の時間ではないため、2次と呼びます。手波-手波それは多項式で大丈夫ですか？

于 2011-02-24T16:34:02.867 に答える
2

チューリングマシンプログラムは、実際にはテーブル（状態xテープシンボル）であるため、プログラムはそのような可能なすべてのテーブルを列挙するだけです。そのように：

for(int symbol_count = 1; true; symbol_count++)
{
    for(int state_count = 1; state_count <= symbol_count; state_count++)
    {
        gen_table(symbol_count, state_count);
    }
}

ここで、gen_tableは、そのようなサイズのすべてのアクションテーブルを列挙します（たとえば、テーブルを大きな数として扱い、状態を数字として扱います）。これはCの2行よりも長いので、おそらくWolframは他のより強力な言語を使用していました。

于 2011-02-24T16:16:10.177 に答える