Skip to main content
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"...
Ariel's user avatar
  • 13.4k
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 ...
aslanides's user avatar
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.'s user avatar
  • 162k
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 ...
Ciro Santilli OurBigBook.com's user avatar
7 votes

Generate string with large Kolmogrov complexity

No. This is basically Chaitin's incompleteness theorem. Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed ...
Yonatan N's user avatar
  • 499
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, ...
Yuval Filmus's user avatar
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.'s user avatar
  • 162k
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 ...
Yuval Filmus's user avatar
5 votes

What are very short programs with unknown halting status?

Collatz conjecture: The following program always halts: ...
CoffeDeveloper's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Vor's user avatar
  • 12.6k
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 ...
David Taub's user avatar
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 ...
Yuval Filmus's user avatar
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.
Watercrystal's user avatar
  • 1,526
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 ...
Rainer P.'s user avatar
  • 852
3 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 ...
David Richerby's user avatar
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....
P. Trinli's user avatar
  • 101
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 ...
Wandering Logic's user avatar
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 ...
Jules's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
LeBleu's user avatar
  • 161
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.'s user avatar
  • 162k
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 ...
David Richerby's user avatar
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,...
Steven's user avatar
  • 29.5k
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 ...
Yuval Filmus's user avatar
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 ...
amashi's user avatar
  • 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 ...
Yuval Filmus's user avatar
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 ...
Ariel's user avatar
  • 13.4k

Only top scored, non community-wiki answers of a minimum length are eligible