|
|
|
|
|
|
by smallnamespace
911 days ago
|
|
|
> would there be even shorter programs that don't look like they make sense but produce the same output Yes, mostly likely > How would you search for these programs? Brute force search is very inefficient so the real answer generally is "be clever" in the mathematical sense. In general, KC is not computable so there is no program that can take a string and return the shortest program that computes that string. However it's always in principle possible for someone to prove that the KC of some particular string is X. |
|
|
Only for a bounded number of strings. I.e. there is a finite set of string X such that for strings outside of X, you can not prove their KC, even in principle.
This result by Chaitin [1] can be paraphrased as: you cannot prove a 2 kilo theorem with a 1 kilo theory.
[1] https://www.jucs.org/jucs_2_5/the_limits_of_mathematics/Chai...