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.

Filter by
Sorted by
Tagged with
0 votes
1 answer
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 ...
Sam's user avatar
  • 163
0 votes
1 answer
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 ...
Craig Feinstein's user avatar
0 votes
0 answers
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.
Jim's user avatar
  • 101
1 vote
1 answer
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 ...
Craig Feinstein's user avatar
0 votes
1 answer
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. &...
Paul Uszak's user avatar
  • 1,602
2 votes
3 answers
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 ...
domotorp's user avatar
  • 260
1 vote
0 answers
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 ...
A_P's user avatar
  • 111
1 vote
1 answer
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 ...
ludog's user avatar
  • 90
1 vote
1 answer
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 ...
user023049's user avatar
0 votes
1 answer
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 ...
domotorp's user avatar
  • 260
1 vote
1 answer
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 ...
Dan's user avatar
  • 61
1 vote
0 answers
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 ...
Philo18's user avatar
  • 119
2 votes
0 answers
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 ...
Doriano Brogioli's user avatar
1 vote
1 answer
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, ...
user56834's user avatar
  • 3,632
1 vote
2 answers
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 ...
Anguepa's user avatar
  • 113
1 vote
0 answers
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 ...
user avatar
1 vote
1 answer
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$ ...
Priyanka's user avatar
2 votes
1 answer
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 ...
Devi's user avatar
  • 21
0 votes
1 answer
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 ...
Oleg Dats's user avatar
  • 299
1 vote
1 answer
79 views

Computability of Kolmogorov Complexity of Turing-Incomplete language

I am trying to determine whether Kolmogorov complexity is computable for a specific language. I am certain this given language is not Turing-Complete. The language is defined as follows: $A;B \text{ - ...
Vladis Becker's user avatar
1 vote
0 answers
44 views

Kolmogorov complexity of a product of two numbers

In his book "Theoretical Computer Science", Juraj Hromkovic informally defines the Kolmogorov complexity $K(x)$ of a word $x$ consisting of zeros and ones as the binary length of the shortest Pascal ...
Frunobulax's user avatar
4 votes
1 answer
224 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,...
Mars's user avatar
  • 696
1 vote
1 answer
72 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$, ...
Terrenay's user avatar
3 votes
2 answers
290 views

Kolmogorov Complexity of ​String Concatenation

For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?
Arthur Lubocce's user avatar
4 votes
1 answer
242 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 ...
Mike Battaglia's user avatar
4 votes
1 answer
114 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 ...
user56834's user avatar
  • 3,632
2 votes
0 answers
378 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 ...
Rami Luisto's user avatar
1 vote
1 answer
225 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$-...
Prithi's user avatar
  • 71
1 vote
1 answer
427 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 ...
Robert_Lewis's user avatar
3 votes
1 answer
70 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 ...
JtailHyper's user avatar
0 votes
1 answer
128 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 ...
Varun Negandhi's user avatar
2 votes
1 answer
108 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,...
Oleg Dats's user avatar
  • 299
3 votes
0 answers
86 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 ...
xuq01's user avatar
  • 1,190
3 votes
0 answers
50 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 ...
PyRulez's user avatar
  • 778
2 votes
0 answers
42 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 ...
Ari's user avatar
  • 1,611
1 vote
1 answer
105 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 particular ...
Paul Uszak's user avatar
  • 1,602
1 vote
0 answers
279 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 ...
Gavin Gale's user avatar
0 votes
0 answers
32 views

Perturbative Kolmogorov Complexity Bounds

Are there any known bounds on the impact of changing (for example) one bit in a string on the resulting string's Kolmogorov Complexity? In mathematical terms, does the equation $|K(x) - K(x')|$ (with $...
nick.schachter's user avatar
6 votes
1 answer
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 ...
Joe Lee-Doktor's user avatar
1 vote
1 answer
72 views

Kolmogorov complexity of a sequence of n bits with k ones

Let Program P be :"Generate, in lexicographic order, all sequences with k ones and n bit length; Of these sequences, print the ith sequence." Apparently the length of this program is $\log(n) + \log(\...
C..O..S's user avatar
  • 25
2 votes
0 answers
34 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 ...
user56834's user avatar
  • 3,632
1 vote
1 answer
107 views

Prove that A is non-regular using K-Complexity Non regularity theorem

Given $Y^A_{x,n}$= the nth string $y∈Σ^∗$ (in lex order) such that $xy∈A$ (if n such y exits). So what completes $x$ if adding $n$ such $y$'s brings us to an element in the set $A$ Given $A \subseteq ...
ZeroDay Fracture's user avatar
1 vote
1 answer
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∈Σ^∗$ (...
ZeroDay Fracture's user avatar
0 votes
1 answer
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 ...
ZeroDay Fracture's user avatar
2 votes
1 answer
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 ...
ZeroDay Fracture's user avatar
3 votes
1 answer
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 ...
Han Zhao's user avatar
1 vote
0 answers
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 ...
DSblizzard's user avatar
5 votes
1 answer
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 ...
Complexity's user avatar
  • 1,157
1 vote
1 answer
785 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 ...
afdez's user avatar
  • 13
6 votes
3 answers
708 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 ...
Ned Ruggeri's user avatar