【第2話】チューリング・マシンで示された計算の原理と限界

今回は、前回説明を思いっきり端折ったチューリング・マシンについて説明しようと思います。個人的には、そこは曖昧にしたままスルーしようと思ってたのに……なんでそこまで突っ込んだ記事を書くかって?

前回の記事を読んだ元同僚(この分野で私よりずっと上を行く専門家)と2月3連休の初日に飲みに行く機会があり、「チューリング・マシンの説明をごまかしてるよね?というか、書いてないよね?」と突っ込まれたんです。

そのとき、彼は既にベロンベロンに酔っ払っており、宴会お開きのときには生まれたての子鹿のように脚をガクガクさせるほど酔っていたため、「まさか藤田先生ともあろうお方が、うまく説明できないはずないですよね~?」などと私を煽ったことなど覚えてないでしょう。

とはいえ、正直ちょっとムカついたので、このマガジンの第2話として説明します。ナメんな!できるんだよ!(たぶん)

チューリング・マシンの構造

さて、チューリングが「『計算できる』とはどういうことか?」を追求したことは、前回説明しました。そして、チューリングがたどり着いた答えは「『計算できる』とは『チューリング・マシンを構成できる』と同じである」でした。

このマシンの構造はいたってシンプルで、たった3つの部品しかありません。1つは「テープ」、もう1つは「ヘッド」、最後の1つは「本体」。それぞれの部品を説明しましょう。

(1)テープは、書いたり消したりできるメモみたいなものだです。ただし、セル状に区切られていて、各セルには記号(データ)が入っています。

(2)ヘッドは、テープのセルを基準にして左右に動きながら、いま接してるセルに記録された記号を読んだり、そこに書き込んだり、消したりできます。

(3)本体は、ヘッドから読み込まれた記号と、あらかじめ決められたルールにしたがって、内部の状態を変化させます。

ここまで読んで、多くの人はこう思ったはずです。「テープは分かる。ヘッドも分かった。でも、本体の『内部の状態』とか『あらかじめ決められたルール』って何やねん」と。

「1+1=2」を計算するチューリング・マシン

実例を見せる方が早いので、とりあえず「1+1=2」を計算するチューリング・マシンを、実際に設計してみましょう。チューリング・マシンの初期設定と「ルール」の表は、以下の図表のようになります。

つまり、このチューリング・マシンは、A~Dの4つの内部状態を持ち、それぞれの内部状態とヘッドから読み込んだ記号とのペアでルールが決まり、そのルールにしたがって内部状態を変化させるわけです。このチューリング・マシンを、実際に動かしてみます。

最初、チューリング・マシンは、ヘッドが「空白」のセルを指していて、内部がAの状態からスタートします。このときのルールは、表に書いてあるとおり「状態はAのまま、セルの変更なし、ヘッドを右に移動させる」(ルール表の「①」の遷移)です。すると、チューリング・マシンはこうなりますね。

さて、状態がAでセルの内容が「1」でのルールは「状態をBに変更し、セルの内容を消去し、ヘッドを右に移動させる」です(ルール表の②の遷移)。この時点でのチューリング・マシンは、下記のとおりです。

というわけで、あとはこの調子で同じです。

・いまヘッドは「+」が書き込まれたセルを指していて、内部状態はBですから「状態をCに変更し、セルの内容を消去し、ヘッドを右に移動させる」(③の遷移)。

・次は、セルが「1」で内部状態はCですから「状態をAに変更し、セルの内容を消去し、ヘッドを右に移動させる」(④の遷移)。

・さらに次は、セルが「=」で内部状態はAですから「状態をDに変更し、セルの内容を消去し、ヘッドを右に移動させる」(⑤の遷移)。

・そして、セルが空白で内部状態はDですから「状態はDのまま、セルに2を書き込み、ヘッドはそのまま」(⑥の遷移)。

・最後に、内部状態がDでヘッドは「2」が書き込まれたセルを指してるので、ここで計算終了。

終了後のチューリング・マシンは、こうなってます。

ほ~ら!「1+1=2」がきちんと計算できましたね~!

……と、ここまで読んで「はぁ?」と思った方、えらい!「なんかインチキじゃね?」と気づいた方、もっとえらい!……そのとおり、このチューリング・マシンは完全なインチキです。

なぜなら、この計算結果は「チューリング・マシンが計算した結果」ではなくて、「私が自分であらかじめ計算した2という結果」を最後のセルに書き込むように、都合よくルールを決めただけだからです。「状態Dのときにセルが空白だったら、そのセルに2を書き込む」というルールがそれです。ご都合主義ですね。少年向けマンガの後付け設定みたいなもんです。

これが許されるなら、例えば「15+13=」という計算でも、私が「最後に 28 を書き込め」というルールさえ設定すれば「計算できる」ことになっちゃいます。明らかにインチキです。

なんでこんなインチキを最初に見せたかと言うと、まずはチューリング・マシンがどう動作するかを理解してほしくて、インチキでも単純な例を見せたかったからです。ウォーミングアップみたいなもんです。

3以下の足し算を計算できるチューリング・マシン

……が、本当にウォーミングアップでおしまいにすると、単なるインチキで終わりますので……マジメにやりましょう。次は「3以下の足し算を計算できるチューリング・マシン」を設計します。足し算の結果は0~3の4種類ありますので、これなら「最後に2を書き込め」みたいに特定の値を指定する恣意的なインチキルールは入れられません。

その前に、数字を2桁の2進数で表現することにします。すると、0~3の数字が次のように表せます。ちなみに、2進数が2桁のとき、これを「2ビット」と呼びます。

いまから設計するチューリング・マシンは、結果が3以下になるものなら全部計算できますので、「1+1」だけでなく「0+0」「0+1」「0+2」「0+3」「1+2」の足し算も計算できます。もちろん、足し算の順番を入れ替えて「2+1」などを計算することもできます。

さて、今度はインチキなしで「1+1」……つまり、きちんと「01+01」を計算してみましょう。これを計算するチューリング・マシンの初期設定は、例えばこんな感じです。

そして、ルール表は、下記のようになります。

うわ~!めんどくせえ!!と思ったアナタ。安心してください。正しい反応です。私も夜中にこれを作りながら、めんどくせえ!!と思って正直やめようとしたのですが、

の顔を思い出したので、最後までやり切りました。引っ越しの準備とか拙著の出版の販促とかで忙しいのに、ここまでがんばった自分を褒めてやりたい。

そして「01+01」がテープに書き込まれた状態で、ルール表にしたがってチューリング・マシンを動作させてやると、下記のようになります。左の赤字で書いたアルファベットは、そのときの本体の内部状態を表します。

ほら!ちゃんと計算できた!ちなみに、答えはもちろん「2」……つまり、「10」なのですが、繰り上がりがあるので、下の桁から「0」→「1」と出力されます。

で、上記のルール表で、3以下のすべての足し算(12 種類)が計算できます。繰り返しますが、私が事前に計算した結果を書き込むようなインチキルールは、どこにも入っていません(ヒマな人は他のパターンで検算してみてください)。

なので、このチューリング・マシンは、正真正銘「3以下の足し算を計算する」チューリング・マシンです。これがチューリングが考えた計算の原理だったわけですね。「チューリング・マシンが構成できる」ことと「アルゴリズム(=計算の手順)が存在する」こととは同じというのは、こういう意味です。

同じ要領で「引き算(例えば9-4)を計算するチューリング・マシン」も設計できますし、「(例えば 323 を)素因数分解するチューリング・マシン」も設計できます。もっとも、ルール表は計算したいことに応じてガラリと変わるわけですが、根っこの原理は一緒です。

万能チューリング・マシンの原理

さて、前回の記事を読んだ賢明なる読者諸氏は、こういう疑問を持つはずです。万能チューリング・マシンは、特殊なチューリング・マシンを、どうやって模倣するのか?と。ごもっとも。説明しましょう。

結論から言うと、万能チューリング・マシンは、自分のテープの「プログラム領域」に特殊なチューリング・マシンのルール表を書き込み、「データ領域」に計算対象となる記号(例えば「01+01=」)を書き込みます。これを図にするとこんな感じです。

万能チューリング・マシンは、まずデータ領域から最初のデータを読み込んで記憶します。次に、ヘッドをプログラム領域で走らせ、内部状態と記憶したデータとに対応するルール(命令)を抽出します。そして、その命令にしたがって、データ領域のデータを読み書きします。

これで、万能チューリング・マシンが、どんなチューリング・マシンでもモノマネできる理屈がお分かりになりましたでしょうか。万能チューリング・マシンが、「いま計算したいことに特化した特殊なチューリング・マシンを呼び出して、その動作を模倣する」とは、ざっくり言えばこういうことです。

さて……賢明なる読者諸氏は、次にこういう疑問を持つはずです。「万能チューリング・マシンが特殊なチューリング・マシンを模倣する仕組みは分かった。でも、そのルール表を『万能チューリング・マシンのテープに書き込む』って、どうするの?」と……さすがにこれについては、正直めちゃくちゃめんどくさくて、適当にごまかそうと考えたのですが、また、

の顔を思い出したので、ここもきっちり説明しましょう。ああ!めんどくせえ!!

プログラムの符号化(コーディング)

結論から言えば、チューリング・マシンを符号化します。さっきの「3以下の足し算を計算するチューリング・マシン」のルール表を、例えば、こんな感じで2進数に変換してしまいましょう。

そうすると、さっきのルール表で「状態Aのときセルが0であることをヘッドから読み取ったら、状態をCに変更し、セルを消して(空白で埋めて)、ヘッドを左に移動させる、このとき出力なし」というルールは、「000010100100011010000110110000」という 30 桁の2進数として符号化されます。

ただし、30 は8で割り切れなくてコンピュータには都合が悪いので、最後にゼロを2つ適当にくっつけて、むりやり 32 桁(32 ビット)にしてしまいましょう。なので、結局このルールは、「00001010010001101000011011000000」という 32 桁の2進数になります。

同じように「状態Dのときセルが1であることをヘッドから読み取ったら、状態をFに変更し、セルを消して、ヘッドを左に移動させ、このとき0を出力」というルールは、「00100010100011001000011011000100」になります。この変換をすべてのルールに適用します。

先ほどのルール表には、7つの内部状態 ✕ 5種類の記号=35 個のルールがあり、それぞれが 32 桁の2進数に符号化されるので、35 × 32 =1120 ビット。つまり、3以下の足し算を計算するチューリング・マシンは 1120 ビット(=140 バイト)で表せます。

万能チューリング・マシンは、3以下の足し算を実行する場合、まずこの 1120 ビットで表される「特殊なチューリング・マシン」を「1120 個のセルからなるプログラム領域」に書き込み、「01+01=」という記号を「データ領域」に書き込みます。

ここで、本当は「01+01=」という記号も「0」と「1」に符号化して書き込むことに注意しましょう。天才数学者シャノン(※1)によれば、あらゆる情報(データ)は2進数に符号化(デジタル化)できるので、チューリング・マシンは、テキスト・画像・音声・動画などのデータをすべて「計算」できます。

なので、ウェブサイトを見たければ「サーバからサイト情報を取得してディスプレイに表示する」という計算を実行するチューリング・マシンも、写真を撮りたければ「カメラを介して得られた画像データをメモリに記録する」という計算を実行するチューリング・マシンも設計できます。

つまり、扱うデータが数値でなくとも、2進表現の符号にして全部「計算」できるわけです。すごいね!だから、原理的に「スイッチのオン・オフ」しかできない電子回路でも、あらゆる「計算」ができるわけです。すっごいね!!

ところで、コンピュータを動作させるプログラムを書くことを「コードを書く」と言いますよね。それは、「万能チューリング・マシン(=コンピュータ)に模倣させる特殊なチューリング・マシンを、符号化(コーディング)する」というのが、本来の意味です。

……と、まあ、そういうわけで、酔っ払いに煽られて、チューリング・マシンをざっくりと説明してみました。やっぱり小難しい話が長くなったので、いつものとおりにおもしろ動画を置いておきます。

ちょっと画質も音質も悪いですが、そんな細かいことを言わずに、お手元の万能チューリング・マシンで観てください。最後は「ブラボー!」としか言いようがないですよ、ホントに。おわり!

脚注

※1:シャノンも超のつく天才です。デジタル回路に関する彼の理論がなければ、万能チューリング・マシンはただの仮想計算機にすぎず、「コンピュータ」として実現できていません。また、こうしてインターネットができるのも、彼の情報理論のおかげです。

ダートマス会議の発起人の1人であり、世界で初めてチェスのプログラムを書いたのもこの人です。一輪車の名手で、大学のキャンパス内を一輪車で走り回る「変人」だったそうです。

まさに 20 世紀を代表する天才です。そんな彼は、21 世紀に入った初めの年に亡くなりました。前回の記事をとおして紹介した天才たちのなかで、平和に大往生を果たしたのは彼だけです。

この記事が気に入ったら、サポートをしてみませんか?気軽にクリエイターを支援できます。

6

藤田 肇

コンピュータと人工知能の不思議な物語

計算機科学の基礎から最新の人工知能の応用まで、コンピュータに関する解説を載せています。
コメントを投稿するには、 ログイン または 会員登録 をする必要があります。