4 ms·
I think I once read that only an exponentially small fraction of binary strings are valid BLC programs. In theory this means you could create shorter programs b
by murbard2 10y ago
I think I once read that only an exponentially small fraction of binary strings are valid BLC programs. In theory this means you could create shorter programs by merely enumerating valid BLC programs, which is bothersome. Is this a correct characterization and do you see a fix?
EDIT: there's the paper https://www.cambridge.org/core/journals/journal-of-functional-programming/article/counting-and-generating-terms-in-the-binary-lambda-calculus/47DE83E8BD697326F0FFD43351E083E3 https://www.cambridge.org/core/journals/journal-of-functiona... citing an exponent of 1.963447954...
- tromp 10y ago> I think I once read that only an exponentially small fraction of binary strings are valid BLC programs This is true for the encoded lambda calculus prefix; but not for the entire BLC program in which you can embed arbitrary binary data. > In theory this means you could create shorter programs Not really; BLC is universal, so program sizes are optimal up to a constant. In other words, for any language L, there's a constant c_L, such that for all x, the complexity of x according to BCL is at most a c_L larger than the complexity of x according to L.
- murbard2 10y agoCool, I was wondering that. So you confirm that I can embed arbitrary binary data in a BLC program with only a constant overhead?
- tromp 10y agoWith two caveats: the binary data must come after the encoded lambda expression, and in case of self-delimiting programs, that lambda expression must somehow know where the binary data ends.