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.

101 questions
Filter by
Sorted by
Tagged with
28 views

Can a Kolmogorov complexity oracle solve halting problem?

I can find https://www.nearly42.org/cstheory/halting_to_kolmogorov/ but the halting problem part is unrelated to proof that kolmogorov can't be solved(still that assume it solvable and output a longer ...
25 views

Algorithmic information theory with stochastic algorithms?

Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, ...
54 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$ ...
38 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 ...
41 views

Turing machine that checks whether a given string is an output of a given machine and input

Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$? My ...
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 ...
33 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. ...
51 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 ...
36 views

53 views

158 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∈Σ^∗$ (...
53 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 ...
184 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 ...
628 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 ...
389 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 ...
26 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 ...
489 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 ...
534 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 ...
512 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 ...
91 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 ...
216 views

51 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 ...
518 views

What is an example of complex random string, in the Kolmogorov-Chatin sense?

Any string generated from a PRNG clearly has a very short description. You need the code for the random number generator, the seed, and then the number of times to iterate. So, it seems that all ...