News for hackers. Stuff that matters.
Re:Chaitin's Constant by fxj on Monday January 20, 2020 @09:15AM (#22098906)
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

And he gave some examples in his book.

http://jillian.rootaction.net/~jillian/science/chaitin/www.c...

See the example code in LISP here:

https://github.com/darobin/chaitin-lisp

Re:Chaitin's Constant by OskarS on Monday January 20, 2020 @10:43AM (#22099576)
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".
Re:Chaitin's Constant by whatshisface on Monday January 20, 2020 @11:46AM (#22100048)
>it is impossible to write a program to calculate the Kolmogorov complexity in general. It is "non-computable".

I don't get it, why couldn't you "simply" iterate through every program shorter than the string you're trying to compress, compiling and running each while discarding the ones with the wrong output and halting when you either find a working program or run out of shorter strings to try?

Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem.

Re:Chaitin's Constant by OskarS on Wednesday January 22, 2020 @11:47AM (#22119157)
> Edit: Oh, I get it now, you can't tell whether or not a given long-running program will eventually produce the target string without solving its halting problem.

Exactly right! I kinda think that these non-computable problems are all sort-of the same problem, just viewed from different angles.

Re:Chaitin's Constant by derefr on Monday January 20, 2020 @11:24AM (#22099897)
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: 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.”

Re:Chaitin's Constant by perl4ever on Thursday January 23, 2020 @09:29PM (#22134853)
If you take the first million digits of pi, and compress it with, say, bzip2, you get a file of about 420KB. This is pretty good in one sense - an 8 bit byte that stores a decimal digit can store 3.3 bits of information, right? As such, you would expect output to be 3.3/8 or about 42%. But obviously that 420KB + a decompressor is nowhere near a minimal program. I've always been fascinated with the Mandelbrot/Julia sets and where that information comes from as well.
Re:Chaitin's Constant by ramses0 on Monday January 20, 2020 @10:57AM (#22099697)
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."

Re:Chaitin's Constant by lisper on Monday January 20, 2020 @01:21PM (#22100880)
Not quite. What is impossible to know is if you have the shortest solution.
Re:Chaitin's Constant by claudiawerner on Monday January 20, 2020 @10:58AM (#22099700)
>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.

Re:Chaitin's Constant by derefr on Monday January 20, 2020 @11:43AM (#22100028)
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.)

Re:Chaitin's Constant by baruchel on Monday January 20, 2020 @12:29PM (#22100417)
I was aware of Chaitin constant but not of Chaitin elegance; thank you for the link!
Re:Chaitin's Constant by misterman0 on Monday January 20, 2020 @09:40AM (#22099081)
>> 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.

Re:Chaitin's Constant by Y_Y on Monday January 20, 2020 @09:43AM (#22099103)
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?
Re:Chaitin's Constant by misterman0 on Monday January 20, 2020 @10:28AM (#22099441)
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".