Chaitin's Constant | Hacker News Reader

Chaitin's Constant

en.wikipedia.org

81 pointsmgreenleaf38 comments

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

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

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?

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

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

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

Not quite. What is impossible to know is if you have the shortest solution.

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

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.

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

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

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

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

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

If you want to read a bit more from the mathematician himself on this very topic he wrote an accessible "pop-math" book about it, "Meta Math!: The Quest for Omega" though you'll need to look beyond the author's rather strange choices of metaphor (https://www.goodreads.com/book/show/249849.Meta_Math_).

It's been a while, but I assume you're referring to the similarities drawn between information theory and sex. This was pretty offputting to me, until I realized the connection was deeper than I recognized - DNA is an apt comparison.

I've read plenty of "pop math" books, and this one stands out as somewhat odd. It's also a quick read and, somewhat uncommonly, written by a person closely connected to the topic - so I'd recommend it.

I just want to drop this playlist here https://www.youtube.com/watch?v=HLPO-RTFU2o&list=PL86ECDEDE3... as its one of my fav lectures

Gregory Chaitin Lecture at Carnegie-Mellon University in 2000, he gives a bit of history of parts of math/computing that leads up to him talking about qualities of random. He touches on Cantor, Bertrand Russell, Hilbert, Gödel and Turing.

Thanks for the link. I just watched that lecture and it really concretized a number of concepts from the literature. Kudos to Gregory Chaitin.

Afaict Chaitin independently came up with the concept of Kolmogorov complexity... as a teenager!

The surprising thing to me was, following the link to "normal numbers", that this is called out as one of the only proved irrational normal numbers, even though it is proven that the set of irrational numbers is normal almost everywhere.

Can somebody explain to me how is this useful? Is it used for anything?

Or is it pure theoretical concept with interesting emerging properties.

The constants themselves would perhaps be useful but they're non-computable so we can't find out what they are anyway.

The idea is useful yes.

> The idea is useful yes.

Well that's the crux of my question, how can it be useful wen its completely undefined.

The idea is mathematically useful.

If you're asking about it's practical use, it has none.

It is defined, very rigorously actually. But it is uncomputable.

The value of a Chaitin constant is highly machine-dependent. In some cases, it can even be proved that not a single bit can be computed (Solovay 2000).

Chaitin constants Omega_U are perhaps the most obvious specific example of uncomputable numbers. They are also known to be transcendental.

Calude et al. (2002) computed the first 64 bits of Chaitin's constant Omega_U for a certain universal Turing machine as

Omega_U = 0.0000001000000100000110..._2 (2) = 0.00787499699...

http://mathworld.wolfram.com/ChaitinsConstant.html

That machine is NOT universal in the required sense, since each data bit is given in ASCII and contributes 7 bits to the program length.

I find this constant to be the most intuitive way to define uncomputable numbers, which itself is the most intuitive way to define uncountable sets.

> which itself [uncomputable numbers] is the most intuitive way to define uncountable sets

Can you explain your intuition for this step?

One of the ways to define the set of computable numbers is as the set of numbers for which there exists a program that, given an integer, gives you the n'th digit of this number.

This set is countable: each one of these programs represents a single number, and you can use Gauss to transform any program into a integer and vice-versa. What's amazing is that almost every real number you heard about is part of this set: pi, e, and √2 can all be nicely put into a well-defined countable set.

The set of the reals is uncountable, which means that almost every number is uncomputable like Chaitin's constant.

You have described how the set of computable numbers are countable. But you have then posited "the set of the reals is uncountable" without any further explanation as to how that is the case. Your explanation helps one understand why computable numbers are countable (and that is for sure a useful insight), but says nothing about uncountable sets.

I still feel the diagonal argument is the clearest intuition for defining an uncountable set.

I was taught that real numbers were countable before learning what computables numbers where. "There's a set of countable numbers that includes every real number you know and doesn't include handwavy concepts" was news to me.

Personally, I never found the diagonal argument intuitive. The proof with the nested open intervals in a sequence was easier for me to understand, but that's probably because I have more of a background in CS.

Just a second, that's technically true, but the set of all "uncomputable but definable(?)" numbers is also countable, which includes Chaitin's constant (and any uncomputable number that can be reasonably called "X's constant").

Almost every real number is not only not computable, they aren't even definable.

It might have some relevance in information compression. He was also working on the halting problem (see lisp code below) and writing programs in LISP that were proving his theorems.

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

He also writes in his book:

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

So in a way, in all three cases, Gödel, Turing, and I, we already have a new ``biological'' complicated mathematics, the mathematics of the third millennium, or at least of the 21st century. [As a child I used to dream that I was in the far future, in a library, desperate to see how it had all turned out, desperate to see what science had achieved. And I would take a volume off the shelf and open it, and all I could see were words, words, words, words that made no sense at all... Writing this book brings back long-forgotten thoughts and the unusual lucidity I experience when my research is going well and everything seems inevitable.]

Numberphile has a video explaining the relationship between the number categories, and includes a brief discussion of where Chaitin's Constant belongs.

https://www.youtube.com/watch?v=5TkIe60y2GI

In contrast: https://www.jamesrmeyer.com/topics/chaitins-omega.html

I'm a fan of Fulton's constant.

Fulton's constant is any number of 9s. E.g., 9, 999, or 999999.

Not to be confused with his Croissant.

Reply on news.ycombinator.com