3 ms·

This is a fascinating topic and is related to the Kolomogorov complexity [1] and the densest I'm aware of is John Tromp's Binary lambda calculus [2]. I don't s

This is a fascinating topic and is related to the Kolomogorov complexity [1] and the densest I'm aware of is John Tromp's Binary lambda calculus [2]. I don't see a reason why the implementation would be larger than the Java NanoVM. However programs in the pure λ-calculus are likely to be slower than necessary and I'd go with one enriched with at least basic integers and integer ops. ADD: yes I know that Kolomogorov just measures self-replication, but I think it's a good proxy for code entropy. At least, I don't know of a better one. [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity [2] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html

kragen 5y ago
It's an interesting idea. Apparently there's a 400-byte implementation of Tromp's blc, but I suspect you could make the interpreter both smaller and faster by using bytecodes rather than Tromp's binary codes, which I think are optimized for giving a plausible measure of Kolmogorov complexity. I've also been working on an interpreter called Qfitzah for large machines; it implements a term-rewriting language with pattern-matching, dynamic containers, dynamic typing, and dynamic polymorphism in under 1000 bytes: http://canonical.org/~kragen/sw/dev3/qfitzah.s http://canonical.org/~kragen/sw/dev3/qfitzah.s My next step on it is to enrich it with basic integers and integer ops. I don't think Kolmogorov complexity measures self-replication. Rather, it uses the code to produce ("replicate") a string to measure that string's entropy.