If you want to make money online : Register now

Why can't we search lexicographicaly ordered programs to compute Kolmogrov complexity?

, , No Comments
Problem Detail: 

Kolmogrov complexity is known to be uncomputable. Why can't we enumerate all programs of size i = 0 in lexicographical order - if any produce string s, that is the Kolmogrov complexity; if not, increment i and iterate? Won't that prove that no program of length < i generates string s?

Asked By : SRobertJames

Answered By : Yuval Filmus

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 the Kolmogorov complexity of a give string, eventually printing the correct upper bound. This doesn't give you the Kolmogorov complexity since you don't know when the program will have printed its final upper bound.

Best Answer from StackOverflow

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

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback