A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [kolmogorov-complexity]

The Kolmogorov complexity of a string s is equal to the length of the shortest program computing s and halting. Measures the lack of structure in a string.

Filter by
Sorted by
Tagged with
9
votes
2answers
596 views

Expected values of Kolmogorov complexity in a random sample

Kolmogorov complexity of a string is not computable. However, in a random subset of size $M$ of binary strings of length $n$, how many are expected to have complexity less than some integer $n_{0}$ ...
9
votes
1answer
338 views

Is Kolmogorov complexity a surjective function?

Let us fix an encoding of Turing-machines and a universal Turing-machine, U, that on input (T,x) outputs whatever T outputs on input x (possibly both running forever). Define the Kolmogorov complexity ...
28
votes
5answers
2k views

Efficiently computable variants of Kolmogorov complexity

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features: It corresponds to an intuition of giving strings with patters or ...
28
votes
2answers
1k views

Can we not output the Kolmogorov complexity?

Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on ...
17
votes
1answer
681 views

Does the uncomputability of Kolmogorov complexity follow from Lawvere's Fixed Point Theorem?

Many theorems and "paradoxes" - Cantor's diagonalization, undecidability of hatling, undeciability of Kolmogorov complexity, Gödel Incompleteness, Chaitin Incompleteness, Russell's paradox, etc. -...
14
votes
1answer
442 views

Comparing the Kolmogorov complexity of theories

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(s) > L$ where $K(s)$ is the Kolmogorov complexity of string $s$ and $L$ is a sufficiently large ...
16
votes
3answers
764 views

Do there exist x such that K(xx)<K(x), where K is Kolmogorov complextity.

Let $K(x)$ denote the Kolmogorov complexity of a string $x$. Do there exist a string such that $K(xx)<K(x)$. (Here $xx$ is the concatenation of $x$ with itself). A similar but different question ...
9
votes
2answers
2k views

Proof for Kolmogorov complexity is uncomputable using reductions

I am looking for a proof that Kolmogorov complexity is uncomputable using a reduction from another uncomputable problem. The common proof is a formalization of Berry's paradox rather than a reduction, ...
8
votes
3answers
922 views

Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
12
votes
2answers
408 views

Kolmogorov complexity with weak description languages

We can think of Kolmogorov complexity of a string $x$ as the length of the shortest program $P$ and input $y$ such that $x = P(y)$. Usually these programs are drawn from some Turing-complete set (like ...
7
votes
1answer
358 views

Difference between time-bounded and memory-bounded Kolmogorov complexity

Let $x$ be a finite string of length $n$. Denote by $C^t(x)$ the Kolmogorov complexity of $x$ bounded by time $t$ (i.e. the length of a minimal program that outputs $x$ and running at most $t$ steps)....
6
votes
1answer
236 views

Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$. A bitstring $B$ is generated by drawing 0s and 1s ...
3
votes
1answer
248 views

Kolmogorov complexity of D and D+d

I'm looking into using of the shelf compression algorithm to approximate the Kolmogorov complexity of a document corpus D and the complexity of D+d, where d is an extra document. I've got a strange ...