4 ms·

> Kolmogorov complexity (wikipedia.org) is: "… the length of a shortest computer program (in a predetermined programming language) that produces the object as o

by tromp 1y ago

> Kolmogorov complexity (wikipedia.org) is: "… the length of a shortest computer program (in a predetermined programming language) that produces the object as output." > Small programs are interesting. But I’m also interested in small programming languages. Generally speaking, the smaller the language, the less expressive it is. It was the study of Kolmogorov complexity that motivated me to come up with the smallest and most expressive language for writing minimal size programs, and define the various flavors of Kolomogorov complexity in terms of it [1]. [1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861 https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

js8 1y ago
Hi, I like your work. Do you think there could be a universal combinator (like iota) and some binary encoding that would produce even smaller interpreters than BLC? I read your paper and you show that a simple encoding of S and K combinators seem to have longer interpreters. However.. What I don't fully understand, the complexity measure seems to depend on the binary encoding. So in theory, you could have a primitive combinator such that the interpreter is really short to express but the combinators for pair, true and false are rather long (when expressed in that primitive), thus hiding complexity in them. Makes me wonder, if you should only measure complexity of the interpreter combinator, and not also complexity of the "quoting" combinator, which would transform already existing encoded combinator into doubly encoded one, forcing you to represent pair, true and false combinators as well.
- tromp 1y ago
  > Do you think there could be a universal combinator (like iota) and some binary encoding that would produce even smaller interpreters than BLC? No; I don't think so. A iota based code (1 for application, and 0 for iota) loses out badly to the SK based code (1 for application, 00 for K, 01 for S). It would instead be better to pick slightly larger bases, picking up some elements like I,B,C, or W. > So in theory, you could have a primitive combinator such that the interpreter is really short to express but the combinators for pair, true and false are rather long (when expressed in that primitive), thus hiding complexity in them. Of course, we're not just optimizing for self-interpreter size, but for overall size across a large set of tasks, such as the important theorems of AIT, or such as the milestones in a busy beaver (surpassing Graham's Number / TREE(3) / Loader's Number [1]). The terms you mention, namely pair, true and false are not tasks, but the tiniest of data structures that you commonly use in programming tasks. Optimizing just for those is not as effective as for larger tasks that need to balance lots of data types and control structures. [1] https://oeis.org/A333479 https://oeis.org/A333479
veqq 1y ago
Here's an attempt to implement it: https://github.com/aartaka/cl-blc https://github.com/aartaka/cl-blc
- tromp 1y ago
  Thanks! Implementations of BLC in many other languages can be found at [1]. [1] https://rosettacode.org/wiki/Universal_Lambda_Machine https://rosettacode.org/wiki/Universal_Lambda_Machine

by tromp 1y ago

js8 1y ago

Hi, I like your work. Do you think there could be a universal combinator (like iota) and some binary encoding that would produce even smaller interpreters than BLC? I read your paper and you show that a simple encoding of S and K combinators seem to have longer interpreters. However.. What I don't fully understand, the complexity measure seems to depend on the binary encoding. So in theory, you could have a primitive combinator such that the interpreter is really short to express but the combinators for pair, true and false are rather long (when expressed in that primitive), thus hiding complexity in them. Makes me wonder, if you should only measure complexity of the interpreter combinator, and not also complexity of the "quoting" combinator, which would transform already existing encoded combinator into doubly encoded one, forcing you to represent pair, true and false combinators as well.

tromp 1y ago
> Do you think there could be a universal combinator (like iota) and some binary encoding that would produce even smaller interpreters than BLC? No; I don't think so. A iota based code (1 for application, and 0 for iota) loses out badly to the SK based code (1 for application, 00 for K, 01 for S). It would instead be better to pick slightly larger bases, picking up some elements like I,B,C, or W. > So in theory, you could have a primitive combinator such that the interpreter is really short to express but the combinators for pair, true and false are rather long (when expressed in that primitive), thus hiding complexity in them. Of course, we're not just optimizing for self-interpreter size, but for overall size across a large set of tasks, such as the important theorems of AIT, or such as the milestones in a busy beaver (surpassing Graham's Number / TREE(3) / Loader's Number [1]). The terms you mention, namely pair, true and false are not tasks, but the tiniest of data structures that you commonly use in programming tasks. Optimizing just for those is not as effective as for larger tasks that need to balance lots of data types and control structures. [1] https://oeis.org/A333479 https://oeis.org/A333479

veqq 1y ago

Here's an attempt to implement it: https://github.com/aartaka/cl-blc https://github.com/aartaka/cl-blc

tromp 1y ago
Thanks! Implementations of BLC in many other languages can be found at [1]. [1] https://rosettacode.org/wiki/Universal_Lambda_Machine https://rosettacode.org/wiki/Universal_Lambda_Machine