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.

learn more… | top users | synonyms

2
votes
3answers
121 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
1
vote
1answer
54 views

Is the length of the shortest quine in a programming language computable?

The length of the shortest program in a given (fixed) programming language that produces a given output is that output's Kolmogorov complexity, which is not a computable function on the set of ...
3
votes
1answer
102 views

What determines the entropy of a program's source code?

a few days ago I asked a question about the limits of compression: Can PRNGs be used to magically compress-stuff? The idea common to all the answers was that if you consider all programs of length ...
4
votes
2answers
89 views

What is an estimation of the Kolmogorov Complexity for the first N integers?

I'm aware some ints have higher or lower Kolmogorov Complexities. For example, the number 5.41126806512 has a very low complexity as it can be expressed by ...
10
votes
2answers
380 views

Kolmogorov Complexity: Why would you need more bytes than the string itself?

I was reading Wikipedia's entry on Kolmogorov Complexity (thanks to this question), which states: It can be shown that the Kolmogorov complexity of any string cannot be more than a few bytes ...
4
votes
0answers
96 views

Proving a string is random

I am reading Kolmogorov Complexity by Li and Vitányi: "Let $x$ be a finite binary string. We write '$x$ is random' if the shortest binary description of $x$ with respect to the optimal specification ...
4
votes
1answer
95 views

Computability of Kolmogorov Complexity

Fix a universal Turing machine $M$. Let $A^*=\{0,1\}^n$ be the set of all binary string of length $n$. Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$. Just for a matter of ...
1
vote
1answer
79 views

The choice of programming language and the length of a program

I wonder how it's possible that: it can be shown that all reasonable choices of programming languages lead to quantification of the amount of absolute information in individual objects that is ...
6
votes
0answers
52 views

Interval density of time bounded Kolmogorov complexity

The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
3
votes
3answers
100 views

What is an example of complex random string, in the Kolmogorov-Chatin sense?

Any string generated from a PRNG clearly has a very short description. You need the code for the random number generator, the seed, and then the number of times to iterate. So, it seems that all ...
5
votes
1answer
174 views

Kolmogorov complexity of string concatenation

If $K(s)$ is the Kolmogorov complexity of the string $s \in \{0,1\}^*$, Can we prove (or disprove) the following statement: "Every string $s$ is a prefix of an incompressible string; i.e. for every ...
13
votes
2answers
244 views

Approximating the Kolmogorov complexity

I've studied something about the Kolmogorov Complexity, read some articles and books from Vitanyi and Li and used the concept of Normalized Compression Distance to verify the stilometry of authors ...
4
votes
2answers
79 views

Kolmogorov complexity of a decision problem

What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine ...
3
votes
1answer
150 views

When does the function mapping a string to its prefix-free Kolmogorov complexity halt?

In Algorithmic Randomness and Complexity from Downey and Hirschfeldt, it is stated on page 129 that $\qquad \displaystyle \sum_{K(\sigma)\downarrow} 2^{-K(\sigma)} \leq 1$, where ...
12
votes
3answers
304 views

Difference between “information” and “useful information” in algorithmic information theory

According to Wikipedia: Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible ...
11
votes
1answer
160 views

Equivalence of Kolmogorov-Complexity definitions

There are many ways to define the Kolmogorov-Complexity, and usually, all these definitions they are equivalent up to an additive constant. That is if $K_1$ and $K_2$ are kolmogorov complexity ...