This is a great point. But these compressions work by establishing *regularity* in the self-evident/raw/explicit primitives they reproduce. And it's that regularity that provides for iteration. The hierarchies you're talking about work because each vertex in the branching structure (not always a tree) has something about it that's similar to some other vertex. A fully recursive system requires all the vertices to be the same in some sense, to have an invariant meaning no matter which "level" that vertex might be at.
As I tried to make clear in my response to Eric's digestion of the Bokov paper, I'm not suggesting that structures like DAGs are figments of our imagination, only the levels we impute onto them. I tried to make a similar argument a long time ago that "order" is a better term than "level". For example, if you group a set of primitives into tuples, 1-tuples, 2-tuples, 3-tuples, ..., you *can*, if you choose, to say all the 3-tuples form a level ... the 2nd level up (0th level being the 1-tuples, the primitives, 1st being the 2-tuples, etc.). But why? What power/usefulness is brought to the table by thinking of them as levels? What's wrong with the more accurate conception of "groupings of 3"? On 5/4/19 5:51 PM, Russell Standish wrote:
I don't think levels are just figments of imagination. Compression algorithms replace explicit descriptions with generative algorithms (like procedures of functions) that when called with appropriate parameters reproduce the original data. These generative descriptions have a tree-like structure, which is exactly the heirarchical structure you're after. Obviously, there is no unique compression algorithm, nor even a unique best algorithm. But I suspect that the best compression algorithms will probably agree up to an isomorphism on the heirarchical structure for most compressible data sets (note that this is already a set of measure zero in the space of all data sets :). I don't have any data for my hunch, though.
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com archives back to 2003: http://friam.471366.n2.nabble.com/ FRIAM-COMIC http://friam-comic.blogspot.com/ by Dr. Strangelove
