News for hackers. Stuff that matters.
Re:Chaitin's Constant by me_me_me on Monday January 20, 2020 @08:32AM (#22098635)
Can somebody explain to me how is this useful? Is it used for anything?

Or is it pure theoretical concept with interesting emerging properties.

Re:Chaitin's Constant by mFixman on Monday January 20, 2020 @08:56AM (#22098793)
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.
Re:Chaitin's Constant by frutiger on Monday January 20, 2020 @11:49AM (#22100078)
> which itself [uncomputable numbers] is the most intuitive way to define uncountable sets

Can you explain your intuition for this step?

Re:Chaitin's Constant by mFixman on Monday January 20, 2020 @12:36PM (#22100493)
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.

Re:Chaitin's Constant by yongjik on Monday January 20, 2020 @03:00PM (#22101668)
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.

Re:Chaitin's Constant by frutiger on Monday January 20, 2020 @12:44PM (#22100555)
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.

Re:Chaitin's Constant by mFixman on Monday January 20, 2020 @03:44PM (#22101949)
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.

Re:Chaitin's Constant by fxj on Monday January 20, 2020 @09:20AM (#22098937)
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.]

Re:Chaitin's Constant by tialaramex on Monday January 20, 2020 @08:42AM (#22098701)
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.

Re:Chaitin's Constant by fxj on Monday January 20, 2020 @09:25AM (#22098972)
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

Re:Chaitin's Constant by tromp on Monday January 20, 2020 @09:30AM (#22099007)
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.
Re:Chaitin's Constant by me_me_me on Monday January 20, 2020 @08:46AM (#22098731)
> The idea is useful yes.

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

Re:Chaitin's Constant by jerf on Monday January 20, 2020 @08:52AM (#22098763)
The idea is mathematically useful.

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

Re:Chaitin's Constant by balfirevic on Monday January 20, 2020 @10:45AM (#22099590)
It is defined, very rigorously actually. But it is uncomputable.