チューリングマシンとは？紙テープの計算機から「計算できる」を考える

コンピューターの仕組みを、画面もキーボードもない小さな機械で表せるとしたら。その機械にあるのは、マス目のテープ、文字を読むヘッド、そして短い指示表だけです。

チューリングマシンは、「手順に従って計算する」とは何かを考えるための理論上の計算モデルです。1936年にアラン・チューリングが示した考え方で、計算できることと、できないことの境界を調べる道具になりました。

構成は、テープ・ヘッド・状態・指示表

一回の操作は小さくても、これを何度も繰り返せます。ヘッドを戻せば、さっき書いた記号をもう一度読むこともできます。

標準的なモデルでは、テープの長さに上限を設けません。ただし、ある有限の時点までに使うマスの数は有限です。「無限のテープを実際に工場で作る」という話ではなく、記憶容量の不足をいったん脇に置いて、計算の性質を調べるための設定です。

歴史とモデルの定義はStanford Encyclopedia of PhilosophyのTuring Machinesに詳しくまとまっています。

具体例：「111」に「1」を一つ足す

ここでは数3を「111」、数4を「1111」と表します。1を数の分だけ並べる、単純な表し方です。ヘッドは左端の1から始め、空白のマスを□で表すことにします。

指示は二つだけです。

テープは最初「111□……」。ヘッドが1を三つ読み進み、初めて空白に出会ったところで1を書くと、「1111□……」になります。これで、この形式の数に1を足せました。

この例では、停止時に移動しない書き方を使っています。チューリングマシンの定義には移動の書き方などに違いがあり、同じ計算を別の指示表で表すこともできます。

簡単な操作で、複雑な計算を表せる

足し算の次には、記号を消したり、別の目印を付けたり、テープの左側へ戻ったりする指示を組み合わせられます。数字や文章も記号の列として表せば、操作の対象になります。

ポイントは、一つの操作が賢いことではありません。決まった操作を、記録を残しながら、順番に繰り返せることです。計算の進み方を細かい段階へ分解できるため、何が計算として実行できるかを数学的に扱えます。

万能チューリングマシンとは

普通のチューリングマシンでは、指示表を変えると別の計算になります。万能チューリングマシンは、ほかのチューリングマシンの指示表と入力をテープ上のデータとして読み、その動きをシミュレートします。

「別の計算手順そのものを、データとして渡せる」というところが面白さです。現代のコンピューターで、ソフトウェアを変えるとさまざまな仕事ができることにも通じます。ただし、万能という言葉は「どんな問いにも必ず答えられる」という意味ではありません。

停止問題：必ず判定する万能な手順は作れない

あるプログラムと入力を渡したら、その実行はいつか止まるでしょうか。それとも、永遠に動き続けるでしょうか。これを一般に判定する問題が停止問題です。

すべてのプログラムと入力に対して、停止するかどうかを必ず正しく判定し、自分自身も停止する計算手順は存在しません。個別のプログラムについて停止を確かめられることとは、区別が必要です。

たとえば、上の「111に1を足す」機械は、有限個の1を読み終われば空白に到達して止まります。その証明ができることと、あらゆるプログラムに使える判定器が作れることは別なのです。

「計算できる」と「すぐ計算できる」も違う

理論上は手順があっても、必要な時間や記憶容量が大きすぎて、現実には計算を終えられないことがあります。

チューリングマシンで計算できるかを調べるのは、まず「手順そのものが存在するか」という問いです。実用的なアプリでは、その先に「待てる時間で終わるか」「端末の容量で動くか」という問いが続きます。

手順の存在、正しさ、速さ。この三つを分けると、コンピューターについての話がずっと読みやすくなります。

紙とペンでも、小さな機械を動かせる

横にマスを並べ、111を書き、指示表通りに指を動かしてみてください。読み取る、書く、右へ進む。たったそれだけの動作が計算になる様子を、自分の手で確かめられます。

ルールから結果を導く考え方は演繹法と帰納法でも紹介しています。ゲームを作る側に興味があるなら、Unityで謎解きアプリを設計する記事もどうぞ。

関連する言葉を比較したい方へ：AI・コンピュータの用語8選では、意味・具体例・注意点をまとめて読めます。

記号の順序を読む暗号問題へ。用語から発想した、この記事とは別の短い体験です。