全プロセスの詳細解説
-
回文プログラムが経る構成（入力 1 0 1 0 1） 5 ステップ
回文判定プログラムがテープ 1 0 1 0 1、ヘッドはセル 0、状態
q0から開始します。プログラムが停止するまでに通過するすべてのコンフィギュレーションを、実際に1ステップずつ実行することなくルール表からカウントし、入力が長くなるにつれてそのカウントがどのように変化するかを述べてください。-
テーブルを移動（ムーブ）のリストとしてではなく、ラウンドの繰り返しとして読み取ります。ラウンドを開始できるルールは 1 つだけです。
q0は最も左のシンボルを消去し、直前に消去した内容に応じて分岐します。1 であればq1へ、0 であればq2へ分岐します。この分岐が比較メカニズムのすべてです。マシンはシンボルをテープ上に保持するのではなく、どの状態にいるかによって保持するため、後で反対側の端と照合する際に追加の移動コストがかかりません。 -
m 個のシンボルのブロックにおける 1 ラウンドをカウントします。左端の消去に 1 ムーブ。次にヘッドは残っている m − 1 個のシンボルを横断し、その先にある空白の上で向きを変えるためにさらに 1 ムーブ費やします。右端の消去に 1 ムーブ、残った m − 2 個の上を戻るのに m − 2 ムーブ、そして左端の空白上での最後の 1 ムーブにより、マシンは再び右を向いて
q0状態になります。 -
今回のテープでは 5、次に 3、そして単一のシンボルのブロックが得られますが、単一のシンボルはラウンドを構成しません。
q0がそれを消去し、q1が右端から外へ進んで向きを変え、q1cがペアとなる相手がいるはずの場所に空白を見つけます。奇数長の回文にはペアのない中央のシンボルが存在し、その空白を見つけることが受理（accept）を意味します。 -
3 つを足し合わせ、フェンスポストエラーに注意します。移動回数は 21 です。問題でカウントするのはコンフィギュレーションであり、初期状態を含めると 21 回の移動により 22 個のコンフィギュレーションを通過します。
-
任意の奇数長 n に一般化します。ブロック長は n、n − 2、……と 3 まで減少し、それぞれ 2m + 1 のコストがかかり、中央は 3 のコストがかかります。このリストを合計すると n の 2 次式となり、1 次式（線形）にはなりません。
解答
22 コンフィギュレーション — 21 ムーブ。2 次式になるという点が押さえておくべき重要な部分です。21 シンボルの回文では 253 ムーブを要します。入力長が 4.2 倍になると、作業量は 12 倍になります。その理由は巧妙なトリックというよりも幾何学的なものです。比較される 2 つのシンボルは常に残りの部分の両端に位置し、ヘッドは 1 つしかないため、すべてのペアに対して残りのテープを 1 往復完全に横断するコストがかかります。マシンに 2 本目のテープを与えれば、同じ処理は線形（1次）になります。読み取りながら入力をコピーし、2 つのヘッドを逆方向に走らせて 1 回のパスで比較すれば、およそ 3n ムーブで済みます。1 本のテープではそのコピーを置く場所がなく、往復移動が強制されるのです。
-
参考文献 (3)
- The single-tape quadratic lower bound for palindromes: F. C. Hennie, "One-tape, off-line Turing machine computations." Information and Control 8(6), 553–578, 1965.
- Where multi-tape time complexity classes were set out: J. Hartmanis and R. E. Stearns, "On the computational complexity of algorithms." Transactions of the American Mathematical Society 117, 285–306, 1965.
- The machine itself: A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem." Proceedings of the London Mathematical Society s2-42(1), 230–265, 1937.