クラフトの不等式
すなわち我々は符号化関数 φ : S ∗ → T ∗ {\displaystyle \phi :S^{*}\to T^{*}} で以下の性質を満たすもののみを考える:
S上の任意の文字列 s i 1 s i 2 ... s i m {\displaystyle s_{i_{1}}s_{i_{2}}\ldots s_{i_{m}}} に対し、
φ ( s i 1 s i 2 ... s i m ) = φ ( s i 1 ) φ ( s i 2 ) ... φ ( s i m ) {\displaystyle \phi (s_{i_{1}}s_{i_{2}}\ldots s_{i_{m}})=\phi (s_{i_{1}})\phi (s_{i_{2}})\ldots \phi (s_{i_{m}})}
φが単射であるとき、φは一意に復号可能であるという。
アルゴリズム的情報理論において、チャイティンの定数は次のように定義される。
Ω = ∑ p ∈ P 2 − | p | {\displaystyle \Omega =\sum _{p\in P}2^{-|p|}}
これは、文法的に正しく停止する全てのプログラム毎にある被加数の総和である。|p| は p のビット列の長さを表す。プログラムは他のプログラムの接頭部とはならない。つまり、ある被加数は別の文法的に妥当で停止するプログラムを表す被加数の接頭部にはならない。従って、このビット列群は接頭符号であり、クラフトの不等式から Ω ≤ 1 {\displaystyle \Omega \leq 1} が成り立つ。