Edited at

ある問題が決定不能であることの意義


まえおき

筆者は、決定不能問題、あるいは計算に関する理論の専門家ではありません(最低限の知識はある…と思いたい)。ここに書いたことはできるだけ誤りがないように注意して書いたつもりですが、何かとんちんかんなことを言っている可能性があります。もし誤りがあればご指摘ください。


TL;DR


  • 世の中には決定不能な問題(≒一般解を求めるアルゴリズムが存在しない問題)がいっぱいある

  • 決定不能な問題の中には(もし解けたら)有用な問題もいっぱいある

  • PEGに関しても決定問題がある

  • 決定不能だからといって絶望しなくてもいい。問題のサイズを限定してみたり、保守的にしたりとかやり方は色々ある


停止性問題と決定不能性

この記事を読んでいる人の中には、決定不能という言葉に馴染みがない人も多いかもしれません。

決定不能というのを形式的に述べることはそこまで難しいわけではないにせよ、それを見ただけだとなんのことやらさっぱり、という事になる人も多い気がします。ただ、情報系学部出身の人だと、決定不能という用語で説明されたかどうかはともかく、チューリングマシンの停止性問題については何らかの形で聞いたことがある人が多いのではないかと思います。ここでうかつな書き方をするととたんに不正確になるので難しいのですが、「任意のプログラムと任意のデータを入力として受け取り、与えられたプログラムが、与えられたデータに対して停止するならば、trueを返し、停止しないならばfalseを返す」という問題のことで、結論としては、そのような問題を解くプログラムは存在しません。ここでポイントなのは、



  • 任意のプログラムとデータを受け取る

  • 「停止しないように見えるけど実は停止するものを、停止しないと判定する」といった形の回答(保守的な回答)は許されない

ということです。

このようなタイプの問題を決定不能(undecidable)といい、チューリングマシンの停止性問題以外にも、多くの問題が決定不能であることが知られています。直観的には、「任意の入力に対するアルゴリズム(アルゴリズム、というのは、必ず停止する、という意味も含んでいます)が存在しない」というタイプの問題が決定不能といえるかと思います。

こういう話を耳にしたときに、「なるほど、理論的にはそうなのはわかった。でも、実際、そんな問題、そうそう遭遇しないでしょ?」という感じの反応に遭遇することもあります。しかし、実際のところ、有用な問題が決定不能であるというのは決して珍しくありません。というか、何かの一般的な問題を解くアルゴリズムを研究などで考えたことがある人なら、その問題が、実は決定不能であるというシチュエーションに遭遇することは決して珍しくないかと思います。


PEGに関する決定不能問題

さて、ここまでだと話が具体的でないので、ここから、特定の決定不能問題について述べたいと思います。

Parsing Expression Grammar(PEG)という形式文法があります。2004にBryan Fordによって提唱された形式文法(PDF)です。実は、それと等価な文法がそれより数十年前に提唱されていますが(もちろん、Fordの論文にそれについては言及があります)。

小難しいことを抜きにして言うと、PEGというのは、

E <- A ("+" A / "-" A)*

A <- P
P <- "(" E ")" / I
I <- /* 整数リテラル(省略) */

こんな感じで、文法を定義するための文法です。BNFを見たことがある人は、/|に置き換えるといいかもしれません。このPEGは、1+11+2-31-(2+3)、...のように、数値を+-でつなげることができ、なおかつ、それらの一部分を()で囲むことで優先順位を変更できるような算術式を表現しています。

PEGは形式文法の中では比較的新しい(要出典)ですが、特に、その単純さや、構文解析器生成系(yaccとかJavaCCとかANTLRとか色々あります)を生成しやすいという特徴のためか、PEGの構文解析器生成系やPEGをベースにしたパーザライブラリが既に多数存在しています(意識していなくても、関数型プログラミング言語などにみられるパーザコンビネータライブラリは、実は、PEGをベースにしているといえるものが多いです)。

さて、このPEGですが、BNF(CFGベース)と違って、選択のための/に優先順位があるという特徴があります。これはどういうことかというと、"ab" / "aabまたはaを表現するが、"a" / "ab"aだけを表現する(abがきたときに、必ず最初の選択肢であるaが正解になってしまうため)ということになります。

この特徴については一長一短があります。このような優先順位があることによって、複雑で柔軟な文法を書きやすくなったり、構文解析器生成系のよくわからないエラーメッセージに悩まされずに済む一方で、これによって思わぬ構文解析器のバグが発生することがあります。

ここで、もし、任意のe1 / e2について、e2 / e1としても意味が全く変わらないかどうかを判定できるなら、利点を享受しつつ、欠点を回避できるので有用です。しかし、残念ながらそのような判定をするアルゴリズムは存在しません(2.3の最後の段落を参照)。Scala風の疑似コードで書くなら、

// e1 / e2 を e2 / e1 と入れ替えても良いかを判定する関数

def canBeReordered(e1: PEG.Expression, e2: PEG.Expression): Boolean = ???

という形になるでしょうか。このような関数を書くことはどうやっても無理ということです。

さて、ここまで書くと、ある問題が決定不能であるというのは何か絶望的なことを示唆しているかのように思えますが、実のところそうではありません

というのは、最初の方で述べた話なのですが、決定不能であるというのは、任意の入力に対して、とかいう言明であるので、たとえば、この話でいうと、与えられるe1e2の形を制限することで、(より小さい問題を解くという形になってしまいますが)決定不能でなくすることが可能ですし、また、e1e2の順序を入れ替えても意味が本当は変わらない場合でも、意味が変わるかもしれないので、意味が変わることにする厳しい判定(保守的な判定)をすることで、やはり決定可能にすることができます(ここで健全とか完全であるとかいう言葉を使わずに説明しようとしたので、妙になっているところがあるかもしれません)。

とはいえ、解こうとした問題が決定不能であることはあまりありがたくないことは確かではあるので、決定可能であるに越したことはないのですが、解こうとする問題が複雑になればどうしても決定不能にならざるを得ない部分はあります(この部分については、理論的な話ではないので、何か私の感覚が誤っているかもしれません)。


まとめ


  • 有用な問題が決定不能(解くアルゴリズムが存在しない)なことはよくある(現実にはまず遭遇しない話ではない)

  • 決定不能であっても絶望する必要はなくて、入力を制限したり、保守的な回答をするといった回避策がある

  • しかし、決定不能よりは決定可能な方が嬉しい

といったところでしょうか。

最後に、この記事では、あえて形式的に書くことを避けましたが、それによって不正確さが生まれているかもしれません。また、私がそもそも決定不能性に関する誤解をしている可能性もあります。そのような場合、遠慮なくコメントなどいただければと思います。