3 ms·

Which important concept or algorithm can't be expressed in ≤1000 lines? Seems like a pretty common theme among groundbreaking ideas.

Y_Y 3y ago
That's a good question. Unfortunately I think you're asking to compute the Kolmogorov complexity of every interesting concept we have that doesn't yet have an implementation less than n=1000 lines, which is equivalent to the halting problem (modulo unbounded memory). If you could exhaustively list all the interesting algorithms (hard but feasible) you could potentially prove a lower bound for each one's complexity by writing a shorter than n implementation (hard, probably infeasiblel and show positively that GP's prop isn't true. On the other hand showing that it was true would require either some very clever proof which can't apply to all programs, but somehow only these interesting ones (very likely impossible) or enumerate all C^n programs where C is the number of possible lines (something like 64^80) and show that none of them implements at least one of the interesting algorithms (absurdly impossible).
- deleted 3y ago
  [deleted]
- nextaccountic 3y ago
  You are right but I think that there's a more interesting question: do humans stumble upon those large interesting/great algorithms in practice? The key point here is that we are looking at algorithms already discovered in human history rather than enumerating all possible interesting algorithms. Of course there is an interesting algorithm that is very large, but humans don't discover them in practice. If you look up a list of greatest algorithms in history, they will be rather small in length. Many of them can be sketched in a whiteboard I think that what is happening here is that our minds just can't hold billions of concepts at once. So if you have an algorithm with billions of things, it was most likely produced by a machine. Handcrafted things, on the other hand, are smaller in comparison Another thing is that our minds like conceptual simplicity and view simplicity as a kind of beauty. So if we have a great algorithm but it is too large, we look for ways to express them in succinct ways (the right abstractions can help with that, and also help with understanding the algorithm better). We end up succeeding because the algorithms themselves had low Kolmogorov complexity (and thus, if they are too large they probably can be further compressed)
magnat 3y ago
Most modern A/V codecs won't fit in that limit by several orders of magnitude. Even standard-compliant JPEG decoder would be hard to squeeze without some serious codegolfing. Discarding some barely used features gets you close to that limit, though [1]. Smallest popular TCP/IP stack [2] is ~20kLoC. [1] https://github.com/richgel999/picojpeg https://github.com/richgel999/picojpeg [2] https://savannah.nongnu.org/projects/lwip/ https://savannah.nongnu.org/projects/lwip/
- epr 3y ago
  A JPEG decoder or TCP stack are very clearly not individual concepts though. There's obviously some subjectivity as to what constitutes a single "concept" or "algorithm", but I'm not sure either of those two examples are in a gray area. A single concept might be implementing just ARP or a discrete cosine transform. If you wanted to do a full TCP stack or JPEG decoder, that would make a lot more sense after building their internal components one by one.
- naasking 3y ago
  JPEGDEC seems to be about 500 lines: https://github.com/bitbank2/JPEGDEC https://github.com/bitbank2/JPEGDEC
  - frankjr 3y ago
    More like 5000 https://github.com/bitbank2/JPEGDEC/blob/master/src/jpeg.inl https://github.com/bitbank2/JPEGDEC/blob/master/src/jpeg.inl
osigurdson 3y ago
This gave me an interesting thought... How many algorithms can be expressed in 1000 lines (say 5 - 80 chars per line) of correct C code. Obviously the number is huge if just look at char combinations (62^80E3 maybe) but if reduced to compiling / correct and unique (i.e. not including the same algorithm with differing variable names for example) the number would obviously be much less. If in the range of < 1E12 it could be practical to have AI further filter by recognizing useful algorithms. Who knows, there might be a warp drive in there somewhere!

Y_Y 3y ago

That's a good question. Unfortunately I think you're asking to compute the Kolmogorov complexity of every interesting concept we have that doesn't yet have an implementation less than n=1000 lines, which is equivalent to the halting problem (modulo unbounded memory). If you could exhaustively list all the interesting algorithms (hard but feasible) you could potentially prove a lower bound for each one's complexity by writing a shorter than n implementation (hard, probably infeasiblel and show positively that GP's prop isn't true. On the other hand showing that it was true would require either some very clever proof which can't apply to all programs, but somehow only these interesting ones (very likely impossible) or enumerate all C^n programs where C is the number of possible lines (something like 64^80) and show that none of them implements at least one of the interesting algorithms (absurdly impossible).

deleted 3y ago
[deleted]
nextaccountic 3y ago
You are right but I think that there's a more interesting question: do humans stumble upon those large interesting/great algorithms in practice? The key point here is that we are looking at algorithms already discovered in human history rather than enumerating all possible interesting algorithms. Of course there is an interesting algorithm that is very large, but humans don't discover them in practice. If you look up a list of greatest algorithms in history, they will be rather small in length. Many of them can be sketched in a whiteboard I think that what is happening here is that our minds just can't hold billions of concepts at once. So if you have an algorithm with billions of things, it was most likely produced by a machine. Handcrafted things, on the other hand, are smaller in comparison Another thing is that our minds like conceptual simplicity and view simplicity as a kind of beauty. So if we have a great algorithm but it is too large, we look for ways to express them in succinct ways (the right abstractions can help with that, and also help with understanding the algorithm better). We end up succeeding because the algorithms themselves had low Kolmogorov complexity (and thus, if they are too large they probably can be further compressed)

magnat 3y ago

Most modern A/V codecs won't fit in that limit by several orders of magnitude. Even standard-compliant JPEG decoder would be hard to squeeze without some serious codegolfing. Discarding some barely used features gets you close to that limit, though [1]. Smallest popular TCP/IP stack [2] is ~20kLoC. [1] https://github.com/richgel999/picojpeg https://github.com/richgel999/picojpeg [2] https://savannah.nongnu.org/projects/lwip/ https://savannah.nongnu.org/projects/lwip/

epr 3y ago
A JPEG decoder or TCP stack are very clearly not individual concepts though. There's obviously some subjectivity as to what constitutes a single "concept" or "algorithm", but I'm not sure either of those two examples are in a gray area. A single concept might be implementing just ARP or a discrete cosine transform. If you wanted to do a full TCP stack or JPEG decoder, that would make a lot more sense after building their internal components one by one.
naasking 3y ago
JPEGDEC seems to be about 500 lines: https://github.com/bitbank2/JPEGDEC https://github.com/bitbank2/JPEGDEC
- frankjr 3y ago
  More like 5000 https://github.com/bitbank2/JPEGDEC/blob/master/src/jpeg.inl https://github.com/bitbank2/JPEGDEC/blob/master/src/jpeg.inl

osigurdson 3y ago

This gave me an interesting thought... How many algorithms can be expressed in 1000 lines (say 5 - 80 chars per line) of correct C code. Obviously the number is huge if just look at char combinations (62^80E3 maybe) but if reduced to compiling / correct and unique (i.e. not including the same algorithm with differing variable names for example) the number would obviously be much less. If in the range of < 1E12 it could be practical to have AI further filter by recognizing useful algorithms. Who knows, there might be a warp drive in there somewhere!