This makes me think about kolmogorov complexity. The program here looks like gibberish but produces the desired output, would there be even shorter programs that don't look like they make sense but produce the same output? How would you search for these programs?
#define p printf
int main(){const char *g[]={"A Partridge in a Pear
Tree.\n","Two Turtle Doves, and","Three French Hens,","Four
Calling Birds,","Five Gold Rings,"," Geese-a-Lay"," Swans-
a-Swimm","t Maids-a-Milk","e Ladies Danc"," Lords-a-Leap","
Pipers Pip","Twelve Drummers Drumm"};
const char *d[{"First","Second","Third","Four","Fif","Six","Seven","Eigh","Nin","Ten","Eleven","Twelf"};for(int i=0,j;i<12;i++){p("On
the %s%s day of Christmas\nMy true love sent to
me\n",d[i],i>2?("th"):"");
for(j=i;j>=0;j--){p("%s%s%s\n",j>4&&j<11?
d[j]:"",g[j],j>4?"ing,":"");}}}
Technically yes, initializing a plain char * from a const char * (from array decay) is a constraint violation (an error the standard requires the compiler to detect and complain about) even in C89. Many compilers will let you off with a warning though.
> 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.
I think it's honestly quite hard to know, as it's really (generally speaking, AFAIPK) impossible to directly compute the KC in most cases, only really from the feasibility standpoint we can check that it's slower than some other version/value.
Which is quite exciting, it sets us up nicely for long-running competitions and the like due to the logarithmic-like growth curve (with sometimes some very fun discoveries on the ultra-tail-end of things! <3 :D)
Am currently running a mini-competition with a current prize bounty of $100 (distributed proportionally by % contribution in logspace) for an LLM that can memorize the most digits of Pi by March of next year. Pi is nice as it actually is quite compressible in theory and seeing if a model is able to learn a sufficiently-close-to-the-MDL set of weights that recovers a highly-compressed algorithm from the data would be extremely nice, indeedy!
However, whether this is feasible or not with off-the-shelf models and such is not entirely easy to know, so for now, it's just a digits-memorizing competition, and we shall see where it goes from there!!! <3 :'))))
