computation-theory - コルモゴロフ複雑度

Question

コルモゴロフの複雑さがランダム性とランダムな入力にどのように関連しているかを誰かが説明してくれたら、私はとても感謝しています。

私が理解できないもう 1 つのことは、与えられた入力 X のコルモゴロフ複雑度を計算することは決定できないことです。それを考えると、どのようにしてランダム性の尺度になるのでしょうか?

ありがとう

Answer 1

コルモゴロフ ランダムは、「ランダム」の漠然とした直感的な概念の特定の定義です。関係を求めるときに参照している他の定義はどれですか (参考http://en.wikipedia.org/wiki/Random_number )?

概念を明確に定義するために、どの文字列がコルモゴロフランダムであるかを一般的なケースで判断できなければならない理由を尋ねる際に、私はあなたの思考パターンに従いません。何が問題になっているのか詳しく説明していただけますか? 他に何もないとしても、停止の問題を指摘させてください。特定のプログラムがその特性を示すかどうかを一般的なケースで判断するためのアルゴリズムはありませんが、確かにプログラムの停止の概念は明確に定義されています。