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

93 questions
Filter by
Sorted by
Tagged with
55 views

### Why don't prefix-free Turing machines suffer from complexity dips?

It's claimed in several texts on algorithmic complexity that prefix-free Turing machines are better for understanding randomness, at least in infinite sequences. In Nies' Computability and Randomness,...
28 views

### Kolmogorov Complexity, struggle with equation

I am working on understanding Kolmogorov Complexity. I've been struggling with the following exercise for quite some time now and would appreciate any inputs. Show that there exists a constant $c$, ...
88 views

### Kolmogorov Complexity of ​String Concatenation

For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?
49 views

### How many “compressible” strings are there?

Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this. It is easy to see that almost all ...
42 views

### How connected are information theory and algorithmic information theory?

In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth). As far as I understand, algorithmic information ...
32 views

### How to measure the length of the program on Turing Machine?

In Kolmogorov complexity, there is a notion: length of the shortest program that describes the data. I can use Lempel-Ziv compression to estimate this value. What if I want to estimate this value by ...
86 views

### On teaching Kolmogorov complexity with Python and the complexity of composed strings

The setting of this question is a bit long-winded, but please bear with me. This fall I will be lecturing a course on mathematical information theory, and on a few lectures we will be discussing ...
66 views

### How can I prove the languages of incompressible words is undecidable?

I have hard time understanding the proof by contradiction for the claim "$L=\{x : K(x) \ge |x| \}$" is undecidable ". The proof is as follows : M' = " On input $n$ Enumerate over all $n$-...
42 views

### Examples of exact computation of Kolmogorov complexity?

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed ...
36 views

### Are real computers capable of producing true random series with a program of finite length?

Suppose that one has a Blum–Shub–Smale machine. Is it possible to write down a program of finite length that produces a series of numbers, with each consisting of a finite number of digits, such that ...
31 views

### Range of values for Kolmogorov complexity

Let $n$ be a positive integer. Is it true that for all $1\leq i \leq n$ there exists a length $n$ binary string $w$ such that $K(w) = i$. Where $K(w)$ is the Kolmogorov complexity of $w$. For each ...
44 views

### Kolmogorov randomness for Pseudo random number generator

I am working on pseudo random number generation for one of my projects. My goal is to prove that the output is almost Kolmogorov Random since Kolmogorov complexity is uncomputable. So would appreciate ...
77 views

### What doest it mean: “computer is an intelligence amplifier”?

There is one example in Kolmogorov complexity books and related articles: Consider we have a monkey at a typewriter and a monkey at a computer keyboard. If the monkey types at random on a typewriter,...
47 views

### Computability of Kolmogorov complexity in total languages

It is well known that the Kolmogorov complexity is uncomputable in Turing-complete programming languages. However, what about total programming languages? For example, is the Kolmogorov complexity of ...
33 views

### How do you resolve this paradox with the invariance theorem?

The invariance theorem of kolmogorov complexity states that for two different languages with complexity functions $K_1$ and $K_2$, we have $$\exists c.\forall s. K_1(s) \le K_2(s) + c$$ Here is an ...
19 views

### Is there a hierarchy theory for time-bounded Kolmogorov complexity?

We know that there are languages in $DTIME(n^t)$ and not in $DTIME(n^s)$ for all $t>s$ due to simple diagonal arguments (i.e., the Time Hierarchy Theorem), but I'm wondering if there is any ...
45 views

### How can Kolmogorov complexity help me practically with measuring entropy?

A comment was made to me saying the following in relation to Kolmogorov complexity:- You're not the first to think non-computability = impractical or even useless. But it can be useful. In ...
208 views

### VC Dimension of A Set of Hypothesis

I am confused about what does a VC dimension of a set of hypothesis means. I have two hypothesis, say $H_1$ with VC dimension of $x$, and $H_2$ of VC dimension of $y$. Does this automatically mean ...
22 views

27 views

### Is there a universal metric of “size of a program”?

There is a universal metric of information: amount of bits. It's universal in the sense that if we write a piece of information in DNA (4-ary digits), we can simply multiply by 2-log-4 to get the ...
58 views

167 views

### Kolmogorov Complexity proving there exists a constant for when if two strings are equal length

When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be ...
321 views

### Proof: Kolmogorov complexity of string concatenation

Does there exist a universal constant $c$ such that for any strings $x, y$, we have: $$K(xy)\leq K(x) + K(y) + c$$ where $K(\cdot)$ denotes the Kolmogorov Complexity of a binary string and $xy$ means ...
25 views

### United space-time complexity of finite strings

Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example ...
324 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 ...
388 views

### How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem

I try to solve the following exercise: We know that K (x), the complexity of Kolmogorov, is incomputable. Show how calculate it, if we have an oracle for the membership problem (or for the HALT ...
399 views

### What Good Is Kolmogorov Complexity Since It Is Relative?

Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a ...
145 views

43 views

### What is The correct terminology for expressing *this* notion of complexity

Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set ...
77 views

### Is Kolmogorov Complexity Universal?

Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information? ...
90 views

### Prefix complexity of x conditioned on prefix complexity of x

I wonder what is $K(x|K(x))$, $K$ denoting (Kolmogorov-Chaitin) prefix complexity. Naively, it looks like it should just be $K(x)+O(1)$. Is that right? The same question for plain Kolmogorov ...
137 views

### Is Kolmogorov-random nonsensical for small numbers?

The Wikipedia definition of Kolmogorov-random defines a string (usually of bits) as being random if and only if it is shorter than any computer program that can produce that string. Aren't nearly1 ...
111 views