News for hackers. Stuff that matters.

A comment on Xmas.c, winner of the 1988 International Obfuscated C Code Contest. Parent comment

Re:Xmas.c, winner of the 1988 International Obfuscated C Cod... by smallnamespace on Saturday December 23, 2023 @07:38PM (#38749842)
> 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.

[ Parent | on HN ]
Re:Xmas.c, winner of the 1988 International Obfuscated C Cod... by tromp on Sunday December 24, 2023 @03:34AM (#38752131)
> 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...

[ Parent | on HN ]