PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
create new user
forget your password?
Main Menu
Kolmogorov complexity upper bounds (Theorem)

$\displaystyle C(x) \leq l(x) + O(1). $

This follows from the invariance theorem applied to a machine that copies the input (which is delimited with a blank) to the worktape and halts.

$\displaystyle C(x\vert y) \leq C(x) + O(1). $

This follows from a machine that works like $ U$ but which starts out by erasing the given string $ y$ from its worktape.

$\displaystyle K(x) \leq K(y) + K(x\vert y) + O(1). $

This follows from a machine that expects an input of the form $ pq$, where $ p$ is a self-delimiting program for $ y$ and $ q$ a self-delimiting program to compute $ x$ given $ y$. After simulating $ U$ to obtain $ y$ on its worktype, it continues to simulate $ U$ again, thus obtaining $ x$.

$\displaystyle K(x \vert l(x)) \leq l(x) + O(1). $

This follows from a machine $ M$ which uses a given number $ n$ to copy $ n$ bits from input to its worktape.

"Kolmogorov complexity upper bounds" is owned by tromp.
(view preamble)

View style:

Cross-references: string, invariance theorem

This is version 1 of Kolmogorov complexity upper bounds, born on 2003-07-04.
Object id is 4421, canonical name is KolmogorovComplexityUpperBounds.
Accessed 725 times total.

AMS MSC68Q30 (Computer science :: Theory of computing :: Algorithmic information theory )

Pending Errata and Addenda
Style: Expand: Order:
forum policy

No messages.

rate | post | correct | update request | prove | add result | add corollary | add example | add (any)