7 ms·
Chaitin's Constant
- benji-york 7y agoI'm a fan of Fulton's constant. Fulton's constant is any number of 9s. E.g., 9, 999, or 999999.
- dboreham 7y agoNot to be confused with his Croissant.
- deleted 7y ago[deleted]
- me_me_me 7y agoCan somebody explain to me how is this useful? Is it used for anything? Or is it pure theoretical concept with interesting emerging properties.
- tialaramex 7y agoThe 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.
- me_me_me 7y ago> The idea is useful yes. Well that's the crux of my question, how can it be useful wen its completely undefined.
- jerf 7y agoThe idea is mathematically useful. If you're asking about it's practical use, it has none.
- deleted 7y ago[deleted]
- balfirevic 7y agoIt is defined, very rigorously actually. But it is uncomputable.
- fxj 7y agoThe 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 http://mathworld.wolfram.com/ChaitinsConstant.html
- tromp 7y agoThat machine is NOT universal in the required sense, since each data bit is given in ASCII and contributes 7 bits to the program length.
- mFixman 7y agoI find this constant to be the most intuitive way to define uncomputable numbers, which itself is the most intuitive way to define uncountable sets.
- frutiger 7y ago> which itself [uncomputable numbers] is the most intuitive way to define uncountable sets Can you explain your intuition for this step?
- mFixman 7y agoOne 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.
- frutiger 7y agoYou 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.
- mFixman 7y agoI 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.
- fxj 7y agoIt 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.cs.umaine.edu/chaitin/unknowable/turing.l http://jillian.rootaction.net/~jillian/science/chaitin/www.c... He also writes in his book: http://jillian.rootaction.net/~jillian/science/chaitin/www.cs.umaine.edu/chaitin/unknowable/ch7.html 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.]
- fxj 7y agoHe 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 agoI'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 agoI'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".
- KboPAacDA3 7y agoNumberphile 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 https://www.youtube.com/watch?v=5TkIe60y2GI
- jaymzcampbell 7y agoIf 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_ https://www.goodreads.com/book/show/249849.Meta_Math_).
- alanbernstein 7y agoIt'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.
- daxfohl 7y agoThe 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.
- Chris2048 7y agoIn contrast: https://www.jamesrmeyer.com/topics/chaitins-omega.html https://www.jamesrmeyer.com/topics/chaitins-omega.html
- opengrave 7y agoI just want to drop this playlist here https://www.youtube.com/watch?v=HLPO-RTFU2o&list=PL86ECDEDE3FA8D8D1 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.
- jdkee 7y agoThanks for the link. I just watched that lecture and it really concretized a number of concepts from the literature. Kudos to Gregory Chaitin.
- deepnotderp 7y agoAfaict Chaitin independently came up with the concept of Kolmogorov complexity... as a teenager!