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.
89
questions
2
votes
0answers
18 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 ...
1
vote
0answers
17 views
Kolmogorov complexity of $y$ given $x = yz$ with $K(x) \geq \ell(x) - O(1)$
I am trying to solve Exercise 2.2.2 from "An Introduction to Kolmogorov Complexity and Its Applications" (Li & Vitányi, vol. 3). The exercise is as follows (paraphrased):
Let $x$ satisfy $K(x) \...
1
vote
1answer
46 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$-...
1
vote
1answer
28 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 ...
0
votes
0answers
31 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 ...
3
votes
1answer
28 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 ...
0
votes
1answer
35 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 ...
2
votes
1answer
65 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,...
3
votes
0answers
45 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 ...
0
votes
0answers
18 views
How does neural net complexity relate to other complexity measures?
In neural networks, "weight regularization" is often used as a so called "complexity penalty" in order to make sure that the network generalizes better from training data.
Similarly, in "program ...
3
votes
0answers
32 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 ...
1
vote
0answers
16 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 ...
1
vote
1answer
43 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 ...
1
vote
0answers
179 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 ...
0
votes
0answers
19 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 $...
5
votes
1answer
74 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
1answer
38 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(\...
2
votes
0answers
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 ...
1
vote
1answer
53 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 \...
1
vote
1answer
108 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∈Σ^∗$ (...
-1
votes
1answer
36 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 $...
2
votes
1answer
157 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
...
2
votes
1answer
297 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
0answers
24 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 ...
5
votes
1answer
285 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
1answer
356 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 ...
3
votes
2answers
345 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 ...
1
vote
1answer
124 views
When is conditional Kolmogorov complexity zero?
It seems intuitive that conditional Kolmogorov complexity is only zero when the bitstrings are the same, and otherwise is greater than 0. I.e. if $b_1 = b_2$, then $K(b_1|b_2) = 0$, otherwise $K(b_1|...
2
votes
1answer
78 views
Unrolling closures into SAT boolean formula
I need to verify some assertions about the minimalist Turing-complete language Jot.
Many of the assertions I want to investigate are semi-deciable (co-recursively enumerable). So far it's been fairly ...
2
votes
0answers
79 views
If a bitstring is compressible, is the minimal Kolmogorov sufficient statistic most likely large or small?
If a bitstring is incompressible, then its minimal Kolmogorov sufficient statistic (MKSS) is zero, since the bitstring is best represented by a structure function that enumerates bitstrings, and thus ...
2
votes
1answer
198 views
Computing the Kolmogorov complexity of a string
What would be the implications for complexity theory if you could compute the Kolmogorov complexity of a string generated by a psuedorandom generator?
1
vote
0answers
32 views
What do you call a set which has the following enumeration-related machine?
A set $S$ of natural numbers is Recursively Enumerable if there exists a Turing machine which enumerates them, i.e. given no input, outputs the elements of $S$ in increasing order (never halting if $...
1
vote
1answer
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 ...
1
vote
1answer
65 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?
...
1
vote
1answer
87 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 ...
2
votes
1answer
105 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 ...
1
vote
0answers
106 views
Kolmogorov complexity of a random string conditioned on another random string
Given two strings $x$, $y$, both of length $n$, what is the probability that $K(x|y,n)=K(x|n)$ ? (Bounds on this probability would be very interesting too). Here $K$ is Kolmogorov complexity, $x$ and $...
1
vote
0answers
73 views
Conditional Kolmogorov compexity of string concatenation
In what follows $K(x|y)$ is conditional Kolmogorov complexity, $xx$ is $x$ concatenated with itself. It appears to me that $K(xx|yy)=K(xx)$ should be true for infinitely many strings $x$ and $y$. In ...
1
vote
1answer
26 views
Is $K(b|a) \geq 1$ if $a\neq b$?
Since $K(a|a) = 0$, is $K(b|a) \geq 1$ when $a\neq b$, as we need at least one bit to distinguish between $K(a|a)$ and $K(b|a)$? If not true in general, is it true if $a$ and $b$ are elegant programs?...
1
vote
0answers
42 views
Joint Kolmogorov complexity of elegant programs
If $a$ and $b$ are different elegant programs (minimal program for some output), is their joint Kolmogorov complexity the sum of their individual complexities, i.e. $K(a,b) = K(a) + K(b)$?
1
vote
1answer
34 views
For a turing machine which computes $y$ with argument $x$, how much does the descriptional length of a machine producing $y$ without input increases
Let $f$ be some function in some programming language (like C), and we need $n$ bits to store this function. Suppose we have some fixed value $v$ for the argument, then let
g() { f(v) }
be the ...
3
votes
1answer
46 views
Gate/transistor number and program length measures of computational complexity?
Are there scaling concepts regarding the number of components needed and minimum program length needed to solve a problem of some complexity?
For example, problems are characterized by O(.) measures ...
2
votes
1answer
89 views
Number of $1$'s in a Kolmogorov-random number
The problem I'm trying to tackle is to show that for a Kolmogorov-random number of length $n$, the amount of $1$'s in its binary representation is greater than $n/4$.
My only idea so far, is to use a ...
4
votes
1answer
229 views
Kolmogorov complexity of a sequence of prime numbers
Let's say $p_1, p_2, p_3, \ldots $ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n_0 \in \mathbb{N}$, so that for all $n \ge n_0$:
$$K(p_n) < \log_2(...
5
votes
1answer
227 views
What's relation between Kolmogorov complexity and pseudorandomness?
In a comment on this question, @Kaveh wondered whether the questioner really wanted to ask "is there a relation between strings with high Kolmogorov complexity and pseudorandomness?" This is not the ...
2
votes
1answer
82 views
An infinite subsequence of random numbers in Kolmogorov sense
Is it possible to construct an infinite increasing sequence of random naturals (in Kolmogorov sense) that is a subsequence of another sequence? Ok, in general I suppose not, e.g. for prime numbers. ...
1
vote
1answer
93 views
Is a bitstring easier to compress if it has lower Kolmogorov complexity?
I have two bitstrings that are 100 bits long. Bitstring A has a Kolmogorov complexity (KC) of 90 and bitstring B has a KC of 10. Intuitively, I think bitstring B is probably easier to compress than ...
2
votes
0answers
149 views
Relationship between algorithm size and compression power
Does the size of an algorithm restrict how many bitstrings it can compress, and how much it can compress the bitstrings?
Some definitions and an example to illustrate this is the case.
An elite ...
8
votes
2answers
1k views
Proof of non-regularity, based on the Kolmogorov complexity
In class our professor showed us 3 methods for proving non-regularity:
Myhill–Nerode theorem
Pumping Lemma for regular languages
Proof of non-regularity, based on the Kolmogorov complexity
Now the ...
6
votes
1answer
63 views
Generate string with large Kolmogrov complexity
Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact?
I think the answer is no except for small $c$, but I'm not sure.
