Kolmogorov complexity concerns the size of the shortest program that generates a given string.
Questions tagged [kolmogorov-complexity]
111 questions
2
votes
1 answer
Kolmogorov complexity for infinite strings
I'm struggling with a problem that I believe I've managed to reduce to a question of Kolmogorov complexity for infinite strings, but since I'm not an expert in this field, I'm not sure about the correctness of the reasoning.
Let us consider an…
Charles
- 525
1
vote
1 answer
Respective complexities of a string and its substring
If $s$ is a substring so that $s \subset S$, can Kolmogorov complexity of the whole string $S$ be lower than that of the given substring, $K(S) < K(s)$?
Arets Paeglis
- 113
1
vote
1 answer
Kolmogorov complexity of sequence and its fragment
Is it possible that part of sequence is more complex than all sequence because the best way to encode it is to use the complete sequence and starting and ending positions of the fragment.
Maybe, for example, string of hexadecimal digits of $\pi$. Or…
zaa
- 708
0
votes
1 answer
Is the Kolmogorov Complexity of 11…1 with even length L less than for the string 1010…10 of the same length?
We define the Kolmogorov Complexity to be independent of any
particular programming language for bit string x as the length of the shortest
string where TM M on input w halts with x on its tape
and is some specified fixed encoding of the…
0
votes
1 answer
Kolmogorov complexity when no language is specified
The statement of theorem 3 in "A frequentist understanding of sets of measures" by Fierens, Rêgo, and Fine (pdf available here) requires that the Kolmogorov complexity of a certain function be less than a certain constant. The function selects…
Mars
- 1,338
0
votes
1 answer
Computability for equality in Kolmogorov complexity?
It is a known result that Kolmogorov complexity is not computable for every arbitrary sequence. I wonder whether the following problem is computable or not:
"Given $x$ and $y$ as two sequences, whether $K(x)\overset{+}{=}K(y)$, where…
Cupitor
- 1,281
0
votes
1 answer
Is the Kolmogorov complexity of a number always its logarithm?
if I have a natural number $a(n,m)$ that depends on some $n$ and $m$, where $m$ is fixed,
isn't then the Kolmogorov complexity of it simply its logarithm?
Rhjg
- 2,029
0
votes
2 answers
Proof of an inequality about Kolmogorov complexity of two words.
It is needed to prove an existing of such constant C that for any words $x$,$y$
$K(x,y) \le K(x) + K(y) + log(|x|+|y|) + C$
(K is Kolmogorov complexity)
I tried to prove it by using next true inequalities:
$K(x|l(x)) \le l(x) + c$
and
$K(x) \le…
Teddy
- 25