5 ms·

He even did more: Mathematician GregoryChaitin defines elegance in computer programming in this way: A computer program written in a given language is elegant

by fxj 7y ago

He even did more: Mathematician GregoryChaitin defines elegance in computer programming in this way: A computer program written in a given language is elegant if no smaller program written in the same language has the same output. He goes on to prove that it is impossible to prove that a given program above a certain very low level of complexity is elegant. https://wiki.c2.com/?ChaitinElegance https://wiki.c2.com/?ChaitinElegance And he gave some examples in his book. http://jillian.rootaction.net/~jillian/science/chaitin/www.cs.umaine.edu/chaitin/unknowable/index.html http://jillian.rootaction.net/~jillian/science/chaitin/www.c... See the example code in LISP here: https://github.com/darobin/chaitin-lisp https://github.com/darobin/chaitin-lisp

misterman0 7y ago
>> His precise theorem is this: Define "LISP program-size complexity" to be the size of a LISP subroutine that examines a proof, determines whether it is correct, and returns either the theorem established by the proof (if the proof is correct) or an error message (if the proof is incorrect). Then, given a formal axiomatic system A, with LISP program-size complexity N, A cannot be used to prove that any LISP expression longer than N + 356 characters is elegant. Doesn't this in fact prove that numbers are discovered, not invented? He defines elegance to be "N". He defines N = 1 356 + N != N Thus, real numbers are real.
- Y_Y 7y ago
  I'm interested in the argument at the end of your comment, but I cannot understand it as-is. Could you flesh it out a bit please?
  - misterman0 7y ago
    I'm fascinated by Chaitin's Constant and his use of the word "elegance". His ideas challenge my current belief system. From the article: >> [what is] the probability that a randomly constructed program will halt [?] Where are you in life when this is a question that needs to be pondered? My bet is you're at a point where (when?) you question nature and/or human nature. >> Real numbers are real I meant to say, real numbers existed all along and were discovered, as opposed to being an invention. What made me come to this conclusion? Here's Chaitin (paraphrased): - run a process that through a series of operations produces a scalar, deterministically. - alter that process. - observe that the scalar has increased/decreased in value. I.e. numbers are "real".
OskarS 7y ago
The general principle here, which is quite foundational in computer science and the theory of complexity, is that of "Kolmogorov complexity". The Kolmogorov complexity of a certain string (roughly speaking) is the shortest computer program needed to produce that string. Much like Turing's halting problem or Church's beta-equivalence, it is impossible to write a program to calculate the Kolmogorov complexity in general. It is "non-computable".
- ramses0 7y ago
  That does a lot to explain why programming is so hard. "If you know the output you'd like, it's impossible to know how much code it will take to get there."
  - lisper 7y ago
    Not quite. What is impossible to know is if you have the shortest solution.
- derefr 7y ago
  And yet, we can fairly-easily upper-bound Kolmogorov complexity (often, we believe, quite tightly, though we can’t know for sure.) Quoting Wikipedia: > It is straightforward to compute upper bounds for K(s) – simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of a self-extracting archive in the given language. This is analogous (but not exactly) to the Travelling Salesman Problem: we “can’t” (in the case of Kolmogorov complexity, literally cannot) get the exact number, but getting a nearly perfect estimate of the number has cheap-and-easy algorithms. It’s fun to think about what an exact solution to computable Kolmogorov complexity would “mean”, though, sort of like it’s fun to think about the consequences of https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation: as a consequence of calculating the Kolmogorov complexity, you’d be optimally compressing the input data, identifying every possible nuance of self-similarity in the input, no matter on what level of abstraction it occurred. The intermediate model of the informational content required to construct the compressor would be immense—possibly a description of all mathematical theorems in the relevant axiom system, and all scientific laws governing the relevant generator-of-structure (e.g. physics, chemistry, biology, human psychology, etc.) Such a system really could “understand the universe from a grain of sand.”
claudiawerner 7y ago
>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 code golf elegant in most instances.
- 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.)
baruchel 7y ago
I was aware of Chaitin constant but not of Chaitin elegance; thank you for the link!

by fxj 7y ago

misterman0 7y ago

>> His precise theorem is this: Define "LISP program-size complexity" to be the size of a LISP subroutine that examines a proof, determines whether it is correct, and returns either the theorem established by the proof (if the proof is correct) or an error message (if the proof is incorrect). Then, given a formal axiomatic system A, with LISP program-size complexity N, A cannot be used to prove that any LISP expression longer than N + 356 characters is elegant. Doesn't this in fact prove that numbers are discovered, not invented? He defines elegance to be "N". He defines N = 1 356 + N != N Thus, real numbers are real.

Y_Y 7y ago
I'm interested in the argument at the end of your comment, but I cannot understand it as-is. Could you flesh it out a bit please?
- misterman0 7y ago
  I'm fascinated by Chaitin's Constant and his use of the word "elegance". His ideas challenge my current belief system. From the article: >> [what is] the probability that a randomly constructed program will halt [?] Where are you in life when this is a question that needs to be pondered? My bet is you're at a point where (when?) you question nature and/or human nature. >> Real numbers are real I meant to say, real numbers existed all along and were discovered, as opposed to being an invention. What made me come to this conclusion? Here's Chaitin (paraphrased): - run a process that through a series of operations produces a scalar, deterministically. - alter that process. - observe that the scalar has increased/decreased in value. I.e. numbers are "real".

OskarS 7y ago

The general principle here, which is quite foundational in computer science and the theory of complexity, is that of "Kolmogorov complexity". The Kolmogorov complexity of a certain string (roughly speaking) is the shortest computer program needed to produce that string. Much like Turing's halting problem or Church's beta-equivalence, it is impossible to write a program to calculate the Kolmogorov complexity in general. It is "non-computable".

ramses0 7y ago
That does a lot to explain why programming is so hard. "If you know the output you'd like, it's impossible to know how much code it will take to get there."
- lisper 7y ago
  Not quite. What is impossible to know is if you have the shortest solution.
derefr 7y ago
And yet, we can fairly-easily upper-bound Kolmogorov complexity (often, we believe, quite tightly, though we can’t know for sure.) Quoting Wikipedia: > It is straightforward to compute upper bounds for K(s) – simply compress the string s with some method, implement the corresponding decompressor in the chosen language, concatenate the decompressor to the compressed string, and measure the length of the resulting string – concretely, the size of a self-extracting archive in the given language. This is analogous (but not exactly) to the Travelling Salesman Problem: we “can’t” (in the case of Kolmogorov complexity, literally cannot) get the exact number, but getting a nearly perfect estimate of the number has cheap-and-easy algorithms. It’s fun to think about what an exact solution to computable Kolmogorov complexity would “mean”, though, sort of like it’s fun to think about the consequences of https://en.wikipedia.org/wiki/Hypercomputation https://en.wikipedia.org/wiki/Hypercomputation: as a consequence of calculating the Kolmogorov complexity, you’d be optimally compressing the input data, identifying every possible nuance of self-similarity in the input, no matter on what level of abstraction it occurred. The intermediate model of the informational content required to construct the compressor would be immense—possibly a description of all mathematical theorems in the relevant axiom system, and all scientific laws governing the relevant generator-of-structure (e.g. physics, chemistry, biology, human psychology, etc.) Such a system really could “understand the universe from a grain of sand.”

claudiawerner 7y ago

>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 code golf elegant in most instances.

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.)

baruchel 7y ago

I was aware of Chaitin constant but not of Chaitin elegance; thank you for the link!