# Tag Info

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.4k

### 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 ...

### 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 (...
• 162k
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 ...

### 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 ...
• 499

### 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, ...
• 278k
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 ...
• 162k
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 ...
• 278k

### What are very short programs with unknown halting status?

Collatz conjecture: The following program always halts: ...

### 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 ...
• 278k

### 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.6k
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
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 ...
• 278k

### 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,526

### 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

### 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 ...

### 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

### 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
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