Title: Theory / Unimportant / CS / Fundamental / Algorithmic randomness and complexity / I - Background / 3 - Kolmogorov complexity of finite strings
Tags: hasSeenConjDef examplesSwitchExample1

Name: The Kolmogorov complexity of \(\sigma\)
Definition: The minimal length of a string \(\tau\) such that \(f(\tau)=\sigma\)
Page: 111
Chapter: 3
Section: 1
Variables: \(\sigma\) a finite string,
\(f:2^{<\omega}\to2^{<\omega}\)
Notation: \(C_f(\sigma)\)

Name: A string random relative to \(f\)
Definition: A string \(\sigma\) such that \(C_f(\sigma)\ge|\sigma|\)
Page: 111
Chapter: 3
Section: 1
Variables: \(f:2^{<\omega}\to2^{<\omega}\)

Name: A universal function
Definition: A function \(F\) such that, for each partial computable function \(f:2^{<\omega}\to2^{<\omega}\), there exists \(\rho_f\) such that \(U(\rho_f\sigma)=f(\sigma)\) for each \(\sigma\in2^{<\omega}\)
Page: 111
Chapter: 3
Section: 1
Denoted by: \(U\)

Smaller0: \(C_U(x)\)
Greater0: \(C_f(x)+|\rho_f|\)
Page: 111
Chapter: 3
Section: 1
Variables: \(f:2^{<\omega}\to2^{<\omega}\)
\(U\) an universal partial computable function,
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Name: The Kolmogorov complexity of \(\sigma\)
Definition: \(C_U(\Sigma)\)
Page: 111
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(\sigma\in2^{<\omega}\)
Notation: \(C(\Sigma)\)
Name2: The plain Kolmogorov complexity of \(\sigma\)
Name3: The C-complexity of \(\sigma\)

Question: Why does \(U\) does not appear in the notation \(C(\Sigma)\) ?
Answer: Because it only change a constant of the value, hence is asymptotically not important
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Let \(\sigma\in2^{<\omega}\)

Question: \(C(\sigma)\) is bounded above by
Answer: \(|\sigma|+O(1)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Let \(\sigma\in2^{<\omega}\)
Kind: Prop

Question: \(C(\sigma\sigma)\) is bounded above by
Answer: \(|\sigma|+O(1)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Let \(\sigma\in2^{<\omega}\)
Kind: Prop

Question: \(C(h(\sigma))\) is bounded above by
Answer: \(|\sigma|+O(1)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Let \(\sigma\in2^{<\omega}\),
\(h:2^{\omega}\to2^{\omega}\) computable
Kind: Prop

Question: \(C(n)\) is bounded above by
Answer: \(|\log(n)|+O(1)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(n\in\mathbb N\)
Kind: Prop

Definition: \(C(0^n)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(n\in\mathbb N\)
Context: Kolmogorov complexity
Notation: \(C(n)\)
Kind: Prop
Definition2: \(C(\sigma)\) such \(\sigma\) is the binary encoding of \(n\)

Definition: \(C(\langle \sigma,\tau\rangle)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Let \(\sigma,\tau\)
Notation: \(C(\sigma,\tau)\)
Kind: Prop

Definition: \(|\tau|\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(\sigma\) a binary string
Notation: \(\sigma^*_C\)
Definition2: \(s_t\) the least integer such that \(U(\tau)[s_t]\downarrow=\sigma\)
Conjdef: A string \(\tau\) such that the following is lexicographically minimal
Definition3: \(\tau\)
Hide remaining def: yes

Smaller0: \(\sigma\mapsto C(\sigma,C(\sigma))\)
Greater0: \(\sigma\mapsto C(\sigma^*_C)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Index: 2
Kind: Prop
Smaller to greater: \(=\)
Prefix Greater: \(\pm O(1)+\)

Name: A \(C\)-random string
Definition: A string \(\sigma\) such that \(C(\sigma)\ge|\sigma|-d\), for some fixed constant \(d\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
Index: 2
Kind: Prop

Question: The number of \(\sigma\), of length \(n\), with \(C(\sigma)\ge n\) is
Answer: at least one
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(n\in\mathbb N\)
Kind: Prop

Question: The number of \(\sigma\), of length \(n\), with \(C(\sigma)\ge n-k\) is
Answer: greater than \(2^n(1-2^{-k})\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(k\le n\in\mathbb N\)
Kind: Prop

Name: An half-random string
Definition: A string \(\sigma\) such that \(C(\sigma)\ge\frac{|\sigma|}{2}\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,

Smaller0: \(\mu\) long enough
Greater0: at least one
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(k\in\mathbb N\),
\(\mu\) a string
Prefix Greater: the number of prefix \(\sigma\) of \(\mu\) such that \(C(\sigma)<|\sigma|-k\) is

Smaller0: \(C(\sigma\tau)\)
Greater0: \(C(\langle\sigma,\tau\rangle)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(\sigma,\tau\) strings
Index: 5
Kind: Prop
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Smaller0: \(C(\langle\sigma,\tau\rangle)\)
Greater0: \(C(\sigma)+C(\tau)+2\log C(\sigma)+O(1)\)
Page: 112
Chapter: 3
Section: 1
Variables: \(U\) an universal partial computable function,
\(\sigma,\tau\) strings
Index: 5
Kind: Prop
Smaller to greater: \(\le\)
Greater to smaller: \(\ge\)

Name: An immune set
Definition: A set of natural, without infinite c.e. subsets.
Page: 114
Chapter: 3
Section: 1
Example: The set of half-random strings.
Extra: doublon ?