今日は邦書メイン。
- informationの定義はいくつかある。ここではcomputability theoryを使った定義を確認する。
- 言葉の定義
- x: 二進文字列
- d(x): xの最小記述
- <M,w>:テープ上にxを設定して停止するTM Mとその入力wの記述。二進文字列。
- K(x): <M,w>のうち最も長さが短いもの。(同じ長さの場合は辞書式で若い方)記述の複雑さ、またはKolmogorov複雑さと呼ぶ。K(x)=d(x)である。
- x: 二進文字列
- 定理を丁寧に理解する。
- 定理6.24
∃c∀x[K(x) <= |x| + c]- この定理は、アルゴリズムによる情報の記述を採用すると、場合によって、表現したい情報そのものよりも長くなってしまうのであるが、それは入力の文字列のあり様にかかわらず、せいぜい定数であるということ。
- これは起動したら何もせず定義するTMをNとすると、
d(x)の候補: <M,w> = <N,x> = <N>x
K(x) = |d(x)| <= |<N>x| = |x| + |<N>|
最後の項はxによらず定数。定理を確認できた。
- この定理は、アルゴリズムによる情報の記述を採用すると、場合によって、表現したい情報そのものよりも長くなってしまうのであるが、それは入力の文字列のあり様にかかわらず、せいぜい定数であるということ。
- 定理6.25
∃c∀x [K(xx) <= K(x) + c]- この定理が意味するところは、入力文字列を二度繰り返すことによってどれくらい情報量が増えるかというとたいして増えなくて、単一の入力だったときとくらべると、入力文字列のあり様に関わらず、せいぜい定数だということ。
- TM Dは、<N, w>を入力として受け取り、Nを入力wでシミュレートした後で、その出力文字列を二回出力するとする。
- これのwをxに変えたものとしてd(x)を選ぶ。
- d(x)を入力とするDはxxを出力するので、K(xx)候補ではある。
d(xx) の候補: <:D,w> = <D>d(x)
K(xx) <= |<D>d(x)| = |<D>| + |K(x)| - これで定理を確認できた。
- この定理が意味するところは、入力文字列を二度繰り返すことによってどれくらい情報量が増えるかというとたいして増えなくて、単一の入力だったときとくらべると、入力文字列のあり様に関わらず、せいぜい定数だということ。
- 定理6.26
∃c∀x,y [K(xy) <= 2K(x) + K(y) + c]- この定理が意味するところ。K(xy) <= K(x) + K(y) + c と予測されるが、そうではなくて連結はもう少し情報を含んでいる、またはコストがかかる、ということ。
- 入力は0or1から成る。
- xyを出力するTMを考えるときに情報として、xとyの区切りを認識する必要がある。
- この2つのことを鑑みて、xの文字を全て2個ずつにして(010なら001100)、yとの区切りを01とする手法をとるとする。x,yからこの手法で構成した文字列をwと呼ぶ。xを2倍にしたものをx'と呼ぶ。
- 今作成中のTMをMと呼ぼう。
- Mは3つの部分からなるとする。
- M1. 全体を統合管理するとともに、x'とyに分離して他の部分に渡す処理。
- M2. x'を受け取りxを出力する部分
- M3. yを受け取りyを出力する部分
- M1. 全体を統合管理するとともに、x'とyに分離して他の部分に渡す処理。
- 。。。いきづまった。
- あれ、この定理、シプサ先生が書いているほど、自明じゃないんじゃないか???
- 深掘りはやめて、先に進むことにする。
- この定理が意味するところ。K(xy) <= K(x) + K(y) + c と予測されるが、そうではなくて連結はもう少し情報を含んでいる、またはコストがかかる、ということ。
- xyのencodingとして、xの長さ(整数)を冒頭につけて、それを00,11方式で書くとすると、
2log(K(x)) + K(x) + K(y) + c
までは追い込める、とな。 - 定義の最適性
- 言葉の定義。
- 計算可能な関数 p: Σ* -> Σ* を、一般的な記述言語と呼ぶ。
- 情報化対象となる二進文字列をxと呼ぶ。
- p(y) = xとなるyのうち、最短かつ辞書式最若のものをsと呼ぶ。
- pに関するxの最小記述をdp(x)と呼び、それはsであるとする。
- Kp(x) = |dp(x)|と定義する。
- LISPだとしたときの例。
- dlisp(x)は、xを出力する最小のLISPプログラム。
- Klisp(x)は、そのプログラムの長さ。
- 定理6.27
「任意の記述言語pに対して、pだけに依存する定数cが存在して、次が成り立つ。
∀x [K(x) <= Kp(x) + c]」- ある記述言語pについて、次のようなTM Mを考える。
- 入力wに対して、p(w)を出力する。
- 入力wに対して、p(w)を出力する。
- xのpによる記述がwであるとする。
- Mは言語Pのインタープリタといえる。
- すると、情報としてのxの記述は、<M,w> となる。
- 定義より、|<M,w>| = |<M>dp(x)| = |<M>| + |dp(x)| = |<M>| + Kp(x)。
- これは、xのアルゴリズムによる最小記述候補だから、
K(x) <= Kp(x) + |<M>|
が確認できた。
- ある記述言語pについて、次のようなTM Mを考える。
- 圧縮不可能な文字列とランダム性
- 言葉の定義。
- c圧縮可能： K(x) <= |x| - c なるcが存在すること。
- xが1圧縮不可能なとき、xは圧縮不可能である、と言う。
- 定理6.29
「あらゆる長さに対して、その長さの圧縮不可能な文字列が存在する」- おお！ この定理の証明、簡単かつ強力。すごい。
- おお！ この定理の証明、簡単かつ強力。すごい。
- 系6.30
「長さnの文字列全体で少なくとも2^n-2^(n-c+1)+1個の文字列は、Cで圧縮不可能である。 - 定理6.31と定理6.32は感じだけ掴んでおく。
おお、第二巻の本文を読了した！！
長かった。。。
次回は章末演習。章末演習を越えれば、ついに最終巻だ！
0 件のコメント:
コメントを投稿