「クレタ人はウソつきか」のお話で、「コンピュータにも解けない問題がある」というお話をしました。現在は身のまわりにコンピュータがあふれているので、このようなことを言われても「そりゃあそうでしょう」くらいにしか思わないかもしれません。ここでは、もう少し具体的な問題で、コンピュータでも解けない問題にどのようなものがあるかを見てみましょう。

ジグソーパズルで遊んでみよう

　皆さんはジグソーパズルをご存知だと思います。現在ではジグソーパズルを解くコンピュータが作られていますが、そこではどのピースがどのピースに隣接できるかを判定する画像解析が主たる課題となっています。ここではアルゴリズムを問題にしたいので、このパズルを変形した「タイル張り」パズルを考えます。

　図1のようなタイルを考えます。タイルは対角線で4つの部分に分けられ、そこには絵が描かれています。このタイルを図2のように、描かれた絵が合うように敷き詰めます。皆さんの中にはこのようなパズルを見かけたことがある方もいるのではないでしょうか。

タイル張りパズル「色をつなげて長方形を作る」

　次にもう少し難しいパズルに挑戦してみましょう。絵は処理が面倒なので、絵の代わりに色を使います。図2では絵を合わせるパズルでしたが、今回は同じ色をつなげてパズルを完成させます。また、ジグソーパズルでは端のピースがあり、端が大きなヒントになるので、ここでも端の色を導入することにします。
次のタイル張りパズル（図3）を見てください。用意された11個のタイル（A-K）を使って長方形を作ることができたらパズル完成です。

タイル張りパズルのルールは次の通りです。

・同じ色を隣接させ、タイルをつなげる
・長方形の端の色は白でなければならない
・白は端にしか使うことができない
・同じタイルを何回でもコピーして使うことができる
・タイルは回転することができる
・使わないタイルがあってもよい

　白は端の色で、端にしか使うことができません。したがって最初の3ピースA, B, C は、角（かど）にしか使えません。色をヒントに隣り合うタイルをみつけて、つなぎ合わせてみましょう。　

実際に試してみたい方は、以下のファイルをダウンロードして印刷し、タイルを切り取ってパズルに挑戦してみてください。

　コンピュータのプログラムができる人は、「タイル張りパズル」を解くプログラムを組んでみてください。色は整数で表すこととし、端の色は 0 とします。たとえば図3の最初のピースAは、白を0、赤を3、青を2 で表すことにすると、色の4つ組 ( 0, 0, 3, 2 ) と表せます。しかし、コンピュータは人間の思考をまねしているだけですから、コンピュータのことを知らなくてもかまいません。

このタイルの場合は、以下のような縦4横4の正方形が作れます。

コンピュータは「タイル張りパズル問題」が解けない？

さて、いよいよ「コンピュータに解けない問題とはどのようなものか？」を考えてみましょう。図3では11個のピースが用意された「タイル張りパズル」をご紹介しました。しかし、これはタイル張りパズルの一つの例にすぎません。ここでは、「タイル張りパズル」と「タイル張りパズル問題」という言葉を使い分けしています。

「タイル張りパズル」
与えられたタイルを使って長方形を作ること。ただし、各タイルはコピーして何枚でも使うことができる。

　皆さんならどのようにしてこのパズルを解きますか。試行錯誤を繰り返して、長方形ができたなら、「できた」と叫んで終わりです。問題は、いつまでたっても解が見つからないときです。タイルはコピーできますから、使えるタイルの個数には制限がありません。
タイル張りパズルとは「与えられた何個かのタイル」のことです。タイル張りパズル（の一つ）を記号 T で表すことにします。つまり、変数 T は、任意のタイル張りパズルを表す代名詞です。コンピュータの分野では、問題を次のように表します。

「タイル張りパズル問題」
　　入力：　タイル張りパズル T
　　出力：　T の解か“解はない”を答える

　コンピュータが問題を解くとは、どのよう入力に対しても、正しい解を出力するか、あるいは解が存在しないと答えることなのです。つまり、いつまでたっても何も答えないことは許されないのです。

　これくらいのパズルであれば、現在のコンピュータなら簡単に解けそうです。しかしこの問題を解くコンピュータは存在しないのです。日本が誇るスーパーコンピュータでも解けません。それどころか、将来現れるいかなるコンピュータでも、解けないだろうと現在の数学者の大半は信じています。

　「まだ現れてもいない未来のコンピュータのことなど、どうしてわかるのだ」と疑問をお持ちの方が多いと思います。また、この「タイル張りパズル問題」が現在のコンピュータで解けないことでさえ納得できない人もいるかもしれません。まだ天才が現れないだけで、天才が現れればこんなパズルなど簡単に解けるさ、と思うかもしれません。でもダメなのです。
「クレタ人はウソつきか」のお話で、（現在の）コンピュータでは解けない問題があることを証明しました。その問題からこの問題が導けるのですが、その橋渡しにはチューリングという天才のお話をしなければなりません。チューリングは「アルゴリズムとは何か」、「コンピュータとは何か」を考え、コンピュータを非常に簡単な要素にまで分解しました。コンピュータに解けない問題が存在すること、それも上で述べたような一見簡単そうな問題でも解けないこと、は20世の数学の大きな成果の一つです。ですから、皆さんがにわかに信じられないのはもっともです。その話はまたの機会にしましょう。

▼関連記事 

▼関連書籍 

▼数学Webマガジン・マテマティカ 『数の発明』
私たち人類はいつ頃から「数」を扱うようになったのでしょうか。旧石器時代までの進化の時代、そして人類が農業というすばらしい手段を発明し、文明が興るまでの間にはどのような道のりがあったのでしょうか。人類が「数の概念」を獲得するまでの様子を見てみましょう。

▼数学Webマガジン・マテマティカ 『バビロニアの数』
皆さんは、むかし南メソポタミア地方に栄えたバビロニアという国をご存知でしょうか。最近になって太古の昔この地に高度な数学や天文学が発展していることが分かってきました。マテマティカWeb連載『 バビロニアの数 』では、60進数という記数法はどのようにして生まれたのか、バビロニアで行われていた高度な計算とはどのようなものだったのか、などバビロニア数学に焦点を当て詳しく紹介しています。ぜひご訪問ください！

▼Twitter、Webマガジンサイトも更新中。よろしくお願いいたします。
Twitter: @mathematicasite
Web:http://mathematica.site/