a few days ago I asked a question about the limits of compression: Can PRNGs be used to magically compress-stuff?
The idea common to all the answers was that if you consider all programs of length < k (Let's call this set $C_k$), then there is only a finite number of possible outputs generated by programs in $C_k$ (let's call that set $S_k$).
In the comments, I asked a followup question roughly equivalent to "what determines which messages are possible outputs?" and have been thinking about this ever since.
It seemes clear that what determines that is the program that executes the program. If we ignore TM's and think in terms of source code, then the output of a piece of code depends only on the syntax and semantics of the programming language. So the language design determines the contents of $S_k$. There are some interesting corollaries:
- All program transformations that do no affect the AST nor enlarge the program beyond k bits will produce programs that generate the same output.
- All refactorings, which might alter the AST but preserve all input/output relationships, will do the same if they do not inflate the size of the source code.
- a PL that provides multiple constructs ("There's more then one way to do it") for achieving the same result (control flow constructs, for example) will , generally speaking, have more programs of length < k which generate the same output and so a smaller $S_k$ then a similar but "slimmer" PL.
This brings me to the following question: If I consider all programs in $C_k$ that generate the same output (it's an equivalence relation) and then proceed to compress them, what would be the results? Would the equivalent programs compress down to roughly the same size or not? Does the compressability depend on the meaning of the program (which is identical) or the bit sequence (which is not)?
A statement given in the answers to the previous question is that the entropy of a bit sequence determines how compressible it is. Is that entropy determined by the input/output relationships encoded in the program, or by it's bit-representation in language X? What's the right way to think of this?
update Since a program describes a computational process rather then merely output, the notion of equivalence suggested really doesn't indicate me much about the relative complexity of programs which are equivalent by that definition.