# 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.

95 questions
Filter by
Sorted by
Tagged with
4k views

### What are very short programs with unknown halting status?

This 579-bit program in the Binary Lambda Calculus has unknown halting status: ...
1k 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 (...
380 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 ...
440 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 self-contained ...
562 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 larger ...
89 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 ...
1k views

### Proof of non-regularity, based on the Kolmogorov complexity

In class our professor showed us 3 methods for proving non-regularity: Myhill–Nerode theorem Pumping Lemma for regular languages Proof of non-regularity, based on the Kolmogorov complexity Now the ...
427 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 ...
183 views

### Average case algorithm analysis using Kolmogorov Incompressibility Method

The Incompressibility Method is said to simplify the analysis of algorithms for the average case. From what I understand, this is because there is no need to compute all of the possible combinations ...
405 views

### What problem cannot be solved by a short program?

BACKGROUND: Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of ...
575 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 ...
71 views

### Generate string with large Kolmogrov complexity

Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact? I think the answer is no except for small $c$, but I'm not sure.
403 views

### What is static complexity?

Definition : Kolmogorov complexity is a static complexity measure that captures the difficulty of describing a string. For example, the string consisting of three million zeroes can be described with ...
184 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 ...
472 views

### Are nearly all natural numbers compressible?

A simple counting argument shows most strings can't be compressed to shorter strings. But, compression is usually defined using Kolmogorov complexity. A string is compressible if its Kolmogorov ...
83 views

### Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is co-recursively ...
327 views

### What's relation between Kolmogorov complexity and pseudorandomness?

In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the ...
99 views

### Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference

My motivations for asking this question are philosophical in nature. I'm by no means a computer scientist though, and I feel as though this question should be answered by someone who is since it's one ...