PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Kolmogorov complexity function (Definition)

The (plain) complexity $ C(x)$ of a binary string $ x$ is the length of a shortest program $ p$ such that $ U(p)=x$, i.e. the (plain) universal Turing machine on input $ p$, outputs $ x$ and halts. The lexicographically least such $ p$ is denoted $ x^{\ast}$. The prefix complexity $ K(x)$ is defined similarly in terms of the prefix universal machine. When clear from context, $ x^{\ast}$ is also used to denote the lexicographically least prefix program for $ x$.

Plain and prefix conditional complexities $ C(x\vert y), K(x\vert y)$ are defined similarly but with $ U(x\vert y)=x$, i.e. the universal machine starts out with $ y$ written on its worktape.

Subscripting these functions with a Turing machine $ M$, as in $ K_M(x\vert y)$, denotes the corresponding complexity in which we use machine $ M$ in place of the universal machine $ U$.



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

View style:

Other names:  algorithmic entropy, information content

Cross-references: place, Turing machine, functions, clear, universal, terms, prefix, universal Turing machine, length, string, binary

This is version 6 of Kolmogorov complexity function, born on 2003-07-03, modified 2004-02-29.
Object id is 4418, canonical name is KolmogorovComplexityFunction.
Accessed 2479 times total.

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

Pending Errata and Addenda
None.
[ View all 2 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)