Questions tagged [kolmogorov-complexity]

Kolmogorov complexity concerns the size of the shortest program that generates a given string.

Filter by
Sorted by
Tagged with
0
votes
1answer
34 views

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, ...
1
vote
1answer
89 views

Proof of a classical Theorem of Martin-Löf on complexity dips for Kolmogorov complexity,

I have a question on the first Theorem from the article Complexity of Oscillations in Infinite Binary Sequences by P. Martin-Löf, which could be downloaded from the publisher or from here. Theorem ...
2
votes
1answer
458 views

A question on Kolmogorov Complexity

Is it true that for all strings of a given length at least one has its Kolmogorov complexity equal to its length ? Is there a proof if the answer is in affirmative? (For any alphabet with more than ...
0
votes
1answer
123 views

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?
1
vote
1answer
48 views

Why $C(n\mid l(n)) \ge C(n) - C(l(n))$ for Kolmogorov complexity

Denote by $C(n)$ the plain Kolmogorov complexity of $n$ and the length of a binary encoding of $n$ by $l(n)$, why do we have $$ C(n\mid l(n)) \ge C(n) - C(l(n))? $$ If I have a shortest program $p$ ...
2
votes
0answers
23 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all $...
3
votes
0answers
52 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the string. ...
1
vote
0answers
62 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
0
votes
1answer
96 views

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 ...
1
vote
0answers
53 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
4
votes
0answers
82 views

Is there any research on Diophantine Approximation with computable numbers

I was wondering if there is any research in the field of Diophantine Approximation using the computable numbers. It seems to be a good fit, a dense countable set with a variety of different potential ...
0
votes
0answers
34 views

How to prove equality $K(x, K(x)) = K(x) + O(1) $?

It is needed to prove that $K(x, K(x))=K(x) + O(1)$ where $K$ means Kolmogorov complexity. I think the equality is true because when we find Kolmogorov complexity of $x$ we already knows $K(x)$ and ...
9
votes
2answers
6k views

Question about the definition of “Prefix free”

I am trying to understand the definition of "Prefix free", but I do not understand the definition nor the example that wikipedia provides. I was hoping for clarification. Below is an excerpt from ...
2
votes
0answers
45 views

Kolmogorov complexity inequality

Prove, that KP (x) ≤ KS (x) + log KS(x) + 2 log log KS (x) + O(1). Please tell me in which direction to think.
1
vote
0answers
38 views

Optimal Kolmogorov complexity

Let computable function U is the best way to describe to Kolmogorov complexity. Prove that the mapping V, determined crucial for any word p as V (p) = U (U (p)), is also optimal way to describe the. ...
1
vote
0answers
94 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
2
votes
0answers
113 views

Does a random binary sequence almost always have a finite number of prime prefixes?

Does a random binary sequence almost always have a finite number of prime prefixes? Specifically, let $x = \sum_{1 \le i}{2^{-i} \cdot x_i}$ with $x_i \in \{0,1\}$ be a random real in $[0,1)$, $X_i = ...
8
votes
1answer
1k views

Relationship between compression, shannon entropy and kolmogorov complexity

I have read that the Shannon Entropy is used as a bound for the compressibility of a message, for example here 1 it says "In other words, the best possible lossless compression rate is the entropy ...
0
votes
1answer
162 views

Kolmogorov complexity of an algorithm?

I've read that Kolmogorov comlexity is about calculating the least number of bits needed to describe a string or other mathematical objects. Does 'other mathematical objects' include algorithms too? ...
6
votes
1answer
249 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
2
votes
1answer
314 views

Prove that these Sets Containing Infinitely Many Incompressible Strings Exist

We define a set $A$ to be special if: $$\liminf_{n \to \infty} \frac{|A^{\leq n}|}{n} = 0$$ I want to prove that there are special recursive sets that contain infinitely many incompressible strings. ...
1
vote
0answers
137 views

Solomonoff induction , Shannon Entropy, Kolmogorov Complexity.

If Expected Kolmogorov Complexity equals Shannon Entropy why can't Shannon Entropy be used as an approximation of Kolmogorov Complexity in Solomonoff Induction? Regarding Kolmogorov Complexity and ...
3
votes
1answer
81 views

How much information is in the question “How much information is in this question?”?

I'm actually not sure where to pose this question, but we do have an Information Theory tag so this must be the place. The "simple" question is in the title: how do I know how many bits of information ...
1
vote
1answer
425 views

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 ...
1
vote
1answer
72 views

Kolmogorov (Kolmogoroff- ) Complexity of infinite sequences, Request for Proof

Let $\xi \in X^{\omega}$ be an infinite sequence and denote by $\xi[1\ldots n]$ its length $n$ initial segment. Then (due to Martin-Löf) the following holds: For every $\xi \in X^{\omega}$ there ...
0
votes
1answer
116 views

Kolmogorov (Kolmogoroff-) Complexity, Contradiction with Invariance Theorem.

Fix some programming languages $S$ which is rich enough such that one can write interpreters for $S$ in $S$. Define $$ K(w) := \mbox{length of a shortest program producing $w$}. $$ Now fix some ...
4
votes
3answers
810 views

Is it possible to create a string with known Kolmogorov Complexity?

I wish to compare compressors using strings with known Kolmogorov Complexity, but I haven't got the theoretical background and tools to understand how to do that. I'm just starting in this area and ...
1
vote
0answers
69 views

Kolmogorov complexity proof of Lovasz local lemma

Roughly speaking, Kolmogorv Complexity proof of lovasz local lemma states that for any $k$-CNF $S$ on $n$ variables and $m$ clauses, where the dependency of every clause is bounded by $2^{k-c}$, for ...
3
votes
1answer
188 views

Definability of Kolmogorov Complexity?

This paper claims to have a proof of Godel's Second Incompleteness Theorem using Kolmogorov Complexity: http://www.ams.org/notices/201011/rtx101101454p.pdf As far as I can tell, it seems to assume ...
0
votes
2answers
149 views

Regularity of balanced binary strings

How can one tell which number of propositional variables is necessary to express a Boolean function given as a sequence of 0s and 1s (a binary string) of length $2^n$ as a Boolean formula? The ...
10
votes
3answers
291 views

Measure of how much information is lost in an implication

In an implication like $p \implies q$, is there some measure of how much information is lost in the implication? For example, consider the following implications, where $x \in \{0,1,\ldots,9\}$: \...
1
vote
1answer
66 views

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)$?
1
vote
1answer
83 views

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 ...
1
vote
0answers
37 views

Is it really true that $K(x|y) = K(x,y) - K(y)$?

Denote by $y^*$ the shortest program computing the string $y$. In the main textbook and various papers of Li & Vitanyi, I have seen the following statements. The first is well established: the ...
2
votes
2answers
241 views

Solovay Randomness

Say that an $x\in 2^{\omega}$ is Solovay random if for all computably enumerable collections of intervals $\{I_n\}$ such that $\sum_n\mu(I_n)<\infty$, then $x\in I_n$ for at most finitely many $n$. ...
3
votes
0answers
357 views

The minimal number of states required to run Goldbach's Conjecture

It is well known that being able to compute Busy Beaver numbers would allow one to solve (in theory) such open problems as Goldbach's conjecture. Simply run a Turing machine with $n$ states to check ...
5
votes
1answer
4k views

Proof that the set of incompressible strings is undecidable

I would like to see a proof or a sketch of a proof that the set of incompressible strings is undecidable. Definition: Let x be a string, we say that x is c-compressible if K(x) $\leq$ |x|-c. If x is ...
4
votes
2answers
159 views

How to assess the complexity of a string

Q How do I quantify complexity of a given string? Consider a sample: ...
8
votes
1answer
512 views

Is there an infinite set of strings whose Kolmogorov complexities are computable?

Is there an infinite set of strings whose Kolmogorov complexities are computable?

1
2