# 通用较低的半区半释放和编码定理 -- computability 领域 和 probability-theory 领域 和 kolmogorov-complexity 领域 cs 相关 的问题

## Universal lower semicomputable semimeasure and Coding Theorem

2

### 问题

$$textbf {m}（x）= sum 2 ^ { - k（ mu）} mu（x）$$

I'm following Li and Vitanyi's book "An introduction to Kolmogorov complexity and its applications" 3ed. I'll rewrite here the definitions I need for my question.

The authors define the reference universal lower semicomputable semimeasure as

$$\textbf{M}(x) = \sum 2^{-K(\mu)} \mu(x)$$

where the sum goes over all lower semicomputable semimeasures. Moreover, they name $\lambda_U(x)$ the probability that the reference universal monotone machine $U$ computes a string that begins with $x$ when provided with coin-flip input.

Question 1: the authors claim that the two quantities above are equal, probably intending equality up to a multiplicative constant. It seems to me, however, that the multiplicative term is not constant but is only bounded. This seems to be confirmed by the fact that they state what should be a Coding theorem as $$-\log(\lambda_U(x)) = -\log(\textbf{M}(x)) + O(1)$$

Unfortunately they only sketch a proof, so it's not clear (to me at least) whether that $O(1)$ is actually a constant or not.
I would like to know whether equality (up to a multiplicative constant) actually holds, and in case, a reference to a proof would be appreciated.

Question 2: The authors claim $\textbf{M}$ is the probability that the reference universal monotone machine $U$ computes a string that begins with $x$ when provided with coin-flip input, but this interpretation is only allowed if equality (up to constant) holds among the two above quantities, otherwise I feel it is not legitimate. Am I wrong?

## 相关问题

4  kolmogorov决策问题的复杂性  ( Kolmogorov complexity of a decision problem )

2  多界Kolmogorov复杂性如何近似？  ( How approximable is time bounded kolmogorov complexity )

4  什么是复杂随机字符串的示例，在Kolmogorov-Chatin Sense中？  ( What is an example of complex random string in the kolmogorov chatin sense )

3  这个证据如何显示$O（1）$多项式界限的Kolmogorov复杂性的序列不是多项式可计算的Kolmogorov复杂性？  ( How does this proof show that sequences of o1 polynomially bounded kolmogoro )

2  （可操作）小问题的成本措施  ( Operationalizable cost measure for small problems )

1  证明$forall c in mathbb {n} ，存在x，y in sigma ^ * ，[k（xy）> k（x）+ k（y）+ c]$  ( Prove forall c in mathbbn exists x y in sigma kxy kx k )

1  一组假设的VC维度  ( Vc dimension of a set of hypothesis )

5  什么是静态复杂性？  ( What is static complexity )

1  表达*这个*复杂性概念的正确术语是什么？  ( What is the correct terminology for expressing this notion of complexity )

3  Kolmogorov串联的复杂性  ( Kolmogorov complexity of string concatenation )

5  函数何时将字符串映射到其前缀kolmogorov复杂性停止？  ( When does the function mapping a string to its prefix free kolmogorov complexity )

23  近似Kolmogorov复杂性  ( Approximating the kolmogorov complexity )

1  Kolmogorov两个数字的产品复杂性  ( Kolmogorov complexity of a product of two numbers )

4  为什么我们不能搜索lexicographicy有序的程序来计算Kolmogrov复杂性？  ( Why cant we search lexicographicaly ordered programs to compute kolmogrov compl )
kolmogrov复杂性是无形的。为什么我们不能以词典顺序枚举所有大小的所有程序= 0 - 如果有任何产生字符串s，那就是kolmogrov复杂性;如果没有，递增我并迭代？不会证明没有长度的程序＆lt;我生成字符串s？ ...

4  几乎是所有的自然数可压缩？  ( Are nearly all natural numbers compressible )
a 简单计数参数显示大多数字符串无法压缩到较短的字符串。但是，压缩通常使用Kolmogorov复杂性定义。如果其Kolmogorov复杂性小于其长度，则串是可压缩的，则为K（s）＆lt; | S | $。字符串的Kolmogorov复杂性被定义为在给定空白磁带时写入串的最小图灵机（TM）的大小。我想将TM的大小定义... 3 有多少“可压缩”字符串？ ( How many compressible strings are there ) 让我们说一串长度$ n $是"可压缩" IFF其Kolmogorov复杂性小于$ n $。为了保持简单，我们可以假设这一点。 很容易看到几乎所有的长度$ n $通过使用鸽孔原理是不可压缩的。 所以我的问题是，长度$ n $是的问题？ 特别是，让我们假设$ k（s）\$ 是二进制字符串的kolmogo...

3  门/晶体管数量和节目长度测量的计算复杂度？  ( Gate transistor number and program length measures of computational complexity )