4 ms·
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
by 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.