|
小野です。
> > logical depth なんてのもあります。
与えられた数列の複雑さについて、
それを計算するためのプログラムの長さと
それを計算するためにかかる時間(ステップ数)との
両方を考慮して決められる指数です。
NP問題のように、簡単なプログラムで答えが得られても
計算が終了するまでの時間が膨大になってしまうような
問題が数学にはあります。
情報量を議論する場合にこのような問題があると、
Kolmogorov complexity は低いが、実質計算できない、
という数列などがあり得ることが考えられるでしょう。
そこでとりあえず、プログラムと計算時間の
折衷案をとったのが logical depth と言えます。
string x が (d,b)-deep であるとは、x が、
最大圧縮率 b かつ 最小ステップ数 d の情報である、
という意味になります。
(ただ併記しただけとという説もありますが．．)
原典は
G. J. Chaitin, IBM J.Res.Develop., 21(1977), 350-359.
C.H.Bennett, "The Universal Turing machine: a half-century
survey", R. Herken(Ed.), Oxford Univ. Press, 1988, pp. 227-258.
などだそうです。
----- |
|
|
