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.
105
questions
1
vote
1answer
15 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 ...
0
votes
1answer
37 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 ...
0
votes
1answer
34 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 ...
0
votes
0answers
25 views
Calculate complexity of game of life(cellular automata) [duplicate]
I want to calculate the kolmogorov complexity of n evolution of a game of game of life(game of life is a kind of cellular automata). I’m not searching for the complexity of a certain pattern of cells ...
1
vote
0answers
27 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 ...
2
votes
0answers
36 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
1answer
29 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
2answers
48 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 ...
0
votes
0answers
23 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
1answer
78 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$ ...
2
votes
1answer
48 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 ...
0
votes
1answer
68 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 ...
0
votes
1answer
48 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{ - ...
1
vote
0answers
34 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 ...
4
votes
1answer
161 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,...
1
vote
1answer
62 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$, ...
3
votes
2answers
203 views
Kolmogorov Complexity of String Concatenation
For all bit strings $x$, $y$ and Kolmogorov complexity $K$, is $K(xy) > K(x)$?
3
votes
1answer
120 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 ...
4
votes
1answer
80 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 ...
2
votes
0answers
317 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
1answer
115 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
285 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 ...
3
votes
1answer
56 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
86 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
95 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
72 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 ...
3
votes
0answers
43 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 ...
2
votes
0answers
31 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
77 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 ...
1
vote
0answers
239 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
27 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 $...
6
votes
1answer
128 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
59 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
30 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
92 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 ...
1
vote
1answer
164 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∈Σ^∗$ (...
0
votes
1answer
58 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 ...
2
votes
1answer
193 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
...
3
votes
1answer
435 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
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 ...
5
votes
1answer
563 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
634 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 ...
6
votes
2answers
569 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
264 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
110 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
87 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
2answers
363 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
39 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
52 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 ...
0
votes
2answers
109 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?
...