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