文字列をプレフィックスのないコルモゴロフの複雑さにマッピングする関数はいつですか？

Question

の アルゴリズムのランダム性と複雑さ DowneyとHirschfeldtから、129ページに記載されています

$ qquad displaystyle sum_ {k（ sigma） downarrow} 2^{ - k（ sigma）} leq 1 $、

ここで、$ k（ sigma） downarrow $は、$ k $が$ sigma $、$ sigma $がバイナリ文字列であることを妨げることを意味します。 $ k $は、プレフィックスフリーのコルモゴロフの複雑さを示します。

$ k $はいつ停止しますか？コルモゴロフの複雑さの非計算性に関する古典的な証拠は、$ k $のドメインに上限を与えるため、有限の数の入力を停止するだけだと思います。ただし、$ k $ haltsを任意に選択できる有限の入力セット（ソースコードに有限数の複雑さを保存する必要があります）。

それで、この合計は明確に定義されていますか？言い換えれば、$ k $のドメインは明確に定義されていますか？

Answer 1

あなたは正しいと思います。 $ k $は、計算できない特定の関数です。著者はおそらく使用することを意味します いくつかの （任意の）近似実装。いいえ、あなたがペダンティックであれば、これは明確に定義されていないようです。また、表記法の悪用と呼ぶこともできます。

代わりにこれを考えてみてください：

$ qquad displaystyle forall {m in mathcal {m} _k}

$ mathcal {m} _k = {m mathrm {tm} mid m（ sigma）！ downarrow は m（ sigma）} $ k $のサブファクションを計算するすべてのチューリングマシン。

本質的に、これは次のことを意味します。バウンドは、実装がコルモゴロフの複雑さを計算できる文字列に関係なく保持されます。

---

Carlがコメントで指摘しているように、$ K $が計算できないため、表記は停止や計算とは関係ないことがもっともらしいです。 $ sum_ {k（ sigma）！ downarrow} $ $ k $のドメイン上の範囲を読み取ります。