(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
さて、作戦当日、アガライさんたちの探検隊は予定通りの時刻に攻撃を始めたのだが……。なんと、丘の向こうのフレンズが来てくれなかったのだ！ ガーンなのだ。 探検隊は撤退を余儀なくされたのだ……
2019-10-22 16:18:08
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
じゃあ、ここで #クイズなのだ 丘の向こうのフレンズは、どうして来てくれなかったのだ？ 少しだけ考えてみてほしいのだ。 答えは色々考えられると思うのだ。
2019-10-22 16:19:44
専攻がわかラナイさん
@ranaisanra
@K9MmU7qClO9irZ3 丘の向こうのフレンズはブラックバックにおっけーを出してから、ある問題に気づいたのだ。作戦を中止するよう、次の伝令を送ったものの、その人がこちらに来る前に約束の時間になったのだ。
2019-10-22 16:46:53
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@5f0zcHiur75F8lL それも正解の1つなのだ！ お見事なのだ！ 計算機はもちろん、とても速く処理を行うから、通信している間に状態が変わってしまうこともあるのだ。だから、通信にどれだけ時間がかかるかは、計算機同士に協力させるうえで、大事なポイントなのだ！
2019-10-22 16:54:45
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
では、アガライさんの用意していた答えを紹介するのだ！ 撤退したあと、ブラックバックは丘の向こうのフレンズにどうして来なかったのか、尋ねたのだ。 彼女達は、こう答えたのだ。 「自分たちが了承したことが、探検隊に伝わっているか分からなかった」
2019-10-22 16:58:11
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
これはどういうことなのか？ じっくり考えてみるのだ。 問題の条件を整理するのだ。 ①探検隊と丘の向こうのフレンズは、伝令を介してのみやりとりできる。 ②伝令は、道中でセルリアンに襲われる可能性がある。 ③攻撃時刻について合意がとれたと判断できなければ、攻撃を始められない
2019-10-22 17:03:14
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
おっともうひとつ、④フレンズは嘘をつかないとするのだ。 さて、探検隊は攻撃時刻を決めて、ブラックバックを伝令として派遣したのだ。 この段階では、探検隊も丘の向こうのフレンズも、相手について何の情報も持っていないのだ。
2019-10-22 17:06:31
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
では次に、ブラックバックが丘の向こうについたときなのだ。 この段階で、丘の向こうのフレンズは、探検隊が決めた攻撃時刻(仮に、朝の10時としておくのだ)を知るのだ。 一方、探検隊は、まだ、「丘の向こうのフレンズが攻撃時刻を知った」ことを知らないのだ。
2019-10-22 17:09:22
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
最後に、ブラックバックが探検隊のもとへ戻ってきたときなのだ。 この段階で、探検隊は「丘の向こうのフレンズが攻撃時刻を知った」ことを知るのだ。 だから、丘の向こうのフレンズと合意がとれたと判断したのだ。でも実はこれは、判断ミスだったのだ。
2019-10-22 17:11:29
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
なぜなら、丘の向こうのフレンズは、 「探検隊が『丘の向こうのフレンズが攻撃時刻を知った』ことを知った」 ことを知らないのだ。 頭がこんがらがりそうだが、がんばってついてきてほしいのだ。
2019-10-22 17:14:56
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
もし、ブラックバックが丘の向こうから帰って来るときに、セルリアンに襲われてしまったら、探検隊は、丘の向こうのフレンズに攻撃時刻が伝わったことを、確信できないのだ。 それゆえ、攻撃を中止せざるを得ないのだ。 そして、丘の向こうのフレンズには、彼女が無事に帰れたか分からないのだ。
2019-10-22 17:20:01
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
じゃあ、どうすればいいのか？ ブラックバックにもう一度伝令をお願いすればいいのか？ ……それでも上手くいかないことは、なんとなく分かると思うのだ。 「相手に伝わったかが分からない」という問題が、どこまでもどこまでも付きまとうのだ。
2019-10-22 17:23:02
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
残念なことに、この問題は解けないのだ。さっき挙げた条件のもとでは、決して合意に至ることはできないのだ。厳密には、背理法で証明されるのだ。 そこで、条件②を変えてみるのだ。
2019-10-22 17:27:39
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
②は「伝令は道中でセルリアンに襲われる可能性がある」だったのだ。これは計算機の世界では、「信頼できない通信路を使用している」ことに相当するのだ。 伝令の役割を、ハクトウワシにお願いするのだ。空を飛べば、セルリアンに襲われないのだ！
2019-10-22 17:30:00
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
これは、「信頼できる通信路を使用している」ことに相当するのだ。 情報が必ず相手に伝わるのであれば、合意には簡単に至れるのだ！ ……と言いたいのだが、まだそうとも言い切れないのだ。
2019-10-22 17:32:39
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ラナイさんが指摘してくれたように、「状況が変わったが、それを伝えるのに時間がかかる」というケースがあるのだ。 遠く離れた相手と合意するのは、簡単ではないのだ～ twitter.com/5f0zcHiur75F8l…
2019-10-22 17:37:40
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
以上、「計算機が協力し合うのは意外に難しい」という御伽噺なのだ。 質問・コメント・ツッコみ、もしあれば投げてほしいのだ。 お付き合い感謝なのだ！
2019-10-22 17:41:41
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
さて、久々にCSのお話をするのだ。今日は「文字列の複雑さ」についてなのだ。 突然だけどクイズなのだ。次のうち、一番複雑な文字列はどれなのだ？ ①0101010101010101 ②11011100101110111 ③1111010010000011
2019-11-07 00:26:47
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
直感的に、①は単純と言えそうなのだ。01が繰り返されてるだけなのだ。 ②も規則性がないように見えるけど、実は二進法で表した自然数を順に並べたものになってるのだ。 ③はとくに規則ないのだ。コイントスして生成した列なのだ
2019-11-07 00:32:49
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
というわけで、直感的には③が一番複雑そうなのだ。それは規則性がないから、言い換えると「簡潔に言い表せない」からなのだ。 この直感を、数学的に定式化したものが今日のテーマ、「コルモゴロフ複雑性」なのだ
2019-11-07 00:35:10
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
簡単のため、文字列は0と1からだけで構成されるとするのだ。コンピュータ上のデータだと思ってくれていいのだ。 文字列sのコルモゴロフ複雑性は、「sを出力するプログラムと入力の組で、最短のものの長さ」と定義されるのだ
2019-11-07 00:37:56
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
例えば、①を生成する「プログラムと入力の組」としては、「入力を8回繰り返した文字列を出力するプログラムと、入力"01"」や「入力を無視して0101………01を出力するプログラムと、入力""」などが考えられるのだ。 こういったものの中で、最短のものの長さが①のコルモゴロフ複雑性になるのだ
2019-11-07 00:41:27
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ここで、「入力をそのまま出力するプログラムR」を考えてみるのだ。 任意の文字列sは、Rにsを入力すると得られるのだ。 従って、sのコルモゴロフ複雑性は (Rの長さ)+(sの長さ)以下だと分かるのだ。 Rはsに依らないから、どんな文字列sもそのコルモゴロフ複雑性は (sの長さ)+定数で抑えられるのだ
2019-11-07 00:47:41
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
コルモゴロフ複雑性が、自身の長さより小さい文字列は、"圧縮できる文字列"だと考えられるのだ！ すると、与えられた文字列が圧縮できるかできないか、できるならどこまで圧縮できるか知りたくなるのだ。 でも残念ながら、それはできないのだ。 言い換えると、コルモゴロフ複雑性は計算できないのだ
2019-11-07 00:53:01
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ではそのことを証明するのだ。以下、文字列sのコルモゴロフ複雑性をC(s)で表すのだ。 コルモゴロフ複雑性が計算可能と仮定するのだ。そして、次のようなプログラムを考えるのだ 入力: 自然数n 出力: C(s)がn以上の文字列s
2019-11-07 01:00:06
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
今文字列は0と1から成るとしてるから、コルモゴロフ複雑性がn未満の文字列は高々2^n-1個しかないのだ。 だから、例えば辞書順にコルモゴロフ複雑性を計算すれば、いつかはC(s)がn以上の文字列sが見つかるのだ。 コルモゴロフ複雑性は計算可能と仮定してるから、ループに陥ることもないのだ
2019-11-07 01:06:49
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
もちろんそのような文字列sは複数あるかもしれないのだ。でも別にどれを選んでもいいのだ。気になるなら、最初に見つかったものを出力すると思ってほしいのだ。 この入力nに対しC(s)がn以上のsを出力するプログラムを、Pとするのだ。 そして、Pのnに対する出力をs_nとおくのだ。
2019-11-07 01:15:41
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
ここで、s_nのコルモゴロフ複雑性を考えてみるのだ！ まず、Pの定義からC(s_n)はn以上なのだ。 一方、sのコルモゴロフ複雑性は「sを出力するプログラムと入力の組のうち、最短のものの長さ」と定義されていたのだ。 このことから、C(s_n)は (Pの長さ)+(nの長さ)以下だと分かるのだ
2019-11-07 01:19:54
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
自然数nの長さというのは、要するに桁数なのだ。ただし今使える文字は0と1だけだから、二進表記したときの桁数なのだ。 例えば、十進法の14は二進法で1110だから長さは4なのだ。 そして、nの桁数は、1+log_2 nで抑えられるのだ。 これは、2^kがk+1桁ということから分かるのだ
2019-11-07 01:27:42
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
すると、C(s_n)について、次の2つの不等式が成り立つのだ。 C(s_n) >= n C(s_n) <= (Pの長さ) +1 +log_2 n (＊) グラフから分かるように、1次関数は対数関数よりずっと速く大きくなるのだ。 Pの長さは定数だから、nが十分大きければ、(＊)の右辺より大きくなって、矛盾するのだ！
2019-11-07 01:33:36
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
矛盾が導かれたので、「コルモゴロフ複雑性は計算可能」は間違いだと分かったのだ。 証明をまとめると 1. コルモゴロフ複雑性が計算可能なら 2. nに対し「n文字未満で表せない文字列s」を返すプログラムがあるが 3. nが大きければsはn文字未満で表せてしまう という流れなのだ！
2019-11-07 01:43:05
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
補足なのだ。 ここではコルモゴロフ複雑性をプログラムの長さを使って定義したのだが、チューリングマシンの記述の長さを使って定義されることもあるのだ。 でも大きな違いはないのだ、今回の話も読み替えられるのだ
2019-11-07 01:49:59
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
以上、「文字列の複雑さ」についてのお話なのだ。 質問・コメント・ツッコみ、もしあれば投げてほしいのだ。 お付き合い感謝なのだ！
2019-11-07 01:51:17
自動運転されてるalley-san
@wuesten_schnee
@K9MmU7qClO9irZ3 随分と前に受けた、データ構造とアルゴリズム扱ってた講義を思い出したのだ データ圧縮をどこまでできるかどうかも関わるで良いのでしたっけ？なのだ
2019-11-07 01:55:42
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@wuesten_schnee あるデータXを圧縮してYになったなら、Yの長さ+解凍プログラムの長さはXのコルモゴロフ複雑性を下回れないのだ。 そういう意味で、どこまで圧縮できるかにも関係してるのだ！ ただ、実際の現場でコルモゴロフ複雑性がどういう扱いなのかはアガライさんは知らないのだ……
2019-11-07 02:06:09
自動運転されてるalley-san
@wuesten_schnee
@K9MmU7qClO9irZ3 なるほどなのだ、教えてくれてありがとうなのだ！ 実際の現場はわかんないねーなのだ。それこそ可逆圧縮を使うお仕事なんて限られてると思うのだ…色々ファイル形式の多い映像ちほーの方々が使ってらっしゃるのかなーなのだ（混乱）
2019-11-07 02:11:02
すしを届ライさん（すしイ）
@LA12631311
@K9MmU7qClO9irZ3 ･プログラムの停止性問題(Pは本当に文字列を返すのか) と、 ･自己言及のパラドックス(PはP自身を含む文字列をどう処理するか) という2つの難問が重なってるのだ。 計算量の上限を定めれば便宜上解決出来そうではあるのだ。
2019-11-07 21:51:36
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 アガライさんはどっちも大丈夫だと考えてるのだ！ 1つ目だが、ある入力nに対し、Pが止まらないと仮定するのだ。 これは、すべての文字列のコルモゴロフ複雑性がn未満であることを意味するのだ。 でもそれはおかしいのだ。→
2019-11-07 23:48:58
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 長さがn未満の文字列は2^n-1個しかないから、 「長さn未満の文字列から復元できる文字列」も高々2^n-1個しかないのだ。 だから文字列を辞書順に調べていけば、いつかは必ずコルモゴロフ複雑性がn以上の文字列が見つかるのだ！ →
2019-11-07 23:49:30
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 2つ目は、Pはコルモゴロフ複雑性を計算するプログラムKを内部に持っているとイメージしてほしいのだ。 Pは文字列を順にKに渡せばいいのだ。具体的に渡すから、自己言及はしないし、Kはどんな文字列に対してもコルモゴロフ複雑性を返すから、たとえプログラムを渡されても問題なく計算してくれるのだ！
2019-11-07 23:52:04
すしを届ライさん（すしイ）
@LA12631311
@K9MmU7qClO9irZ3 まさにそのKが問題なのだ。 Kは渡された文字列の「最短表現候補」から最短の表現を探すけど、候補の中には無限ループを含むプログラムや、天文学的な時間がかかるけども目標の文字列を出力するプログラムが含まれるのだ。 それらを全て検証することはそもそも不可能なのだ。
2019-11-08 02:08:05
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 ここでの計算可能性は、計算量は考えてないのだ。たとえ1兆年かかっても答えが出るなら計算可能としているのだ また、最短表現候補を単に順に調べたなら、確かにループがあると困るのだが、候補に1,2,3,…と番号を振って、1→2→1→3→2→1→4……の順で1ステップずつ動かせばループには陥らないのだ→
2019-11-08 02:23:06
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 ただ、ここではコルモゴロフ複雑性を計算するようなプログラムKが存在しないことを言いたいのだから、Kの細かい動作はあまり気にしなくていいのだ〜。 どんな動作をしようと、矛盾は導かれるのだ
2019-11-08 02:24:31
すしを届ライさん（すしイ）
@LA12631311
@K9MmU7qClO9irZ3 確かに問題の本質ではないのだけど、気になるのだ。 n文字以下の候補にループがあった場合、そのループが正しい文字列を出力しないとは決して確定出来ないから、C(s_n) >= nである事自体が確定出来ないのだ。 これは計算順序を変えても変わらないのだ。
2019-11-08 03:08:03
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 では、説明を変えてみるのだ。「アガライさんが考えたような愚直なアルゴリズムだと、ループを見抜けることになってしまう。この問題を回避する巧いアルゴリズムがあったとしても、矛盾を引き起こしてしまう、だからKは存在しない」ではどうなのだ？→
2019-11-08 21:02:32
(博士課程で)足掻(くア)ライさん
@K9MmU7qClO9irZ3
@LA12631311 実際、これはアガライさんも調べて初めて知ったのだが、コルモゴロフ複雑性を計算するプログラムがあったなら、それを使って停止問題を解けるのだ。
2019-11-08 21:04:54