(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
矛盾が起きたので、最初の仮定「Rは可算集合」は間違いなのだ！ つまり、実数全体Rは非可算集合、正の整数全体とは1対1の対応を作れない集合なのだ！
2019-11-30 00:44:34
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
Rは正の整数全体Nを真に含んでいるから、さすがにRの大きさがNの大きさより小さいとするのは不合理に思えるのだ。 というわけで、Rの大きさはNの大きさより大きいのだ！ すると次に気になるのが、RはNと比べてどのくらい大きいのか？ ということなのだ。
2019-11-30 00:51:40
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
例えば、Nよりは大きいが、Rよりは小さいサイズの集合は存在するのか？ それとも、そんなものはなくて、「Rの大きさ」は「Nの大きさ」の"次の大きさ"なのか？ この問いの答えは「分からない」なのだ。 アガライさんが知らないということではないし、人類がまだ知らないということでもないのだ。
2019-11-30 00:54:13
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
現代数学の標準的な枠組み、ZFC公理系では、「Nよりは大きいが、Rよりは小さいサイズの集合が存在する」という主張を、証明も反証もできないのだ。 そういう集合が存在している体系も、存在していない体系もありうるのだ。
2019-11-30 01:00:21
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
証明も反証もできないのは、公理が不足しているからだとも考えられるのだ。でもそれなら、いったいどんな公理を付け加えたらいいのだ？ ↑の主張は、本当は正しいのだ？ 間違ってるのだ？ Rの本当の大きさは何なのだ？ 興味あるフレンズは「連続体仮説」で調べて、そして解き明かしてほしいのだ！
2019-11-30 01:05:25
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今日のお話はここまでなのだ。 質問・コメント・ツッコみ、もしあれば投げてほしいのだ。 お付き合い感謝なのだ！
2019-11-30 01:06:20
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@DoctorArai んー、ほとんどの場合、ZFC公理系が使われてると思うのだ。 数学基礎論では他の公理系も考えると思うが……、いや、アガライさんは基礎論は詳しくないからなんとも言えんのだ
2019-11-30 06:43:36
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ひっさびさにCSのお話をするのだ。今日のテーマは計算機のモデルなのだ。 計算機のモデルと言っても、色々種類があるのだ。今日は、決定性有限オートマトン(Deterministic Finite Automaton)について話すのだ。 長いので以下、DFAと略すのだ。
2020-01-18 21:55:02
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
DFAは入力として有限の長さの文字列が与えられたときに、それを「受理」もしくは「拒否」するのだ。 これは、与えられた文字列がある性質を持っているか否かを判定している、と考えてほしいのだ。
2020-01-18 21:57:04
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
例えば、与えられた自然数が3の倍数かどうか判定するDFAは、27や60や3141は受理するが、13や61や1414は拒否するのだ。
2020-01-18 21:59:23
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
DFAは、内部に有限通りの状態を持っているのだ。入力された文字列を1文字ずつ読み取りながら、読み取った文字に応じて、内部状態を変化させることにより計算を行うのだ。
2020-01-18 22:02:17
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
具体例として、3の倍数かを判定するDFA Mの動作を考えてみるのだ！ フレンズのみんなは、3の倍数かを判定するときは、各位の和が3の倍数になってるかを調べると思うのだ。このMも、その方針で動作するのだ。
2020-01-18 22:05:02
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
Mは内部に、0,1,2という3つの状態を持っているのだ。これは、今考えている値の3で割った余りを保持するための状態なのだ。 0→1→2→0→1→……の順で、読み取った数字の分だけ状態を変化させるのだ。 例として、31415が入力されたときの、Mの動作を考えてみるのだ。
2020-01-18 22:10:47
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
いや、ちょっと後の説明に支障があるのだ。まどろっこしくなってしまうが、Mの状態変化を 現在の状態の値に読み取った数字を3で割った余りを足し、さらにそれを3で割った余りに変化させる と訂正するのだ。 DFAは1文字読むごとに、状態の変化が1回起こるのだ。さっきのは誤解を招く表現だったのだ
2020-01-18 22:17:47
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
例えば状態0のときに数字'4'を読んだなら、0に「4を3で割った余り」すなわち1を加え、それをさらに3で割った余り、すなわち1へと状態が変化するのだ。 状態2のときに数字'8'を読んだなら、2に2を加え、3で割った余りの1へ状態が変化するのだ
2020-01-18 22:19:53
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
改めて、Mに31415が入力されたときの動作を考えるのだ。 状態0からスタートするのだ。まず1文字目は'3'だから、0から0へと変化する、つまり実質変化なしなのだ。 2文字目は'1'だから、0から1へ変化するのだ。 3文字目は'4'だから、1から2へ。 4文字目は'1'だから、2から0へ。
2020-01-18 22:24:50
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
そして5文字目は'5'だから、0から2へ変化するのだ。 入力を全部読んだ後、状態が0になっていれば、入力は3の倍数。状態が0でなければ、入力は3の倍数でないと判定できるのだ。 今の例だと、状態2で終えているから、31415は3の倍数でないと判定されるのだ。
2020-01-18 22:27:01
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
別の例として、文字列の長さが偶数かを判定するDFAを考えてみるのだ。 これの動作はさっきよりシンプルなのだ。0,1という2つの状態を持ち、状態0からスタートして、1文字読むたびに0から1、1から0、と交互に変化させていけばいいのだ。 全部読んだ後、状態0だったなら、長さは偶数なのだ
2020-01-18 22:34:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
より高度な例としては、2進数で与えられた整数が、5の倍数かを判定するDFA、というのもあるのだ。 さらにいうと、任意に固定された自然数nに対し、2進数で与えられた整数がnの倍数かを判定するDFAもあるのだ。
2020-01-18 22:39:15
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
DFAはシンプルな計算モデルだが、色々な性質を判定してくれるのだ！ ……しかしながら、決して万能ではないのだ。DFAでは判定できない性質というのも、世の中には存在するのだ。
2020-01-18 22:41:27
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
鍵を握るのが、ポンピング補題なのだ！ これは、 DFA Mが十分長い文字列sを受理するなら、sのある部分文字列を"ポンプ"して得られる文字列s'も、Mは受理する という主張なのだ。 (実際にはもう少し強い主張なのだが、本質的なのは上記の部分なのだ)
2020-01-18 22:45:51
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
文字列のポンプとは、文字列を繰り返す、または削除することなのだ。 例えば、abbcabbという文字列で、"cab"をポンプすると、 abbb (削除した) abbcabcabb (2回繰り返した) abbcabcabcabcabb (4回繰り返した) などが得られるのだ！
2020-01-18 22:48:43
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ポンピング補題を証明してみるのだ。 DFA Mの状態数をnとするのだ。そしてMは長さがn以上の文字列sを受理すると仮定するのだ。 DFAは1文字読むごとに状態変化が1回起こるのだから、sを全部読むまでに、状態変化がn回以上起こるのだ。
2020-01-18 22:52:52
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
状態数がnなのだから、その間に複数回現れる状態があるはずなのだ！ 文字列sをs=xyz と分割するのだ。ここで右辺は、文字列x,y,zを繋げた文字列を表すのだ。 例えば、 s="abbcabb" x="abb" y="cab" z="b" のとき、s=xyzと表せるのだ。
2020-01-18 22:56:57
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
DFA Mは、s=xyzを読む過程にて、xまで読んだ直後と、xyまで読んだ直後で、同じ状態tになったとするのだ。 DFAがどのように状態を変化させるかは、そのとき読んだ1文字と現在の状態だけによって決まることに注意してほしいのだ。 それまでにどんな文字列を読んできたかは、影響しないのだ。
2020-01-18 23:00:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
xまで読んだ直後と、xyまで読んだ直後で、同じ状態tになったということは、 状態tからスタートして、文字列yを読むと、状態tに戻ってきた ということなのだ。 つまり文字列yは、状態変化のループを引き起こしているのだ！
2020-01-18 23:04:05
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
このことから、Mがsを読んで到達する状態と、sの部分文字列yを"ポンプ"して得られる文字列s'を読んで到達する状態は、一致するのだ！ それゆえ、Mがsを受理するなら、s'も受理するのだ！
2020-01-18 23:05:26
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
DFAで判定できない性質の1つに、 文字列が a^n b^n の形式をしている (＊) というものがあるのだ。ここでnは0以上の整数で、a^nはn個の連続したaを意味するのだ。 つまり、aaabbbやabは(＊)を満たすが、aabやaabbaabb、bbaaなんかは(＊)を満たさないのだ
2020-01-18 23:10:18
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ポンピング補題を使えば、(＊)を判定するDFAが存在しないことが示せるのだ。 そのようなDFA Mが存在すると仮定するのだ。 Mは、a^m b^m という文字列を受理するのだ。ここでmは十分大きな整数なのだ。 ポンピング補題より、ある部分文字列があって、それをポンプして得られる文字列も受理されるのだ
2020-01-18 23:14:16
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
でも、そんなことあり得ないのだ。 部分文字列がa^k、あるいはb^kという形式なら、ポンプするとaの個数とbの個数が一致しなくなるのだ。 かといって、a^k b^l という部分文字列をポンプしたら、全体がa^n b^nという形式じゃなくなるのだ。 矛盾が導かれたので、このようなMは存在しないと分かるのだ！
2020-01-18 23:16:52
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
(＊)も判定できる、より強力な計算モデルの1つに、プッシュダウンオートマトンというものがあるのだが……それはまた、別の機会に。 今日のお話はここまでなのだ！ 質問・コメント・ツッコミは大歓迎なのだ！ お付き合いありがとうなのだ！
2020-01-18 23:20:52