4 ms·

>A computer program written in a given language is elegant if no smaller program written in the same language has the same output. I would hesitate to call cod

• derefr 7y ago
  I think Chaitin Elegance is about “formal languages”, not notations (what we would call programming languages.) A formal language is an entire equivalence-class of bijectively-transformable notations. In other words, it’s the rules of the language as stated about its lexemes, not about its source bytes. Or, to say that another way, Chaitin Elegance is about the message-length of your program when put into the space-optimal notation for its formal language. For an extensional definition: a machine-code ISA, and its assembly language, are both the same formal language, just different notations for it. The assembly language is more verbose compared to the machine-code, but there’s a bijection between their semantics. Chaitin Elegance, for this formal language, would measure the byte-size of the program in its machine-code formulation, not in its assembler formulation. Long variable names in the assembler formulation don’t matter; but long function bodies do, if they coerce near jumps into far jumps. For another example: picture doing code-golf in Forth, where your goal is to minimize the number of Forth words you use in your program, not the number of bytes per se. (Note that in this case the “optimal notation” you’re measuring the elegance of doesn’t exist anywhere except in the in-memory state of the Forth VM, where it’s the compiled threaded-code representation of your program with all words represented as pointers.)