Kolmogorov complexity: Difference between revisions

Revision as of 07:44, 30 June 2024

Revision as of 09:03, 21 July 2024

Line 381:

Note. <math>U(p) = x</math> does not mean that the input stream is <math>p000\cdots</math>, but that the universal Turing machine would halt at some point after reading the initial segment <math>p</math>, without reading any further input, and that, when it halts, its has written <math>x</math> to the output tape.

'''Theorem.''' (Theorem 14.11.1 <ref name=":1" />) <math>\log \frac{1}{P(x)} = K(x) + O(1)</math>

==Conditional versions==