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

112 questions
Filter by
Sorted by
Tagged with
34 views

### On proving the uncomputability of Kolmogorov complexity by contradiction

I have seen a proof by contradiction for the uncomputability of Kolmogorov complexity. The idea the basically the same as in the proof for halting problem (i.e., there are cases that lead to Berry ...
58 views

### Time bounded Kolmogorov complexity and one way functions

I recently read the following article https://www.quantamagazine.org/researchers-identify-master-problem-underlying-all-cryptography-20220406/ which links to https://arxiv.org/abs/2009.11514 that ...
22 views

### Kolmogorov Complexity: Is there a Program P which outputs Kolmogorov string K, P doesn't contain K and P is longer than K?

Given a binary string, K, with length N, and Kolmogorov Complexity N, is there a program P, of length M, and with Kolmogorov Complexity M such that: P outputs K. M >= N. P does not contain K.
1 vote
55 views

### Chaitin’s version of Gödel’s theorem and pseudorandomness

Chaitin’s version of Gödel’s theorem roughly states that there exists a constant c such that for each string of one’s and zeroes x, the sentence “the algorithmic information complexity (Kolmogorov ...
16 views

### In Kolmogorov's $K(s) \leq |s| + c$, why is $c$ +ve?

Kolmogorov said "It seems natural to call a chain random if it cannot be written down in a more condensed form, i.e., if the shortest program for generating it is as long as the chain itself. &...
1k views

### Storing N bits on the smallest possible space in a real computer

Update. Since my original question was misunderstood by many, and lead to a lot of debate about various issues, let me try to pose this modified and rephrased question: Assume that I have a computer ...
1 vote
25 views

### Solomonoff induction generates sequences of unbounded Kolmogorov complexity?

I was reading this paper, and the author (in private correspondence, though I'm sure it's also in the paper) explains that a bit string generated through Solomonoff induction will have growing (and ...
1 vote
80 views

### is Kolmogorov complexity computable on a finite domain?

The proof in the wikipedia article for the uncomputability of Kolmogorov complexity uses the fact that there are strings of arbitrarily large Kolmogorov complexity. What if we restrict to a finite ...
1 vote
45 views

### Is there a known relationship between Kolmogorov Complexity of a binary string and the logic optimization of the corresponding Boolean function?

I haven't thought about how to go about proving it or finding a counterexample (I probably don't have the right background), but it seems intuitive to me that, given some representation of a Boolean ...
41 views

### Small Turing machine accepting single complicated input?

This imprecise question is about a simple example for the following problem. I would like a Turing machine with few states that accepts only inputs which look complicated to the naked eye. Of course ...
1 vote
118 views

### kolmogorov complexity for finite Language?

In lectures my professor proved that there is no Turing machine that for every x it calculates k(x). On the other hand, I saw a claim online that for finite language L there is a Turing machine that ...
1 vote
34 views

### What is the most random Markov martingale?

Consider a boxing match between players A and B. If A wins, then $1$ point is gained; otherwise $1$ point is lost. Assume that $A$ is as same good as B. Denote by $X_t$ the expected point of A at time ...
44 views

### Kolmogorov complexity of probability distributions, with and without time bound

Kolmogorov complexity of a string is the length of the shortest algorithm that generates it. Here I'm focusing instead on randomly distributed strings $x$, with length $n$, with a probability ...
1 vote
45 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, ...
1 vote
252 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 ...
1 vote
35 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 ... 1 vote
111 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$ ...
53 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 ...
200 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 ...
1 vote
79 views

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

1 vote
199 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∈Σ^∗$ (...
67 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 ...
217 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 ...
608 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 ...
1 vote
29 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 ...
658 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 ...
1 vote