3 ms·
That would (kind of) be the Kolmogorov complexity[1] (only kind of - the Kolmogorov complexity is actually the shortest program that produces a single output, r
by rwmj 6y ago
That would (kind of) be the Kolmogorov complexity[1] (only kind of - the Kolmogorov complexity is actually the shortest program that produces a single output, rather than the shortest program that implements an algorithm). In any case the search space is still vast: making some assumptions about the number of bits in a character of C source code, you'd be searching something like 2^(6*60) bits, a number with about 108 decimal digits. We're in "longer than the lifetime of the universe" territory here. It might be better to search C ASTs instead, although the numbers are still going to be huge.
The general field of endeavour for searching binary programs is called superoptimization[2] and people really do it for very small program fragments.
[1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity
[2] https://en.wikipedia.org/wiki/Superoptimization https://en.wikipedia.org/wiki/Superoptimization