World's most popular travel blog for travel bloggers.

[Answers] Kolmogorov complexity vs purposefully inefficient Turing machines

, , No Comments
Problem Detail: 

It's a theorem that, although the Kolmogorov complexity of a string is relative to the Turing machine you're working with, it differs by at most a constant (basically the amount of space it takes to write an interpreter for Turing machine A inside of Turing machine B).

My question is: how does this theorem deal with the issue of Turing machines with purposefully inefficient encodings?

For example, suppose we have a universal Turing machine $M_{terrible}$ that requires its input to be repeated five times. It starts by verifying that the input is in fact of the form x ++ x ++ x ++ x ++ x, then executes the universal Turing machine $N$ on just x. Shouldn't this force the Kolmogorov complexity of strings relative to $M_{terrible}$ to be 5 times larger than they are relative to $N$? Why doesn't this violate the theorem?

Asked By : Craig Gidney

Answered By : Yuval Filmus

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 all such description languages result in the same notion of Kolmogorov complexity, up to an additive constant.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54643

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback