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

99 questions
Filter by
Sorted by
Tagged with
22 views

### How many strings of length |w| are unrelated?

For sufficiently large |w|, how many of the 2^|w| strings of length |w| are entirely unrelated? A way to define this: two strings are unrelated if their joint Kolomogorov complexity is practically ...
30 views

### Kolmogorov-Complexity of strings in decidable languages

I just recently learned about Kolmogorov-Complexity and had an idea for giving an upper bound for strings in a decidable language. Is the following statement true? Say we have a recursive language. ...
40 views

### A property of Kolmogorov random strings

I am working on the following problem: Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\{0,1\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ ...
31 views

### Expressivity of neural networks, how much information can be stored

I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps ...
44 views

### How to define enumeration of the set of finite state machines?

I want to write a function that takes N (maximum number of states) as a parameter, enumerates all possible finite state machines up to N states, and returns random FSM with a probability in proportion ...
33 views

103 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 ...
50 views

147 views

### Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)

When proving a language is non regular we can use Kolmogorov complexity. As far I know to do this we just have to use this satisfy the following conditions Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (...
49 views

### Kolmogorov complexity of prefixes of computable sequences

Let the characteristic sequence of a set $A ⊆ \mathbb{Z^+}$ be the following infinite binary sequence: $$χ_A = b_1b_2b_3\ldots,$$ whose $n$th bit is 1 if $n ∈ A$ And 0 otherwise. Write $χ_{A,n}$ for ...
180 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 ...
368 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 ...
452 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 ...
508 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 ...
479 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 ...
201 views

50 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 ...
102 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 ...