3 ms·
Surely we can do some sort of automated search at this point to give the shortest such program.
by Y_Y 6y ago
Surely we can do some sort of automated search at this point to give the shortest such program.
- rwmj 6y agoThat 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