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


12

The central concept here is Kolmogorov complexity, and more specifically compressibility. To get a intuitive feeling of compressibility, consider two strings $A \in \mathbb{B}^*$ and $B \in \mathbb{B}^*$, where $\mathbb{B} = \{ 0,1 \}$. Let $A = 1010$ $1010$ $1010$ $1010$, and $B = 1011$ $0110$ $0111$ $1001$. Note that $|A| = |B| = 16$. How could ...


9

I guess one possible answer to your question is this: Take a pseudorandom number generator $G$. Try to chose a generator which has some powerful attacks against it: a random number generator attack for $G$ is (for our purposes), an algorithm $A$ which, when given an imput string $s$, determines a seed $A(s)$, such that $G(A(s))=s$. Then approximate the KC of ...


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

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

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

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


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

I apologize in advance for that I give way too many details, but I'm about to contradict people. About $K(x)≤K'(x)+c$ The fact that $K_1(x)≤K_2(x)+c$ usually comes from an interpreter of the description language #2 into the description language #1 and not from a translation from programs of #2 into programs of #1. For example $K_\mathtt{C}(x)≤K_\mathtt{...


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 formatting): ...


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

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

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


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

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): ...


5

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)$.


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

Like Kaveh said, you can view a decision problem as a language consisting of the descriptions of all the "yes" instances. Then the Kolmogorov complexity of the language is, as you said, the length of the smallest program that produces all those descriptions. How we describe the program that generates the instances (and hence defines the Kolmogorov ...


4

We can view of a language $A$ as an infinite binary string (the infinite binary string corresponding to the characteristic function of $A$) and then use the notion of Kolmogorov complexity for such strings. Google for: Kolmogorov complexity infinite words


4

It could be because "useful" is hard to define. Say we have a highly-structured, information-rich message $x$ which can be compressed at most by a factor of $\alpha$ to the message $y$. Intuitively, $x$ and $y$ contain the same amount of useful information; indeed, they contain the same amount of information according to the usual definition. Now imagine a ...


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