Title Author(s) Citation Issue Date Type 計算できない問題について山崎, 秀記一橋論叢, 101(4): 591-601 1989-04-01 Departmental Bulletin Paper Text Version publisher URL http://hdl.handle.net/10086/12576 Right Hitotsubashi University Repository （141）計算できない問題について ● 計算できない間題につ山崎秀 ξ同計算など、数値の計算に利用されていた。つまりプログラムは数値計算のプログラムがほとんどだった。もちろ計算だけに限られるものではなくなっている。そして、最近ではコンピュータ︵バソコン︶通信がはやり、株のてくれ．るようにも見える。そこで本当にコンピュータは仕事もこなしてくれる、あるいはどんな問題でも計算しコンピュータは適当なプログラムさえ与えれぱ、どんな・売買をバソコン通信を利用して行いませんかという広告この問に対する議論を通して、計算可能性理諭というコンビュータ・サイエンスの基礎的分野の入門、紹介をしなんでもできるのだろうか、という問を考えてみたい。り、適当なプログラムを与えることによりこれらの仕事たいというのがこの小文の目的である。も見かける。これら外見上様々な仕事をするコンビューをさせることができる、ということは御存知だろう。この問に対する答えおよぴ問自身に対する批判としてタもハード的には同一の原理に従って動作するものであ訳、テレビゲーム、など様々な話題が新聞に繊っている。ワープロ、銀行での預金管理などのデータ処理、機械翻ん今でも数値計算プログラムの重要性僅言うまでもない 0 はじめに七コンビュータはいまや身近なものになり、いろいろなてが、上にあげた例にも見られるように、その応用は数値、場面で利用されている。思い付くままに並べてみても、しコンビュータは最初は弾道の計算やロケットの軌道の 591 己 ■ 第4号（142）第101巻一橋諭叢を作曲するとは、何を持ウて作曲したというのか。ただとも数学的に、定式化できないという疑問がある。音楽し・かし、これにはそもそも仕事の定義自体が、少なくきないという議論もあろう。でも計算できると答えるだろう。しかし、桁数が二の十・け算がコンピュータで計算できるかと聞かれれば、だれ同様のことはもっと簡単な例にも見られる。例えぱか桁数の円周率を計算するプログラムが作れるだろう。ままか、あるいは。こく簡単な変更で、いくらでも多くのはコンビュータの計算スビードが発達すれば、あるいは音を並べるだけでよいのなら、そのプログラムは簡単に兆乗桁位の整数同士のかけ算がやはり現在のコンピューいくつか考えられる。例えぱ、人間の創造的能カに関す作れるだろう。しかし、音の並びがどういう条件を満たタで許しえる時間内に計算可能とは思えないだろう。だ計算時間やデータの記憶装置をいくら使ってもよいとすしていれぱ、作曲をしたというのにふさわしいかを、きからといって、かけ算の計算が︵一般的には︶できないる事柄、音楽を作曲するとか、絵を描くとかいう仕事はちんと述べることなど期待できないだろう。逆に言うと、というのでは議論にならない。そこで以後、計算時間やれぱ、原理的には計算できる。現在あるプログラムそのもしその様なことが可能なら、つまり、どのような音の計算のための記憶領域はいくらでも使用してよいというコンビュータにはできない、つまり作曲プログラムはで並びを我々は美しいと感じるかをきちんと定式化できるよう。これは、現在のコンピュータを使って、普通の時次に、円周率を十億桁求める、という仕事を考えてみとにする。い。そこで、数学的に定式化できる仕事だけを考えるこ題を解く方法を手にいれ、その暁には、コンビュータにが足りないために解けないのであって、いつかはその問もある。そのような間題はその問題に対する我々の知識らないために、解くことができないという例はいくらでまた、その仕事あるいは問魑を解決する方法をまだ知︵理想的な︶コンビュータを仮定する。間内では行うことができない。実際、現在求められていも解けるようになるだろう。ここでは、そのような問題なら音楽を作曲するプログラムも可能になるかも知れなる円周率の最大桁数は約二百万桁である。しかし、これ 592 も、除いて考えることにしたい。では問題を数学的にきちんと定式化でき、コンピュータがいくらでも記憶装置を用いてよく、また計算時間をいくらでもかけてよいとして、なおかつ、その間題に関する我々の知識がいくら増えたとしても、それでもなおコンビュー。タで解けない問題が存在するであろうか。言い替、、んると、その問題を解くプログラムの存在自身が矛盾を導くような問題があるかということである。その答えは︸。ωである。それについて、これから説明をしたい。なお、この小文では、︵理想の︶コンビュータで計算できない問題があるか、という形で問を設定したが、この問は実は人間に計算できない問魑があるかという問と同じであると︵少なくとも計算機科学者の間では︶信じられている。ある問題に対し、その手順に従えぱだれでもその間趨が解けるような呉体附な手順があることと、それを解くコンピュータのプログラムがあることとは同値である、というチャーチの仮説は現在広く受け入れられている。したがって、その問題を解くための具体的な手順の存在自体が矛盾を導くような問題が存定式化される以前は、即ち、計算できるとはどういうこ工かが定義される以前は、答えは旨であろうと予想されていたことに注意しておきたい。ープログラムの停止性判定めておきたい。︵といっても、この小文の性格上、完全本論に入る前に、いくつかの点をもうすこし厳密に定に厳密というわけにはいかない。︶まずコンビュータが解く︵あるいは解かせたい︶問題を数学的に定式化するとは、一体何を定めれぱよいのだろうか。最初にも述べたように、コンビュータは数値の計算をするだけの機械ではない。もっと一般的に、何等かの入カが︵いくつか︶あって、それに対し何等かの出カを出す機械と考える。では、入カや出カは何かといえぱ、それは適当に定められた文字︵記号︶を並べた文字列であると考える。入カや出力を構成する有限個の文字の集合は、プログラムしようとする仕事によって適当に定めれぱよい。考えてみれぱ、数値計算も、入出カは数字の列であると考えれぱ上記の範晴にはいる。そして簡単のために、コンビュータが停止したときだ ■ □ 在する。本題にはいる前に、この問は、問がはっきりと 593 :cc L･1C t :lr'f* f :1 (143) 第4号（144）第101巻橋論叢けその出カを考えることにし、コンビュータが計算を続けている間はなにも出カされないものとする︵あるいはされたとしても無扮する︶。また、コンピューノが停止するのは停止命令に出会ったときだけとする︵プログラムの最後には必ず停止命令があるものとする︶。次に、コンピュータにさせたいと思う仕事は次のようにして、定式化する。それは与えられた個数の与えられた条件に合った文字列をその入カとして定める︵これを入カ条件という︶。そして、与えられた入カ条件に合う入カに対し、どの様な出カを出せぱよいかを定める︵入出カ関係︶。したがって、間題は与えられた入カ条件を満たす任意の入カに対し、与えられた入出カ関係を満たす出カを求めるプログラムが存在するか、ということである。では、コンビュータに解けない問題を説明しよう。以下の議論では適当なプログラム言語を固定しよう。BA SICでもFORTRANでもまた機械語であってもかまわない。与えられたプログラム︵考えているプログラム言語の文であるから、ある記号列︶とそのプログラムの入カに対し、プログラムがその入カのもとで、停止するか否かを判定せよという停止性判定問題を考える。この停止性判定問題を解くプログラムは存盾しない。それを証明しよう。問題を解くプログラムと、問題の入カとしてのプログラムとがあるので、読者は混乱しないように気を付けて欲しい。定理− 次のような停止性判定プログラムHは存在しない。 Hの入カ一記号列XとW Hの出カ一次の条件が満たされていれぱ1、さもなけれぱ0。、 Xは正しいプログラムであり、Xが入カ Wのもとで停止する。証明このプログヲムHが書けたとしよう。このプログラムはあらゆる入カに対して停止しなけれぱならないことに注意しよう。Hを変形して次のようなプログラムG を作る。 Gの入カ一記号列X Gの出カ一入カX，XをプログラムHに入れたとき、 Hが︵停止して︶1を出力するなら 594 （145）計算できない問題について ● Gは停止しない。 Hが0を出カするならはGは停止す、る。このプログラムはプログラムHを次のように変形すれぱよい。出カ命令があったらそれを特別の変数aに出カすべき値を代入する命令に置き換える。プログラムが停止するのは停止命令にであったときだから、停止命令を aの値が1なら例えぱ次のような無限にループする命令 1 ㎝ざ勺︵無隈ループ︶昌二︷芭1IHま9o貝o↓oHo た入力に対し停止するか否かをそのどちらの場合にも数明されたプログラムは与えられたプログラムが与えられ定問題を二つに分けてみよう。上で存在しないことが証 Hの入カ一記号列XとW 定理2 次のよ交なプログラム甘は存在する。くれなくてもよい︶プログラムとに分けて考えてみよう。停止しないことを教えてくれる︵停止することは教えてないことは教えてくれなくてもよい︶と、プログラムがラムが停止することを教えてくれるプログラム︵停止しさて、Gに入カとして自分自身Gを入れてみよう。G ここで、問通をよりハツキリさせるために、停止性判そもそもHが存在しないことが証明された。口 H えてくれるプログラムである。そこで、これを、プログとそれにつづく停止命令に置き換えれぱよい。 WX は停止するだろう・か。Gが停止すれぱ、それはHに入カとしてG，Gを入れたとき出カが0であることを意味するから、Hの性質からGは入カGにたいし停止しない。これは矛層である。一方、Gが停止しないときは、入力 G，Gに対するHの出カは1である。これはGが入カG のもとで停止することを意味し、これも矛盾である。どちらにしろ矛盾であり、この矛盾が起きた理由は停．止判定プログラムHの存在を仮定したことにあったので、 595 X ● 第4号（146）第101巻一橋論叢るインタプリタとよぱれるもので、一般にコンビュータもとで模倣するプログラムを書けぱよい。これはいわゆ証明記号列Xがあらわすプログラムの動作を入カWのカWのもとで停止する。 Xは正しいプログラムであり、Xが入て︶1を出カする。ログラムでないから矛盾である。一方、Gが停止しないするから、肥の性質からGは入カGにたいし停止するプとして、G，Gを入れたとき出力が0であることを意味は停止するだろうか。Gが停止すれぱ、それは旺に入力さて、Gに入カとして自分自身Gを入れてみよう。G の出カ。 Gの出カ一X，Xをブログラム甘に入れたときの甘 Gの入カ一記号列X がプログラムを解釈し、そのプログラムの意味通りに実ときは、入カG，Gに対する肥の出カは0である。これ Rの出カ一次の条件が満たされていれば︵停止し行するさいに必要とされるプログラムである。このようはGが入カGのもとで停止することを意味し、これも矛ムではない。 Xが入カWのもとで停止するプログラい。中で、入カとしてのプログラム︵を表す文字列︶とそのは否定に関して対称的でないこともわかる。上の証明のわかる。また、後半のような意味でのプログラムの存在結局非停止性を調ぺることができないためであることが二れらにより、停止性判定問題が計算可能でないのは、そもそも肥は存在しない。口止判定プログラム甘の存在を仮定したことにあったので、どちらにしろ矛盾であり、この矛盾が起きた理由は停盾である。なプログラムが書けることは明かだろう。口定理3 次のようなプログラムHは存在しない。甘の入カ一記号列XとW 皿の出カ一次の条件が満たされていれぱ︵停止し証明このプログラム甘が書けたとしよう。旺を変形して︶0を出カし、さもなければ停止しなて次のようなプログラムGを作る。 596 （147）計算できない間題について ■ れることであり、そのようなプログラムHは、停止しなし停止するしないどちらの場合にもそのことを教えてくていたことは、与えられたプログラムがその入カにたいグラム甘の違いを見てみよう。プ回グラムHに要求され繰り返しになるかも知れないが、プログラムHとプロることに注意して欲しい。入カを処理するプログラムとが巧みに二重に使われていこのように、半計算可能性というのは、否定に関して能でさえない。て、非停止性︵停止しないことの︶判定問題は半計算可したがって、停止性判定問題は半計算可能である。そし在するとき、その判定間題は半計算可能であるという。なデータにだけそのヒとを答えてくれるプログラムが存一方、判定問題に対し、その答えがyeSであるよう定問題がともに半計算可能なら、その判定問題は計算可対称的でない。ところで、ある判定問題とその否定の判存在しない。能である。か否か判定せよという判定問題は、答えがyeS，nO 与えられたデータにたいし、それがある性質を満たすする。 Pの否定を半計算するプログラムGがあるとき、Pを計計算可能である。逆に、Pを半計算するプログラムFとその否定はともに計算可能であり、したがってともに半証明判定問題をPとする。Pが計算可能のとき、Pと定理4 判定問題は、それ自身とその否定がともに半計どちらの場合にも答えてくれるようなプログラムが存在算するプログラムHを次のように構成することができる。れぱそれでよい。停止しない場合には、それを教えてくするとき、計算可能であるという。したがって、与えらすなわち、Hはその入カに対し、FとGを平行して動か算可能のときそのときのみ、計算可能である。れたプログラムが与えられた入カに対して停止するかとし、どちらかから返ってきた答えを答えとする。Fかられる必要はない。そしてそのようなプログラム甘は存在の入カに対し停止する場合にだけそのことを教えてくれ一方、プログラムwでは、与えられたプログラムがそいことを教えてくれ、プログラム肥が存在しないので、 f いう停止性判定問題は、計算可能でない。 597 ● 一橋論叢第101巻第4号（148）で表す。ここで、2，3，5、−・−・は素数を順に持って㌧㌧㌣−⋮ 数列ができる。そして数列i，j，k、・⋮：を数入カに対しF，Gのどちらかは必ず停止するので、Hはきたものである。したがって文字列bcabは、数返ウてくれぱyes，Gから返ってくれぱnoである。必ずyesかnoの答えを返すプログラムであり、Pはで表される。ここで重要なのは、数を記号列に変換した Nよ♂−、計算可能である。口 2 計算可能という言葉についてであると定義した。この言い方がふさわしいかについて、ログラムが存在するときに、その問題は︵半︶計算可能ても同じになる。に変換可能であり、どちらの土俵で計算可能性を議論し能であるということである。こうして数と記号列は互いり、逆に記号列を数に変換したりする計算が、ともに可すこし議論してみたい。さてコンビュータプログラムが存在するという意味で 1節では、︵理想的な︶計算機上である間題を解くプまず、計算可能性を定義する土俵をどこにするかによない。︶逆に、記号例は自然数で表せるだろうか。まず、そして表記法を仮定せずに自然数を書き表すことはでき法を仮定すれぱ記号列として扱える。︵例えぱ10進法、である。最初にも注意したように、自然数は適当な表記の小文でも説明したように記号列の上で定義するやり方数の上で定義するもの︵いわゆる帰納的関数論︶と、こ仮定にしてきた。︶。なものになる。︵実はこのことに関しては暗黙のうちにらず、定義される概念は︵適当な符号化によって︶同値号列かなど︶、演算としてなにが許されているかに関わを持つか、基本的なデータとして何を扱い︵自然数か記変性を持つ。すなわち、元になる計算機がどの様な能カ第一に、プログラムが存在するという概念は、強い不の計算可能性はどの様な性質を持っているだろうか。記号をそれぞれある奇数と対応させる。例えぱaは1，第二に、計算可能と呼べる候補として考えられた数多って、実は大きく分けて二つの流儀がある。一つは自然 bは3，cは5、⋮⋮。すると文字列に対し、対応する 598 （149）計算できない問題についてストのシステム、帰納的︵部分︶関数などがあり、さらるテユーリング機械や、論理学者達によるλ−計算、ポここではないが、それには、計算機の数掌的モデルであ致することが知られている。具体的な説明をする余裕はくのシステムによる定義はすべて、上に述ぺた定義と一ログラムが停止するしないを含めて︶どういう性質を満プログラムの計算結果、あるいはその入出カ関係が︵プ同じ計算結果を持つプログラムは数多くある。そこで、プログラムは何かある計算をするのだけれど、一般にう間題が計算可能でないのだろうか。きるだろう。では、どういう間題が計算可能で、どうい以上のことから、計算機のプログラムが存在することは、プログラムの字面は問題ではなく、字面が異なって算結果に関する判定問魑ということにする。この問題でたすかを判定する問題を考える。これをプログラムの計をもって、あるいはそれと同値な他の定義でもって、いても同じ計算をするプログヲムに対しては、同じ答えが返らなけれぱならない。プログラムの計算結果に関する判定問題は、それが自グラムは存在しないことを証明した。プログラムに関す 2節で、プログラムが停止するか否かを判定するプロてのプログラムに対してその問題の答えがn0のときでに対してその間題の答えがyeSであるか、またはすぺ判定問題が自明であるというのは、すべてのプログラム明な問題でない隈り、計算可能ではない。プログラムのる他の性質はどうだろうか。例えぱ、そのプログラムがプログラムの計算結果に関する判定問題はそれが自明定理5 ︵ライスの定理︶ある。自明な判定問題が計算可組であるのは明かだろう。 3 ライスの定理仮説であり、現在広く受け入れられている。︵半︶計算可能の定義としてよいというのがチャーチのムなどもある。にはチ冒ムスキーの句構造文法、マルコフのアルゴリズ r 10個以上の変数を使っているか否かという問題はどうだろうか。これはプログヲムの字面を眺めてみれぱわかることなので、実際にそのようなプログラムを書くのは面倒だとしても、そのプログラムが存在することは納得で 599 ，第4号（150）第101巻一橋論叢でなけれぱ計算可能でない。証明 Pをプログラムの計算結果に関する自明でない判定問題とし、Pを解くプログラム9があるとする。決して停止しないプログラムOを用意する。さらに、Oに対するPの答えとは違う答えになるプログラムを持ってくる。それをNとしよう。さて、Pを解くプログラム9が存在したとして、それを用いて、停止性判定プログラム Hが作れることを示そう。それは次のような二つのステブログラムH X W 第ーステップて、9はXがWのもとで停止するか否か判定できることのどちらかであるかを判定できるのだから、答えによっ・Rの構成入カX，Wに対し、次のようなプログラムRを︵H になる。これは前の定理に矛盾し、したがって上記のよ XをWのもとで動かすの計算の中で︶構成する。うなプログラムgは存在しない。 □ らかのプログラムと等しい。そして、プログラムHはそ RはX，Wによって、外見上の振舞いはNかOのどち RをQに入カする。第2ステップない︵Oと同じ振舞い︶。 XがWのもとで停止しなけれぱ、Rは何も出カし定の問題は半計算可能でさえない。合もある。しかし半計算可能である問題の場合、その否もちろん、停止性判定間題のように半計算可能である場でも成り立たないかの場合を除いて、計算可能でない。性質を判定せよという間題は、いつでも成り立つかいつしたがって、プログラムの計算結果について何等かの振舞う。 XがWのもとで停止すれぱ、以後RはNと同じにップからなるプログヲムである。 R 600 （151）計算できない問魑についてしくなるようにできるか否か、判定せよという問題。れは今巳、計算の理論と呼ぱれる計算機科学の一分野の存在すること、また数多く存在することをしめした。こ以上、この小文では、原理的に計算可能でない問題が群︶上で、生成元の積で与えられた二つの元が等しいくつかの等式で定義される有限生成群︵または半群︵半群︶の語の問題定せよという間題与えられた整数係数方程式が整数解を持つか否か判ヒルベルトの第十問題。始まるもととなった研究をコンビュータの言葉を借りてその歴史的な経緯や数理論理学における結果について、ちによって得られていたことは注意しておく必要がある。以下に上げるようなより進んだ教科書等を参照していた余裕はないが、この小文を読んで興味を持たれた方にはこれらの問魑に関する詳しい説明や歴史的な説明をするいか否か判定せよという間魑。︵筆者のカ不足もあって︶述ぺることができなかったのだくことで許してもらいたいと思う。町またプログラムに関する判定問題以外にも、計算可能マト山崎、横森訳、サイエンス社、岩o。。。︶︵一橋犬学助教授︶スでない問題の例は色々知られている。以下にその様な問横芸議森は残念である。ュータが存在する以前に、主に数理論理学の分野の人た説明したものである。この結果は、実は世の中にコンビ 4 終わりに ’ エ理赤ン論墾社岩波 ○ 書蟹店ン題︵のうち簡単に説明できそうなもの︶をいくつか上げマス田、、計算論とオートマトン理論引（渡サ辺イてみよう。ポストの対応問題上下二つの文字列からなる対がいくつか与えられる。この対を重複を許して並ぺて、上の列と下の列が等 601 1 ビ端嚢娑筍 A3M （．）．野一崎サア、口 1