チューリングマシンにおける計算時間と計算空間：シミュレーターで測るアルゴリズムの効率
チューリングマシンは、計算の基本的な能力を探るための理論モデルです。これまでの記事では、チューリングマシンが「何」を計算できるか、あるいはどのような問題を「決定」できるかという計算可能性に焦点を当ててきました。しかし、計算機科学においては、「どのように」計算するか、つまり効率も非常に重要な要素となります。アルゴリズムの効率を評価する際の基本的な尺度となるのが、計算時間と計算空間です。
本記事では、チューリングマシンにおける計算時間と計算空間の概念を定義し、これらの尺度がシミュレーター上でどのように観測できるのかを解説します。シミュレーターを利用することで、抽象的な計算量理論が具体的な機械の動作としてどのように現れるのかを視覚的に理解することができます。
計算時間とは
チューリングマシンにおける計算時間（Time Complexity）とは、マシンが与えられた入力を処理し、停止状態に至るまでに実行するステップ（状態遷移）の総数を指します。各ステップでは、ヘッドの移動、テープへの書き込み、状態の遷移といった一連の動作が行われます。
計算時間は通常、入力のサイズ $n$ の関数として表現されます。入力サイズとは、一般的に初期テープに書かれた記号列の長さです。例えば、長さ $n$ の文字列を入力として受け取るマシンがあった場合、その計算時間は $T(n)$ のように表されます。
最も関心があるのは、入力サイズ $n$ が大きくなったときに計算時間がどのように増加するかという、漸近的な振る舞いです。この漸近的な振る舞いを表現するために、計算量理論ではビッグオー記法（$O$記法）などの記法を用います。例えば、$O(n^2)$ の計算時間を持つアルゴリズムは、入力サイズが2倍になると計算時間が約4倍になる傾向があることを示します。
シミュレーター上では、計算時間は「ステップ数」として直接的に表示される値に対応します。シミュレーションを実行し、マシンが停止した際に表示される総ステップ数を確認することで、その特定の入力に対する計算時間を測定することができます。異なるサイズの入力に対してシミュレーションを行い、得られたステップ数を比較することで、おおよその計算時間の傾向を把握することが可能です。
計算空間とは
チューリングマシンにおける計算空間（Space Complexity）とは、計算中にマシンが使用したテープのセルの最大数を指します。これは、計算の途中で必要となるメモリ量に相当します。チューリングマシンでは、テープが唯一の記憶媒体であるため、使用するテープのセル数が空間計算量となります。
空間計算量の定義にはいくつかのバリエーションがあります。例えば、初期入力が書かれた部分を除いた、作業領域として使用したセルの最大数を指す場合や、ヘッドがアクセスした最も左のセルから最も右のセルまでの範囲に含まれるセル数を指す場合などがあります。文脈によって定義は異なりますが、本質的には計算に必要な記憶容量を示しています。
計算空間もまた、入力のサイズ $n$ の関数として表現されます。例えば、空間計算量が $S(n)$ のように表される場合、$S(n)$ は入力サイズ $n$ の関数として使用するテープセル数の上限を示します。
シミュレーター上では、計算空間はシミュレーション中にテープがどれだけ右（または左）に拡張され、どの範囲のセルが使用されたかによって観測できます。多くのシミュレーターでは、ヘッドが最も左および最も右に移動した位置や、テープの全体像を表示する機能があります。これらの情報から、計算中にマシンがどれくらいの範囲のテープを使用したか、つまり計算空間を把握することができます。特に、作業領域として追加でテープを使用する場合、テープが右方向に拡張されていく様子は、空間計算量の増加を視覚的に示します。
シミュレーターを用いた計算時間・空間の測定例
具体的なチューリングマシンを用いて、シミュレーター上で計算時間と空間を観察してみましょう。ここでは、単純な例として「入力文字列を、その直後の空き領域にコピーする」タスクを考えます。
入力例: テープ上に #abc# が書かれているとする（#は空白記号）。出力として #abcabc# を目指す。
このタスクを実現する基本的なアルゴリズムは、以下のようになります。
1. 入力文字列の左端（a）から開始する。
2. 現在の文字を記憶する（状態として持つか、別のトラックにマークするなど）。
3. テープの右端まで移動する。
4. 右端の空白セルに記憶した文字を書き込む。
5. 左端に戻り、次の文字に対して手順2-4を繰り返す。
6. 入力文字列の全てをコピーしたら停止する。
計算時間（ステップ数）の観察
入力文字列の長さが $n$ の場合（例: "abc" なら $n=3$）、最初の文字 a をコピーするには、右端まで $O(n)$ ステップかかります。文字を書き込んだ後、左端に戻るのにも $O(n)$ ステップかかります。これを $n$ 回（各文字に対して）繰り返すため、合計のステップ数は $O(n) \times n = O(n^2)$ となります。
シミュレーターで入力 "a" ($n=1$), "ab" ($n=2$), "abc" ($n=3$) などでシミュレーションを実行し、総ステップ数を記録してみてください。入力サイズが大きくなるにつれて、ステップ数が二次関数的に増加する傾向が観察できるはずです。
計算空間（テープ使用量）の観察
元の入力文字列の長さが $n$ の場合、コピー先の文字列も長さ $n$ となります。コピーされた文字列は元の文字列の直後に配置されるため、合計で $2n$ 個の文字がテープ上に存在することになります（空白記号や作業用マークは含めず、単純なデータとして）。マシンが動作中に一時的に文字を記憶するために状態を使用する場合は空間は増えませんが、別のトラックやテープ上の特定のセルを作業領域として使用する場合、追加の空間が必要になります。上記の単純なアルゴリズムでは、コピー先の $n$ セルが必要です。したがって、必要な空間は入力サイズ $n$ に比例し、$O(n)$ となります。
シミュレーターでシミュレーション中にテープ表示を確認してみてください。初期入力の右側に新しい領域が使用され、そこに文字が書き込まれていく様子が分かります。最終的に使用されるテープの範囲（左端から右端まで）は、入力サイズ $n$ に比例して増加するのが観察できるはずです。
まとめ
チューリングマシンにおける計算時間と計算空間は、アルゴリズムの効率を理論的に評価するための基本的な尺度です。計算時間はマシンが停止するまでのステップ数、計算空間は使用するテープのセル数として定義されます。これらの尺度は、入力サイズに対する漸近的な振る舞いを $O$記法などで表現することで、アルゴリズムのスケーラビリティを分析する上で非常に有用です。
シミュレーターを利用することで、抽象的な計算時間（ステップ数カウンター）や計算空間（テープ表示範囲）が、チューリングマシンの具体的な動作とどのように結びついているのかを視覚的に把握することができます。様々なチューリングマシンのプログラムをシミュレーターで実行し、異なる入力サイズでのステップ数やテープ使用量を観察することで、計算量理論への理解をより一層深めることができるでしょう。計算の効率を意識することは、現実世界のプログラミングやアルゴリズム設計においても不可欠なスキルとなります。