アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで

154

5

章 究極の機械

面倒になりますが、1本のテープしか持たないチューリングマシンであっても、複数のテープを持つ機

械ができるタスクを実行することができます。したがって、チューリングマシンにテープを追加して

も、新しい能力は得られません。

5.3.4

　多次元のテープ

最後に、チューリングマシンにもっと大きなストレージデバイスを与えてみましょう。1次元のテー

プの代わりに無限の大きさの2次元の格子を使って、テープヘッドを左右だけでなく上下に動かせるよ

うにするのです。これは内部ストレージの特定の部分に素早くアクセスしたい場合に役立ちます。ま

た、各行の文字列の周りに無限の長さの空白を残しておけるので、それぞれの文字列を簡単に大きく

することができます。スペースを作るために、テープ全体にわたって情報を移し替える必要はありませ

ん。

ところが、こうした2 次元の格子は、必ず1次元のテープでシミュレートできます。最も簡単なの

は、1次元のテープを2 本使うことです。1本目のテープは実際にデータを格納するのに使い、2 本目の

テープはスクラッチ領域として使います。まず一番上の行から順番に、行の末尾を特別な文字でマー

クしながら、シミュレートする格子

†

の各行を1 本目のテープに格納していきます。

1本目のテープのヘッドは、これまで通り、現在の文字の上に置かれます。格子を左右に動くには、

単にヘッドを左右に動かします。ヘッドが行末のマーカーに到達すると、サブルーチンを使ってテープ

に沿ってずらすことで、空間を1つ分広げま ...