- 理論計算機科学における計算可能性とNP-hardは、個別の整数や単一の真偽問題ではなく、関数、言語、無限列に適用される概念
- Sipserの例で「神が存在すれば常に1を、存在しなければ常に0を返す関数 f」は、どちらの場合も定数関数なので計算可能
- P vs NPは入力を受け取る問題ではなく、1つのイエス/ノーの問いなので、それ自体をNP-hardや計算不能と呼ぶことはできない
- Busy Beaver関数全体は計算不能だが、BB(6)のような特定の値は、どんな整数 k であっても
print k プログラムが存在するという点で、同じようには扱えない
- 繰り返される混同の核心は、無限対象向けの概念を個別の問題に適用してしまうことにあり、停止問題の計算不能性とGödelの不完全性を混ぜる習慣も同系統のもの
Sipserの例が教える計算可能性の範囲
- Michael Sipserの Introduction to the Theory of Computation には、計算可能性の定義を明らかにする宿題問題がある
- f:{0,1}*→{0,1}を、神が存在すれば常に1を返し、存在しなければ常に0を返す関数とする
- 問いは f が計算可能かどうかであり、答えは宗教的信念とは無関係
- f は計算可能
- 常に1を返す定数関数は計算可能
- 常に0を返す定数関数も計算可能
- f がそのどちらかであるなら、f もまた計算可能
- 同じ構造の並行した問いも同じ直観を与える
- 「神が存在すれば n=3、存在しなければ n=5 のとき、n は素数か」という問いでは、n が完全には特定されていなくても、{3,5}の要素であるという情報だけで素数だと言える
- f も同様に、どちらの定数関数かが分かれるだけで、計算可能だと判断するには十分に特定されている
計算可能性はプログラム作成の難しさではなく存在の有無
- 計算可能性は関数や無限列に適用される概念
- 個別のイエス/ノーの問いや個別の整数には、計算可能性を同じ形で付与しない
- 核心となる問いは、入力を出力へ写像するコンピュータプログラムが存在するかどうか
- そのプログラムを選ぶ、見つける、書くことがどれほど難しいかは、計算可能性の定義には含まれない
- プログラムを書くには神の存在有無を解決しなければならないとしても、計算可能性の判定自体は変わらない
P vs NPをNP-hardと呼べない理由
- 「P versus NPという問い自体がNP-hardだから解けないのか」という問いは、過去25年間に何度も繰り返されてきた
- NP-hardは3SAT、Independent Set、Cliqueのように入力を受け取る関数や言語に適用される
- 入力はBoolean formula、graphなど
- 出力はその入力に対する答え
- ある問題を多項式時間で解ければ、還元によってNPのすべての言語や関数も多項式時間で解けるとき、NP-hardと呼ぶ
- P vs NPは関数や言語ではなく、1つのイエス/ノーの問い
- その答えがZermelo-Fraenkel集合論の公理と独立である可能性は排除されていない
- しかし、この問い自体を計算不能またはNP-hardだと言うことはできない
- P vs NPの問いに正確に答える高速なプログラムは形式的には存在する
- P=NPなら「P=NP」を出力するプログラム
- P≠NPなら「P≠NP」を出力するプログラム
Busy Beaverで繰り返される同じ混同
- Busy Beaver 5の値が決定された記事のコメントでも、似た問いが繰り返された
- 「BB(n)の値が計算不能になる最小の n は何か」
- 「BB(6)はすでに計算不能であり得るのか」
- Busy Beaver関数は計算不能
- しかしBB(6)のような個別の整数には、計算可能性の概念をそのようには適用しない
- BB(6)がどのような整数 k だと判明しても、
print k プログラムは存在する
- このプログラムはその整数を出力する
- 代わりに問えるのは、どの n についてBB(n)の値がZF集合論のような公理系で証明不能かという問題
- AaronsonとAdam Yedidiaは2016年にこの問いを扱った
- 現在の記録は n=745 で、AaronsonとAdamの n=8000 を改善した値
- すべての特定の整数は「計算可能」と見なせ、計算不能なのはBB関数全体
「ゾンビのような誤解」が生き残り続ける理由
- 繰り返される混同の核心は、無限列や関数のために設計された概念を、個別の整数や未解決問題に誤って適用することにある
- 停止問題の計算不能性とGödelの不完全性を混ぜる事例も、同じ系統の混同
- 両者は密接に関係している
- Gödelは個別の命題について語れるようにしてくれる
- Turing計算可能性は特定の公理系に相対的なものではなく、絶対的な概念
- この説明は、同じ教育上の誤解が再び現れたときにリンクできる参照点の役割を果たす
- 最後の問いは、この「ゾンビ」のような誤解をどう鎮められるかに向けられている
1件のコメント
Hacker News のコメント
計算可能性という概念が必然的に無限を含むという点は、かなり直感に反することがある
たとえば任意の文字列 s についてコルモゴロフ複雑性 K(s) を計算するアルゴリズムがあるかと問えば、答えはよく知られている通り「ない」。任意長の文字列を入力として K(s) を計算するチューリングマシンは存在せず、証明は停止問題を使って短く済む
しかし、長さが n より短い任意の文字列 s について K(s) を計算するアルゴリズムがあるかと問えば、答えは「ある」。どんな n についてもそのようなアルゴリズムは存在する
方法はがっかりするほど単純で、2^n 個の可能な全文字列について K(s) の値を持つ巨大なルックアップテーブルを備えたチューリングマシンを作ればよい。実際にそのテーブルをどう求めるかは別問題で、特定の実装は有限の記述を持ち、K(s) もすべての s について有限なので、アルゴリズムは存在する
したがって有限な対象に対する有限な問いは、計算可能性の観点ではあまり面白くないことがある。答えをすべて出力するプログラムを常に書けるからであり、問いが無限の対象集合へ拡張されたときに初めて、有限な何かが無限個の問いに答えられるのかが面白くなる
実際には、無限が「どんな一回限りの小細工よりも十分大きな N における近似的・究極的・定常状態の挙動」の代わりをしているわけだ
現実ではそうした小細工も重要で、ビッグオー比較で無視される定数や低次の項も実性能には重要である。「定数因子が意味を失うほど大きな問題」と「定数という言葉が暗黙に意味する範囲に収まるほど小さな問題」の間には常に緊張がある。たとえば 32 ビット整数が整数のふりをしている場合がそうだ
無限大の観点では、すべての有限数は実のところ非常に小さい。宇宙の果ての椅子に座って見れば、1 マイルも 1 ミリメートルと変わらない
このシナリオは実質的に「コンピュータ上のヒルベルトの無限ホテル」のようなものだ。既存のプログラムを一部屋ずつずらせば新しいプログラムを追加でき、計算に必要なテーブルサイズはそのままでよい
さらに一般化すると、多くの人は無限、アレフ、超限数学がどう機能するかについての直感が弱い。日常的な関連性も低く、数学や圏論・集合論の創発的性質に深く絡んでいる。無限がどんな有限数よりも大きいというだけでなく、ある無限が別の無限よりもさらに大きいこともある、という点は、小学校的な「無限」の概念にとどまる直感からはすぐには見えてこない
より興味深い問いは、アルゴリズムを計算可能にしてくれる何らかの n < ∞ が存在するかどうかだが、当然ながら答えはノーであり、チューリング賞は吹き飛ぶ
可能なすべてのチューリングマシンを短いものから列挙し、s を出力するものを探せばよい、という考え方だ。より短いマシンをすべて試して s を出力しなかったなら、s を出力する最短のマシンを見つけたことになるので、その長さが K(s) になる。同じ長さ、またはより長い別のマシンが s を出力することもあり得るが、K(s) は最小長についての値なので変わらない
私の経験では、ここでは古典的なコンピュータサイエンスよりも構成主義数学のほうが人々の直感によく合う
たとえば P=NP 問題の答えを出力するプログラムが存在するという構成的証明はまだない
私の論文でも、計算可能な Julia 集合に関連してこの問題を扱った。Mark Braverman はすべての二次 Julia 集合が計算可能であることを証明したが、本人もその証明は一様には計算可能でないと説明している。代わりに、望む Julia 集合のパラメータを受け取り、複数の集合を望む解像度で描こうとする 5 つの機械を作り、各 Julia 集合ごとにそのうち 1 つが正しく描く
構成主義数学におけるコンパクト集合の構成的概念は、計算可能な Julia 集合に必要な意味での計算可能集合とおおよそ対応する。しかし、すべての二次 Julia 集合がコンパクトであることは構成的には証明できず、可能なパラメータの複素平面を複数の領域に分けたうえで、各領域内で該当する Julia 集合がコンパクトであることを証明しなければならない
古典数学ではこれらの領域の和集合は複素平面全体だが、構成主義ではこの結果は成立しない。同様に、古典数学では正の実数と正でない実数の和集合は実数直線全体だが、構成主義ではやはり成立しない
構成主義的アプローチは、計算を実際に実現するにはどんな追加情報が必要かを正確に教えてくれる。つまり、与えられたパラメータが複素平面のどの領域に属するかを明らかにする必要があり、そうして初めて望む画像を得るために 5 つの機械のどれを実行すべきかが分かる。こちらのほうがはるかに満足のいく答えに感じられる
人々は本能的に、分岐文のどちら側にいるのかを知る必要があると分かっており、古典論理で訓練されたせいでその事実を忘れたわけではないだけだ
「5 つのうちどれが正しいのか」という問いについて、まだ見つかっていない証明があると見ているのか、それとも ZFC の中でのように決定不能だと見ているのかも気になる
これが、停止問題の決定不能性を理解しにくくしている要因の一つだと思う
「複雑すぎて、ある機械が停止するかどうか判別できない機械がある」と言いたくなるが、取るに足らないプログラム
return trueとreturn falseのどちらかは、どんな機械と入力を与えても常に正しい答えを返す「そのプログラムたちはチューリングマシンについて何も知らないから除外すべきだ」と反論したくなるかもしれないが、決定可能性とはそういう話ではない。「2つのうちどちらのプログラムが正しいかを見つけるのが決定不能だ」と考えることもできるが、それも真または偽として定まった答えがある。問題は、機械/入力の組み合わせからなる無限集合へ拡張されたときに初めて決定不能になり得る
例えば任意の有限次元ベクトル空間は、その双対空間および二重双対空間とさまざまな方法で同型だが、後者については、そのようなすべての空間にわたって一貫した「自然な」同型を選べる一方、前者についてはそれができない
「なぜ自然に同型ではないのか？ 基底の長さは同じなのに！ 基底に依存するかどうかをなぜ気にするのか？ ほかの証明では基底を選んでいるのに、なぜそれは問題ないのか？」といった混乱が生じる
文言の問題は、様相論理が必要になる点だと思う
「神が存在するなら f:{0,1}*→{0,1} を定数 1 関数とし、神が存在しないなら定数 0 関数とする。f は計算可能か？ ヒント：答えは宗教的信念には依存しない」
正確な問いは、f が計算可能であるだろうか、すなわちすべての x について f(x)=M(x) を満たすチューリングマシン M が存在するだろうか、というもの
答えは「存在する」。どの世界であっても、自明なチューリングマシン M=1_M または M=0_M があるからだ。逆に元の表現である「f は計算可能か」は様相的に誤った問いであり、Sleeping Beauty や Red Envelope のパラドックスのような、文法的に不正確な問いに近い
別の見方をすると、神や、実際そうかもしれない何らかの事実への依存性が後から埋められるが、使用前には決まるコンパイラ指示子やプラグマに近い、ということ。正しく問えば、関数と計算可能性の厳密な定義を展開する問題にすぎず、どちらも Sipser で明示的に定義されている
f という名札の指示対象が、神が存在すれば定数 1 関数、神が存在しなければ定数 0 関数になるという話であり、私たちは神の存在の有無を知るまでどちらなのか分からないだけだ。2つの定数関数の計算可能性は自明なので、実際には計算可能性の問題というより名札の問題に近い
確率論が現実に適用されたときに機能するという事実自体が非常に謎めいており、さまざまな科学的・哲学的探究の対象になってきたことを考えれば、驚くことではない
提案された “would f be” 式の解決も、あまり解決になっていないように思う。「神」の問いの目的は、読者を特定の P-NP 問題から離れさせ、定数関数については計算可能性の概念が役に立たないことを理解させる点にある。この提案が役立つには、元の P-NP の問いにも適用できなければならないが、よく定義された数学的問いに様相的アプローチがどう入り込むのかは、まだ見えていない
「神が存在するなら f:{0,1}→{0,1} を定数 1 関数とし、神が存在しないなら f:{0,1}→{0,1} を定数 0 関数とする」
そのような述語が本人の神の概念に合っているかどうかは、別の非数学的な問題だ
古典論理で、偽である命題はあらゆるものを含意する、と学ぶときに人々が驚くのと似ている。数学には厳格な形式規則があり、「含意する」や「もし」といった語の日常的意味に対する先入観は脇に置くことが重要だ
G:t∈ℝ⁺->{0,1} を、時刻 t に神が存在すれば 1、そうでなければ 0 とする、という形だ
もちろん非慣性系で G を分析すると、さらに面白くなる
Sipser は、ほとんどの人が計算と経験的調査の違いをよく分かっていない点を利用している
「神は存在するか」は、おそらく答えられない問いかもしれないが、それは論点ではない。その答えを探すことは、そもそも計算の領域ではない。計算は入力を出力へ写す手続きにすぎず、この場合、神の存在の有無は入力の一つだ
入力値を実際には知り得ないため混乱するが、プログラムはそれでも存在し、自明なプログラムだ。別の二値の経験的問いに置き換えてもよい
例えば f:{0,1}* -> {0,1} が「Paris に移動式トイレが少なくとも1つあれば 1、なければ 0」だとしよう。これは計算可能で、真である入力で実際に実行することも可能だ。神に関する関数も計算可能だが、推測した入力でしか実行できないだけだ。出力が私たちの住む宇宙と意味のある対応を持つと保証できなくても、それでも計算可能な関数である
さらに単純に f:{0,1}* -> {0,1} だけを考えてもよい。「神が存在する」と「神が存在しない」はそれぞれ可能なビット文字列だ。このうち一方を入力として受け取れば 0、もう一方を受け取れば 1 を出力するプログラムが存在し得るか、と問うなら、当然可能だ。入力が経験的に真かどうかは関係ない
問いの f は関数ではなく名札だ。神が存在すれば f の指示対象は常に 1 を出力する f1 であり、神が存在しなければ常に 0 を出力する f0 である。したがって実際には計算可能性の問題ではなく、名札の問題である
数学者やコンピュータ科学者が会話の便宜上、細部を省いた省略表現を使うため、こうしたことはよく起きる
「両辺に dx を掛ける」と言うのと変わらない。「巡回セールスマン問題は NP 困難か？」という質問は、特定のインスタンス 1 つではなく問題の族を指している。特定のグラフを固定すれば N がないので、当然 NP 困難ではない
これを知っていれば自明すぎて言う価値もないが、用語の意味を知らない人にはまったく届きにくい
私も過去に別の分野で似た形の誤解をしていた。DNA をコードのように見て、基質を介して直接、または DNA を修正する形でメッセージをやり取りするものが、そのコードを実行しているのだと信じていた。全体として完全に役に立たないモデルではないが、いつそのモデルに取りつかれてはいけないのかを知る必要があった
数学的背景のある生物学者にとって、DNA をチューリングマシンの実行モデルとしてそのまま見るのは明らかに誤りだが、私にはそうではなかった。結局、基礎知識になじみがないことから来る問題である
決定可能性、計算可能性、存在、さらには果物のような言葉でさえ、学術的文脈と日常的文脈では意味が異なる。日常的な意味の直感を学術的文脈に持ち込むと、こうした「間抜けな質問」が生まれる
Wikipedia に載っているある巨大数は、学術的な意味では「存在」し「計算可能」だが、その桁数は私たちの宇宙の中に収まらない
注意して読まないと文言が紛らわしい
「神が存在するなら f:{0,1}*→{0,1} を定数 1 関数とし、神が存在しないなら定数 0 関数とする。f は計算可能か？」において、選択肢は関数の一部ではない
関数 f が「神が存在する」の値に応じて分岐しているのではなく、分岐はメタ言語の中にある。私たちは f=0 なのか f=1 なのかを知らないが、どちらであっても可能な 2 つの関数はいずれも計算可能なので、f も計算可能である
さらに、f が実際にその分岐を含んでおり、関数の定義域が 0（神が存在しない）と 1（神が存在する）だとしても、定義域の各値について結果を計算できるという意味では、依然として計算可能な関数である
混乱の核心は、値が未知だとみなされる自由変数を f の中の分岐条件へ押し込むことにある
「神が存在するなら n=3、神が存在しないなら n=5 としよう。n は素数か？」という例には、喜んで異議を唱えたい
ここでは n が 3 または 5 だと主張するために排中律を使っているが、「神が存在する」という命題について排中律が成り立つという正当化がない
この場合、排中律が正当化されるかを問題にするなら、なぜ排中律だけを問題にするのかも正当化しなければならない。なぜ爆発原理まで捨てて paraconsistent logic で作業しないのか？ Kolmogorov もこの公理には重大な問題があると見ており、当初は構成主義論理と両立しないと考えていた
また、この命題の正確な定式化によっては、必ずしも排中律が必要ではないかもしれない
神は必ずしも物理法則や基本的な論理的必然性に縛られないかもしれない。そのような神の概念は特定の神学的推論の系譜から出たものであって、一般的な場合ではない
望むなら神は 6 を奇数にすることもできる。すべての数学、論理的一貫性、宇宙全体を変えたり、77 だけが偶数で他のすべての数は奇数である世界を作り、すべての数学者にその配置が完全に一貫しており、常に正しかったと思わせることもできる
したがって答えは、ある程度宗教的信念に依存すると見なせる
理論計算機科学と複雑性理論は、CS の学部生や隣接業界の従事者にとって、素粒子物理学が一般人に占める位置と似ているように見える
一般人がエンタングルメントという言葉を聞いたことがあるように、私たちは NP 困難という言葉を聞いたことがあり、数学的な展開を自分で追う代わりに、ひどい一般向けの比喩や空想で置き換えてしまう
筆者は長い訓練のせいで自分なりの非常に厳密な計算可能性の定義を選び、その語の特定の定義について記事全体を書いたうえで、同じ語を別の定義で使う世の人々を、間抜けな質問をしていると決めつけたのかもしれない
職場で研究者と話すときや一般の人と話すときに、こういうことは本当によく起きる。共通の用語を定めるのは難しく、自分の用語を基準に線を引いたうえで他人についてこいと言うやり方は疲れる