1. No category

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