下半可计算半测度

质量表示随机输入落在某个会停机输出 $x$ 的程序上的概率。模拟只能发现已经停机的程序，不能把尚未停机的程序可靠地宣布为永不停止。因此每个输出的质量往往只有向上的近似。

丢失质量有两种可兼容解释：随机比特没有形成被接受的程序，或形成的计算没有终止。只观察输出分布时，两者都表现为总质量不足一；若应用需要区分原因，模型必须另加状态。

多个程序会把质量汇到同一输出 ​

设一台机器仅在程序 0、10、110 上停机，分别输出 $a$、$a$、$b$。这三个程序前缀自由，因此

剩余 $1/8$ 没有输出。若模拟先发现 110，再发现 0，最后发现 10，$m_s(a)$ 会从 $0$ 跳到 $1/2$ 再到 $3/4$；不需要按程序长度发现，也不能在尚未发现 10 时断言 $a$ 的质量已算完。

下半可计算通常不等于可计算 ​

取一个不可计算的左 c.e. 实数 $\alpha \in (0,1)$，令 $m(a)=\alpha$、其余输出质量为零，就得到下半可计算半测度，却不是可计算分布。相反，若一个离散下半可计算半测度已知总质量恰为一，则每个 $m(x)$ 都可计算：其他输出的质量和从下逼近，给 $1-\sum _{y\ne x}m(y)$ 从上逼近；上下界最终夹到任意精度。

这一论证说明归一化不是无害修饰。若总质量本身不可计算，除以它可能破坏有效性；不能先强行归一化，再声称得到可计算概率分布。

同一个名称还有树版本 ​

有些文献把 $M:2^{<\mathbb{N}}\to [0,1]$ 满足

称为连续或树半测度。这里 $M(\sigma )$ 是输出延续某前缀的质量，不是输出恰好等于 $\sigma$ 的质量。两种约定不可把同一个公式直接互换；后续编码定理公理库算法编码定理Algorithmic coding theorem · Levin coding theorem证明通用离散算法概率的负对数等于前缀复杂度加常数，并用阈值编码展示如何把可枚举质量变成短描述。使用本页的离散版本。

存在一个通用下半可计算离散半测度 $m$，对任意同类半测度 $\nu$ 都有常数 $c_{\nu }>0$，使 $m(x)\ge c_{\nu }\nu (x)$。构造先有效枚举经过预算约束的候选半测度，再作混合 $\sum _e{2}^{-e-1}{\nu }_e$。逐个分量的系数保证总质量不超过一，并给出对第 $e$ 个分量的支配常数。

这不是逐点取最大值，后者可能超出总预算。算法编码定理公理库算法编码定理Algorithmic coding theorem · Levin coding theorem证明通用离散算法概率的负对数等于前缀复杂度加常数，并用阈值编码展示如何把可枚举质量变成短描述。进一步证明通用质量的负对数与最短前缀描述长度只差一个常数。