9
votes
Accepted
Proof of non-regularity, based on the Kolmogorov complexity
To my knowledge, this is not one of the "classical" approaches used to characterize regular languages.
This approach is discussed in "A New Approach to Formal Language Theory by
Kolmogorov Complexity"...
- 13.6k
8
votes
Without fancy math, how does the MC-AIXI algorithm work?
I'll assume that the paper you're referring to is Veness et al. (2011) - A Monte-Carlo AIXI Approximation. The paper (and the AIXI model more generally) is rather technical, and so it is difficult to ...
- 81
8
votes
Storing N bits on the smallest possible space in a real computer
Represent the string $x$ using the following encoding:
$$0, x_k, \dots, 0, x_2, 0, x_1, 1, x_0$$
where $x_0 = x$, $x_{i+1} = \text{len}(x_i)$ is a binary representation of the length of $x_i$ in bits (...
D.W.♦
- 166k
7
votes
Accepted
What are very short programs with unknown halting status?
Overview of Turing Machine decidability starting on the a blank tape (Busy Beaver style)
For the blank tape input only:
4-state machines: all decided in 1983
5-state machines: in 2024 a Coq proof ...
7
votes
Kolmogorov Complexity of String Concatenation
Let $w = 0^{2^n}$, so that $K(w) = O(\log n)$. The string $w$ has $2^n+1$ prefixes, and so some prefix $x$ satisfies $K(x) \geq n$. This example strongly violates your inequality.
On the other hand, ...
- 279k
6
votes
Accepted
What's relation between Kolmogorov complexity and pseudorandomness?
The standard notion of pseudorandomness is about a process. You can say that the process (the pseudorandom generator) is pseudorandom, or not. The notion of pseudorandomness of a single string is ...
D.W.♦
- 166k
6
votes
Accepted
How many "compressible" strings are there?
A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$.
Conversely, considering the program $\Pi$ that gets an integer $r$ and a string ...
- 279k
4
votes
What Good Is Kolmogorov Complexity Since It Is Relative?
The relativity is up to an additive constant. Suppose that you express Kolmogorov complexity relative to your favourite universal Turing machine $U$, but I do it relative to my favourite UTM ...
- 82.2k
4
votes
Is Kolmogorov Complexity Universal?
The formal version of your statement is known as the invariance theorem, which states (informally) that any two definitions of Kolmogorov complexity differ by at most a constant. This issue is covered ...
- 279k
4
votes
Proof of non-regularity, based on the Kolmogorov complexity
Another very easy example is the following: use Kolmogorov complexity to prove that $L_{ww} = \{ww \mid w \in \{0,1\}^* \}$ is not regular.
I give you a very informal proof hoping that it can help ...
- 12.7k
4
votes
Accepted
What is static complexity?
Complexities in this context could be divided into dynamic and static:
Dynamic complexity is an attribute of the execution of a program with the string as an input. For example, the time or space ...
- 632
4
votes
Accepted
Why don't prefix-free Turing machines suffer from complexity dips?
Answering the titular question, the proof of the proposition breaks down for prefix-free encodings, since $\sigma$ doesn't necessarily belong to the prefix-free code.
There are other ways of seeing ...
- 279k
4
votes
Turing machine that checks whether a given string is an output of a given machine and input
No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.
- 1,536
4
votes
Storing N bits on the smallest possible space in a real computer
You can achieve N+2log2N with a simple algorithm:
Write down the binary string.
Prefix it with its length.
Prefix that with as many zeros as the length is long.
With this encoding, a 20 bit string ...
- 852
3
votes
Solomonoff's theory of induction, Kolmogorov complexity and Bayesian Inference
Mathematics and computer science doesn't have anything to say about whether simpler hypotheses are more likely. That's a question about reality, not about math / computer science.
What computer ...
D.W.♦
- 166k
3
votes
Prefix complexity of x conditioned on prefix complexity of x
For plain complexity the assertion is true. One direction is clear: $K(x|K(x))\leq K(x)$ (easier to describe x from something than from nothing). In the other direction one can argue by contraposition....
- 101
3
votes
What is an example of complex random string, in the Kolmogorov-Chatin sense?
New research since this question was asked may actually provide an answer, if I read it correctly.
One of the most complex* 12 bit strings in the Kolmogorov sense is 001111000011, relative to all 5 ...
- 161
3
votes
Gate/transistor number and program length measures of computational complexity?
Two well-known books in this research area are:
Jeffrey D. Ullman, Computational Aspects of VLSI, Computer Science Press, 1984
and
F. Tom Leighton, Introduction to Parallel Algorithms and ...
- 17.8k
3
votes
Accepted
Number of $1$'s in a Kolmogorov-random number
I've found an answer which uses certain facts I was not aware of, but it's nevertheless really good.
Our machine $M$ takes the length of a number, $n$, and an index $j$ as an input (we encode the ...
- 337
3
votes
Accepted
Kolmogorov complexity of a sequence of prime numbers
Since we can generate $p_n$ given $n$, $K(p_n) \leq K(n) + O(1) \leq \log_2 n + O(1)$. The prime number theorem implies that $p_n = \Theta(n\ln n)$, and so $\log_2(p_n) = \log_2 n + \log_2\log_2 n \pm ...
- 279k
3
votes
Examples of exact computation of Kolmogorov complexity?
The underlying problem with the example you quote is that it's informal and completely imprecise. As you say, why don't we include the size of the "simple algorithm"? Why are we allowed to assume that ...
- 82.2k
3
votes
Accepted
Turing machine that checks whether a given string is an output of a given machine and input
No. Any such machine $T^*$ would allow you to immediately solve the halting problem.
Given a description of $M$, construct a Turing machine $T_M$ that simulates $M$ and then outputs some fixed string,...
- 29.6k
2
votes
Accepted
An infinite subsequence of random numbers in Kolmogorov sense
If $x$ is Kolmogorov random then $C_U(ax+b) \geq \log x - O(\log a + \log b + 1)$ (why?), and so
$$
\frac{C_U(ax+b)}{\log (ax+b)} \geq \frac{\log x - O(\log a + \log b + 1)}{\log x + O(\log a + \log b ...
- 279k
2
votes
Accepted
Is a bitstring easier to compress if it has lower Kolmogorov complexity?
I think your intuition is not correct. We can't effectively reason over the space of all programs, even all programs up to a given size (e.g. 90 for A and 10 for b) and it's not certain what the units ...
- 56
2
votes
Accepted
Is $K(b|a) \geq 1$ if $a\neq b$?
Whether $K(a|a) = 0$ could depend on your universal computer. The only thing you can say in general is that $K(a|a) \leq C$ for some constant $C$ independent of $a$.
You can arrange for a universal ...
- 279k
2
votes
Computing the Kolmogorov complexity of a string
If we're talking about a generator who can handle any length $n$ seed (perhaps this is more cryptographic PRG oriented), and stretch it to some length $n'>n$ pseudorandom string, then the answer is ...
- 13.6k
2
votes
Accepted
Kolmogorov Complexity proving there exists a constant for when if two strings are equal length
Consider a procedure which has two inputs, $P$ and $DIFF$. Here $P$ is a self-delimiting program, and $DIFF$ is a list of indices, stored in some self-delimiting fashion (we leave the encoding vague ...
- 279k
2
votes
Accepted
Prove that A is non-regular using K-Complexity Non regularity theorem
Suppose that $A$ is regular. Then there exists a constant $c$ such that for all $x \in \Sigma^*$ and for all $n$ such that $Y^A_{x,n}$ exists, $C(Y^A_{x,n}) \leq \log n + c$.
Let us take $x = 0^{2m}1$...
- 279k
2
votes
Accepted
How can I prove the languages of incompressible words is undecidable?
Consider the word $w_n$ that is the output of $M'$ given input $n$.
Note that description of $w_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose ...
- 39.1k
Only top scored, non community-wiki answers of a minimum length are eligible