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.
Exactly right! I kinda think that these non-computable problems are all sort-of the same problem, just viewed from different angles.
> 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.”
"If you know the output you'd like, it's impossible to know how much code it will take to get there."
I would hesitate to call code golf elegant in most instances.
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.)
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.
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".
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