(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
次のうち、もっとも難しいのはどれなのだ？ ①与えられた整数が素数かどうかの判定 ②与えられたグラフが一筆書きできるかの判定 ③与えられたプログラムが停止するかの判定 #深夜の知識クイズなのだ
2019-09-26 23:49:05
23時にねたいさん
@netainoshirenai
@K9MmU7qClO9irZ3 ③だと思うのだ 停止するかはやってみなきゃ分かんないからなのだ！ 当てずっぽうなのだ！
2019-09-27 00:01:54
じきいさん
@yabaiaraisan
@K9MmU7qClO9irZ3 1はエラトステネスのふるい…だと思うので、これは除外できそうなのだ… そして2か3のどちらかと言われると……直感で、答えは3！……にしておくのだ！
2019-09-27 00:04:26
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@yabaiaraisan 正解なのだ！ 1と2は判定するアルゴリズムがあるのだが、3にはないのだ！
2019-09-27 00:21:40
院生のスナネコ
@sandcat_lab
@K9MmU7qClO9irZ3 1は√nまでの素数で全部割って整数が1度でもあれば素数でないので、n回よりも小さいのだ 2は各点を調べて奇数の辺を持つ点が3個以上ならアウトなので最大n回なのだ 3は停止するの定義が分からないのですが、おそらく定義づけが1番難しいところだと思うのです
2019-09-27 00:23:35
じきいさん
@yabaiaraisan
@K9MmU7qClO9irZ3 なのだー！ ジキイさんはIT技術についてずぶの素アライグマなので、もしよければ↓の考えがあってるかどうか、教えていただけるとうれしいのだ… 「1と2は与えられた問題を解決したら停止できる」 「3は"停止する条件"抜きに"停止することそのもの"の判断が必要になるから困難」 という理解だったのだ
2019-09-27 00:30:34
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@sandcat_lab おおっ、詳しいのだな！ その通り、1と2はそのやり方で判定できるのだ！ プログラムが停止するというのは、無限ループに陥っていないということだと思ってほしいのだ！ メモリはいくらでも使える、仮想的なコンピュータを考えてるのだ！
2019-09-27 00:33:46
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@yabaiaraisan まさにその通りなのだ！ 1と2は、最悪総当たりすれば分かるのだ。けど3はやってみても分からない場合があるのだ。 実際にプログラムを動かして、止まらないように見えても、ループしてるのか、計算に時間がかかってるのか、見分けがつかないのだ！
2019-09-27 00:37:45
院生のスナネコ
@sandcat_lab
@K9MmU7qClO9irZ3 それは(完璧な)判定は不可能なのだ… モンテカルロ法的に計算リソースをさいてプログラム実行時間を長くすれば正確になる(タイムアウトで判定)けど、無限ループしていない保証は無いのだ
2019-09-27 00:37:50
じきいさん
@yabaiaraisan
@K9MmU7qClO9irZ3 なるほどなのだ！それらの問題は素人目線ながら確かに難しそうなのだ！ 教えてくれてどうもありがとうなのだ〜！
2019-09-27 00:40:11
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
(解説)答えは③なのだ！ ものすごくざっくり言うと、①と②は「やればできる」、③は「やってもできない」からなのだ！ ……さすがに雑すぎるので、もうちょっと説明するのだ！ とにかく言いたいのは、③は①②と比べて桁外れに難しいということなのだ！
2019-09-27 00:52:21
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
まず①なのだが、正の整数nが与えられたとき、2から√nまでの整数で順番に割って、割り切れたら合成数、そうでなければ素数と分かるのだ。 n=0なら素数ではないし、n<0でも-1倍して同じことをすればよいのだ。 つまり①は、判定する手続きがあるのだ。
2019-09-27 00:57:38
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
次に②だが、これも簡単な判定法があるのだ。 各頂点から出ている辺の数に注目するのだ。「全ての頂点から偶数本の辺が出ている」または「2つの頂点から奇数本、残りの頂点からは偶数本の辺が出ている」とき、一筆書きが可能で、そうでなければ不可能なのだ。
2019-09-27 01:14:27
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
証明は mathtrain.jp/euler_graph が分かりやすいのだ。 ただ、もしこの方法を知らなくても、辺の順列を全パターン調べれば、一筆書きできるかは分かるのだ。 つまり②も、判定する手続きがあるのだ。 (ホントはグラフが連結かつ有限という条件をつけるべきだったのだが、大目に見てほしいのだ)
2019-09-27 01:19:35
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
さて、③なのだが、これは判定する手続きが「ない」のだ。 いやいや、実際に動かしてみればいいだろって？ 確かに、止まる場合はそれでOKなのだ。 でもループに陥ってた場合は？ ループしてるのか、計算に時間がかかってるのか、見分けがつかないのだ！
2019-09-27 01:22:04
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
↑のやり方ではダメだとしても、もっとうまいやり方があるのではないかって？ 答えはNOなのだ。 プログラムが止まるかを判定する手続きは「ない」のだ。これは見つかっていないということではなく、存在しないことが証明されているのだ。
2019-09-27 01:25:09
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
では証明してみようなのだ！ プログラムが止まるかを判定する手続きが存在すると仮定するのだ。 すると、その手続き自体もプログラムとして表現するできるはずなのだ。 そのプログラムをHとおくのだ。
2019-09-27 01:32:01
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
このHを使って、矛盾を引き起こすプログラムCを構成するのだ！ Cは、プログラムPを入力として受け取るのだ。そして、PにPを入力したときに、それが止まるかをHを使ってチェックするのだ。もし止まったらCはループし、止まらなかったらCは停止するのだ。 さあ、あと1歩なのだ。
2019-09-27 01:40:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
CにCを入力したときを考えるのだ。 Cは、Hを使って、「CにCを入力したとき、止まるかどうか」をチェックするのだ。 その結果が「止まる」だったら、Cはループするのだ。 でもそれっておかしいのだ！ だって今、CにCを入力したのだ！ Hは「止まる」と言っているのに、ループに陥ってしまったのだ！
2019-09-27 01:42:55
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
逆にHが「ループする」と言っていたとしても、今度はCが止まるから、おかしいのだ！ どっちにしろ矛盾するのだ！ ではなぜ矛盾が起きたのか？ それは、プログラムが止まるかを判定する手続きがあると、勝手に仮定したからなのだ！ つまりこの仮定は間違っていたのだ！ そんな手続きは存在しないのだ！
2019-09-27 01:45:27
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
まとめるのだ。①と②は判定する手続きがあるけど、③にはないのだ。つまり、③は桁外れに難しいのだ。 このような「どんな問題が解けるのか？」を研究するのが、計算可能性理論と呼ばれる分野なのだ！
2019-09-27 01:54:30
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
(冗談編)次のうち、一筆書きより難しいのはどれなのだ？ ①テトリス ②数独 ③ルービックキューブ #深夜の知識クイズなのだ
2019-09-27 00:17:15
じきいさん
@yabaiaraisan
@K9MmU7qClO9irZ3 言われてみればルービックキューブも正八面体とか正二十面体とかになると組み合わせの数が爆発的に増え難易度がちょう上がりそうなのだ！縦棒が落ちてこないフラストレーションだけじゃないのだな〜！ありがとうなのだ！
2019-09-27 00:45:05
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
(解説)答えは「分からない」なのだ。アガライさんが知らないってだけでなく、人類はまだこのクイズの答えを知らないのだ。 と言っても全く分からないわけでもないのだ。「全て一筆書きより難しい」か「全て一筆書きと同じくらい難しい」のどちらかなのだ。
2019-09-27 02:03:36
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
P≠NP予想というのを聞いたことがあると思うのだ。このP、NPというのは、問題の分類を表しているのだ。 ざっくり言うと、P問題は「簡単に解ける問題」、NP問題は「簡単に答えのチェックができる問題」なのだ。
2019-09-27 02:06:20
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
P問題はNP問題でもあるのだ。つまり、簡単に解ける問題は、答えのチェックも簡単にできるのだ。 ではその逆は？ まだ分からないのだ。NPだがPではない問題を人類はまだ見つけていないし、P問題とNP問題が一致することの証明もできていないのだ。
2019-09-27 02:11:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
P≠NP予想を解決するために、鍵になるであろう概念が、NP完全問題なのだ。 NP完全問題は、NP問題の中でも最も難しい問題なのだ。NP完全問題はいくつもあるのだが、そのうちの1つでもP問題であると証明されたなら、P問題とNP問題が一致することが従うのだ。
2019-09-27 02:14:33
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
一筆書きはP問題で、①〜③はNP完全問題なのだ。 グラフを見て、一筆書きできるかどうかは簡単に判定できるから、P問題なのだ。 そして、例えば数独は、数字が全部埋まってるものを渡されたら、それがちゃんと数独のルールを満たしているかは簡単にチェックできるのだ。それゆえ、NP問題なのだ。
2019-09-27 02:19:24
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
①〜③のNP完全性の証明については、アガライさんも詳しくないので省略するのだ。 ともあれ、このクイズの答えは、P問題とNP問題が一致しているなら「全て一筆書きと同じくらい難しい」、PでないNP問題が存在するなら「全て一筆書きより難しい」になるのだ。
2019-09-27 02:23:19
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
もしこのクイズの答えが分かったなら、すぐにクレイ数学研究所にコンタクトをとるのだ！ P≠NP予想には懸賞金がかけられているのだ。100万ドル、およそ1億ジャパリコインが君のものなのだ！
2019-09-27 02:25:26
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
集合は、高校では「数学的なものの集まり」のように、習ったと思いますの。これでは定義としてふわふわしすぎてますので、現代数学では、もっとカチッと決まってますわ。 「集合はどのような性質を満たすべきか」を考え、いくつかのルールにまとめ、そのルールを満たしているものを集合と呼んでますの
2019-10-16 00:13:14
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
そのルールは、考案した方々の頭文字をとって、ZF公理系と呼ばれてますの。もっとも、わたくしは集合論をやっているわけではないので、普段は意識しませんわ。よほどへんてこな集合を考えない限り、「数学的なものの集まり」という捉え方で困ることは少ないと思いますの。
2019-10-16 00:16:59
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
"よほどへんてこな集合"の例として、ラッセル集合というのがありますの。これは、「自分自身が属していない集合をあつめてつくった集合」ですの。 式で書けば R={X|X∉X}となりますわ。文だとややこしいですが、式だとシンプルですわね。
2019-10-16 00:21:18
専攻がわかラナイさん
@ranaisanra
R={X|X∉X}って時点で頭が混乱なのだ。自分自身が要素として属さない集合全体の集合……？ってどういう状況なのだ？？謎が深いのだ
2019-10-16 00:42:09
フジイさん(物理)
@physics_arai
@5f0zcHiur75F8lL パラドックスは混乱して正解なのだ笑 「もしかしたらこんな犯罪(矛盾)の可能性もあるかもしれない！」って普通じゃありえないような可能性を提示してきて「こういうことが起こらないように○○を規制しなきゃダメだ！」って新しく法律作るのを要求するようなことやってるのだ 数学ではこれが大事なのだ
2019-10-16 01:03:30
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
高校で扱うような、"ふつうの集合"……{1,3,5}や{2n | nは整数}、∅なんかは、どれもRに属しますわ。これらは、そもそも集合を要素として持っていませんもの。 むしろ、Rに属さないものがイメージしづらいかもしれませんわね。「全ての集合をあつめて作った集合」などは、きっとRには属さないですわ
2019-10-16 00:26:13
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
じゃあ、Rはどうなのでしょう？ RはR自身に属するのですか？ 考えてみましょう。まず、RがR自身に属すると仮定しますわ。 R={X|X∉X}でしたから、RがRに属するということは、R∉Rを意味しますの。……って、おかしいじゃありませんの！ RがRに属さないことになってしまいますわ！
2019-10-16 00:29:59
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
きっと仮定がおかしかったのですわ。RがRに属さないとしてみましょう。 R={X|X∉X}でしたから、RがRに属さないということは、R∉Rの否定、つまりRがRに属することを意味しますわ。……って、やっぱりおかしいじゃありませんの！
2019-10-16 00:31:50
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
これは困りましたわ。RがRに属するとしても、属さないとしても、矛盾が出てきてしまいますの。 では、"どちらでもない"が答えなのでしょうか？ うーん、もしかしたら、そういう流派もあるのかもしれませんが、わたくしは知りませんの。詳しいフレンズがいたら、教えてくださいな。
2019-10-16 00:35:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
もっとシンプルな解決策がありますの。それは、ラッセル集合を"のけもの"にしてしまう……つまり、「ラッセル集合は、実は集合ではない」ということにしますの。 実際、集合が満たすべき性質を満たしたルール……ZF公理系では、ラッセル集合は作れませんの。
2019-10-16 00:39:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
「ある条件を満たしているものをあつめてきて、集合を作る」という操作は、無条件にできるものではないと、この「ラッセルのパラドックス」は教えてくれますわ。矛盾というセルリアンが出てきてしまうことがありますから。
2019-10-16 00:44:22
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
じゃあ、ZF公理系で作った集合からは、矛盾は生まれないのかと言うと……実は分かりませんの。というのも、「いくつかの条件を満たしている体系が矛盾を生まないことは、その体系の中では証明できない」という定理――不完全性定理があるからですの。 ZF公理系は、不完全性定理の仮定を満たしていますわ
2019-10-16 00:47:21
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ただ今のところ、矛盾は見つかってませんし、わたくしもZF公理系は矛盾を生まないと信じてますの。 万が一矛盾が生まれたら……きっと大ニュースになると思いますわ。
2019-10-16 00:49:12
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
最後に少し補足を。「全ての集合をあつめて作った集合」を途中で考えましたが、実はこれもほんとうは集合じゃありませんの。 これは、「部分集合をあつめてつくった集合は、もとの集合よりたくさんの要素を持っている」という、カントールの定理により、集合じゃないと分かりますわ。
2019-10-16 01:00:14
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今日のお話はここまでですわ。質問・コメント・ツッコみ、もしあれば投げてくださいまし。お付き合いありがとうございました
2019-10-16 01:02:05
元東大限界博士のアライさん
@DoctorArai
@K9MmU7qClO9irZ3 のだ。 だとするとラッセル集合は存在しないのだ？ しないのに名前がついてるのだ？
2019-10-16 00:33:41