Kraft's Inequality: The Measure-Theoretic Condition for Prefix-Free Codes — E8 Intelligence Research

FINDING: Kraft's inequality is the exact measure-theoretic condition for a prefix-free code to exist over a binary tree, linking code lengths to a probability-like sum that must not exceed 1. | MATH: For a prefix-free code over alphabet size \(D\) with codeword lengths \(l_i\), Kraft's inequality: \(∑_i D-l_i ≤ 1\). Equality holds for complete (maximal) prefix-free codes. This is equivalent to the existence of a measure-preserving partition of the unit interval \([0,1]\) into subintervals of length \(D-l_i\), assigned in lexicographic order. The optimal prefix-free machine (universal Turing machine with prefix-free domain) has halting set satisfying this inequality, and its algorithmic probability \(m(s) = ∑U(p)=s 2-|p|\) is a semimeasure. | CONNECTION: The binary case \(D=2\) yields lengths \(l_i\) such that \(∑ 2-l_i ≤ 1\). The dyadic intervals of lengths \(2-l_i\) form a self-similar partition — a binary tree whose branching ratio is exactly 2. This is Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com