[FoRK] The World's Smallest Programming Language
Dave Long <
dave.long at bluewin.ch
> on >
Mon Sep 11 08:03:42 PDT 2006
> Seems to me there's probably some interesting intersection there with
> algorithmic information theory, Chaitin incompleteness / Kolmogorov
If these are the iota and jot I'm thinking of, see also "zot":
where he mentions Tromp's influence.
One very practical issue with combinator reduction is that it can be
not only exponentially larger, but also slower, than lambda or graph
Maybe I just need to read the speed prior stuff more closely, but it
seems that if algorithms jump drastically between big-O classes
depending upon whether they're expressed with naming/sharing or not, it
would affect which programs were chosen by a speed prior. Or does time
expand pretty uniformly across codes?
Depending upon how much you care, this might be a question for kc-list.
More information about the FoRK