13

The exact value of the Kolmogorov complexity depends on the language chosen to represent strings. This language has to be Turing complete, so representing all strings as themselves isn't an option. By the pigeonhole principle, if there is at least one string of length at most $n$ whose representation is shorter than itself, then there is also at least one ...


8

Any probability distribution. If you have a computable probability distribution that gives your data probability $p(x)$, then by the Kraft inequality, there's a computable compressor that compresses it in $-\log p(x)$ bits (round up if you object to fractional bits). This means pretty much any generative machine learning algorithm can be used. This is why ...


8

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 talk about without using much math. I'll do my best to explain informally here. The question is in two parts, so I'll address each separately. Models The ...


8

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", by Ming Li and Paul M.B. Vitanyi (see section 3.1). They give several examples where one can use the statement you mentioned instead of using the pumping ...


7

Fancy answer We need to show that the set $$R = \{x \in \{0,1\}^* \mid C(x) < |x|\}$$ is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to $$\exists n, m \in \mathbb{N} \,.\, T(n,0,m) \land U(m) = x \land |n| < |x| \tag{1}$$ where $T$ is Kleene's predicate and $U$ the associated output function. In words, the ...


7

It is impossible to give a specific example of a string with high Kolmogorov complexity. If I was to give an example in this answer, then the following piece of code would retrieve it: wget http://cs.stackexchange.com/q/9721 (plus some O(1) post-processing). A string of high Kolmogorov complexity is as elusive as a random number: There is in fact a ...


7

For any given problem, you can create a programming language where a program to encode the solution to that problem is a single character. (cf. HQ9+). Kolmogorov complexity is language dependent. The answer to your question about which problems cause a blowup will depend heavily upon whichever "standard formal language" you choose. There are some ...


7

We want to show $\overline{R_c}\in RE$. $\overline{R_c}=\left\{x|\exists M\hspace{1mm} s.t. \hspace{1mm} M(\epsilon)=x,|\langle M\rangle|<|x| \right\}$, i.e. $x$ is not a Kolmogorov-random string if there exists a Turing machine which outputs $x$ (say, when initialized with blank input), with description $\langle M\rangle$ shorter than $|x|$. Given $x$, ...


7

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 string can be proven to have Kolmogorov complexity larger than $C$. The core idea is that if you could do it for every string, then you can write a program of ...


6

The description of a string considered here is an input to some universal Turing machine. You can think of it as a C program. The string hello world does not, by itself, form a C program, but the following one does: int main(int argc, char *argv[]) { printf("hello world"); }. As you can see, the overhead is constant but not zero.


6

A result of Shannon's states that there exists a sequence of functions $f_n\colon\{0,1\}^n\rightarrow \{0,1\}$ that is so that the problem $P(n)$ of computing $f_n(x)$ for $x\in\{0,1\}^n$ requires at least $\Theta(\frac{2^n}{n})$ boolean operations (i.e. the circuit complexity of computing $f_n(x)$ is at least $\Theta(\frac{2^n}{n})$). This theorem is not ...


6

The problem is in your poor definition of "algorithmically random number" as applied to irrational numbers. In particular: has the same length (number of bits) as the number itself. has no meaning if the number is of unbounded length. Your Wikipedia link gives better definitions, which don't have this problem. For example (and paraphrasing ...


6

No, there is no general algorithm to compute a close approximation to the Kolmogorov complexity of the sequence $1,2,\dots,n$. Any candidate algorithm you come up with will have some inputs where it gives a bad answer (a poor approximation to the correct answer). Denote by $[n]$ the binary encoding of the natural number $n$, and let $[[n]] = [1],[2],\ldots,...


6

Should Kc be restated as being resource based and not solely program size based? No. If you change the definition like that, you get a different concept, and the different concepts deserves its own different name. If you want to examine that concept, you should give it its own name. Kolmogorov complexity is a standard term with an accepting meaning; ...


6

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 not defined; that's not something you can talk about. Kolmogorov randomness is a property of a bit-string. You can say that a particular bit-string (sequence) ...


6

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, given $xy$ and $|x|$, we can easily extract $x$. This shows that $K(x) \leq K(xy) + O(K(|x|))$. In particular, if $|x| = n$ then $K(xy) \geq K(x) - O(\log n)$.


5

This is a classical question in the foundations of Kolmogorov complexity: does the programming language matter for the sake of defining minimal description length? It depends on your model, but in general the answer is "no" or "almost no". Suppose that $P_1,P_2$ are two Turing complete programming languages. In particular, in $P_1$ you can write an ...


5

grammar coding is a less-frequently used version of a compression algorithm and can be taken as a "rough" estimate of Kolmogorov complexity. grammar coding is not as commonly used as a compression algorithm as other more common approaches maybe mainly because it doesnt improve much on compression from eg Lempel-Ziv on text based-corpuses, but it may do well ...


5

What Li and Vitanyi mean by a reasonable programming language is one that is Turing-complete. This means that you can simulate it on a Turing machine and you can simulate a Turing machine on it, so it has the same expressive power as a Turing machine. This gives you a kind of class of languages. I can prove that C is equivalent to a Turing machine, and that ...


5

For every $n$ there is a "busy beaver" machine (i.e., a Turing machine on the tape alphabet $\{0,1\}$ run on the empty tape) which outputs $1^n$ using $O(\log n/\log\log n)$ states, which is asymptotically optimal (up to constants). Here is how this machine works. For every $C$, we will construct such a machine having $O(\log n/C) + O(C2^C)$ states. The ...


5

You are stating the theorem incorrectly. The theorem states that the Kolmogorov complexity is the same up to a constant for essentially optimal description languages, which are those in which you can describe running a Turing machine on an input $x$ using $|x| + O(1)$ bits. Given this definition, it is a simple matter of playing with definitions to see that ...


5

Collatz conjecture: The following program always halts: void function( ArbitraryInteger input){ while( input > 1){ if(input % 2 == 0) input /= 2; else input = (input*3) + 1; } // Halt here } Slight variation (still a conjecture, because it's based on a result from Collatz's one): ...


4

That's right. You can run all machines in parallel and you'll find shorter and shorter descriptions, but at some point there will always be a shorter program still running, for which you can't prove that it won't halt with $x$ as output. The probability you describe (of a program not halting, assuming some distribution on inputs) is the complement to ...


4

Surprisingly, the Kolmogorov complexity of some arbitrary number is known to be uncomputable. So the general form of your question, is an arbitrary number algorithmically compressible is undecidable (i.e. the problem of computing the algorithmic complexity of a sequence). This can be proven by reduction to the Halting problem. Problems that are known to be ...


4

The problem with your approach is that some programs never halt, and it's difficult (indeed, uncomputable) to tell whether they do. You can tell if a program outputs $s$ and halts, but you don't know how much to wait before declaring that the program never halts. However, your approach shows that it is possible to write a program that prints upper bounds on ...


4

The idea of the incompressibility method is that an incompressible input satisfies certain properties that can be helpful in the analysis. In your case, the complexity of the algorithm depends on how many characters appear in the string. When processing the $k$th character, the "running time" (or rather its proxy, the number of comparisons when checking the ...


4

A big thing that is studied in higher type computability is infinite streams. Others have talked about hyper computation but this isn't quite the same. For starters the objects and functions studied in higher type computability are all things you can do in Haskell or some other such real programing language. These functions DO terminate in finite time thanks ...


4

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 you better understand the role of Kolmogorov complexity. The key idea is the following: a finite automata $D$ (that recognizes a regular language $L_D$) has a ...


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