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.
4
votes
1answer
58 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
24 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
34 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 ...
2
votes
3answers
50 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 ...
4
votes
1answer
112 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 ...
8
votes
1answer
109 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 ...
3
votes
2answers
66 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
114 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
224 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 ...
10
votes
1answer
127 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 ...
