What are...Chaitin’s constants?

Подписаться 27 тыс.

Просмотров 3,9 тыс.

50% 1

Goal.
I would like to tell you a bit about my favorite theorems, ideas or concepts in mathematics and why I like them so much.
This time.
What are...Chaitin’s constants? Or: Computing a glimpse of randomness
Disclaimer.
Nobody is perfect, and I might have said something silly. If there is any doubt, then please check the references.
Slides.
www.dtubbenhauer.com/youtube.html
The subtitle and thumbnail title is stolen.
www.emis.de/journals/EM/expma...
Chaitin’s constant.
citeseerx.ist.psu.edu/viewdoc...
en.wikipedia.org/wiki/Chaitin...
mathworld.wolfram.com/Chaitin...
sites.math.washington.edu/~mo...
Digits of Chaitin’s constant.
www.emis.de/journals/EM/expma...
www.cs.auckland.ac.nz/~cristi...
oeis.org/A100264
math.stackexchange.com/questi...
Halting problem.
en.wikipedia.org/wiki/Halting...
brilliant.org/wiki/halting-pr...
www.geeksforgeeks.org/halting...
Goldbach conjecture.
en.wikipedia.org/wiki/Goldbac...
mathworld.wolfram.com/Goldbac...
www.britannica.com/science/Go...
Background material.
mathworld.wolfram.com/Univers...
en.wikipedia.org/wiki/Turing_...
en.wikipedia.org/wiki/Computa...
Mathematica.
demonstrations.wolfram.com/Tu...
demonstrations.wolfram.com/Th...
www.wolfram.com/language/11/n...
demonstrations.wolfram.com/se...
Pictures used.
www.shantanualshi.com/static/...
en.wikipedia.org/wiki/Goldbac...
mathworld.wolfram.com/images/...
www.lifeiscomputation.com/wp-...
i.warosu.org/data/sci/img/011...
RU-vid and co.
• 4.7 Chaitin's Omega Nu...
mindmatters.ai/2021/04/is-cha...

Опубликовано:

29 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 16

@westpole Год назад

Loved this.....makes you really feel and hope there's more to mystery of numbers that goes beyond the omega...kinda like how we keep discovering x planets after pluto in our solar system...cheers!

@VisualMath Год назад

Rather big asteroids than planets ;-) But outside of the solar system there is a huge run on planets right now. I think that is pretty cool: the universe is so empty that it is remarkable that you can find anything nontrivial. Anyway, fun fact: most(=uncountable many versus countable many others) real numbers are not computable meaning that we cannot write find any reasonable expression for them, left aside being even able to think about them. (Omega is not computable but, for example, pi is computable because pi has "very efficient" sum expressions.) The real numbers are so weird that it is remarkable that you can find anything expressible. So in some sense it doesn't matter whether most real numbers exist or not: our brains cannot digest them. Anyway, enough waffle: glad that you like Omega; I am a big fan too!

@talumcatum8460 2 года назад

The reals really (heh) seem like the most unreal numbers out there... although I can "buy" the idea that they are useful due to how they're defined intuitively it seems like their definition admits too much weirdness (i.e. mostly instances that we can never even refer to, little-own construct most of them). I wonder if a tighter specification / mathematical structure could essentially provide all of the useful aspects of the real numbers (continuity, etc) without all the weird undefinable elements? I studied real analysis at uni but never really pondered until recently just how weird a concept they are. I think many mathematicians probably take them for granted too.

@VisualMath 2 года назад

Indeed, reals are really unreal ;-) You are not the only one wondering, but I think most mathematicians run the fair and efficient strategy to ignore “the problem of the reals” (ignoring problems until you can’t ignore them anymore is my favorite strategy - I apply it all the time!) due to several reasons: Firstly, it is a matter of taste whether one sees it as a problem that most real numbers are “weird” (most are even weirder than Chaitin’s constants). Second, and maybe more importantly, it actually doesn’t matter as the “weird” numbers, by definition, will never show up anywhere ;-) Third, it it not so clear what a “correct” definition is supposed to be - the one via e.g. Dedekind cuts is very straightforward and works fine in practice, so trying to convince other that one found a “better” definition will be tough. There are certainly more reasons but these are the main reasons imho. There are several subset of the reals that where invented partially trying to have some more controlled sets (computable numbers etc.) but none ever really made it to the popularity of the reals. Algebra has a much easier time than analysis. For almost all algebraic purposes the algebraic closure of Q (containing all solutions to polynomial equations with rational coefficients - the square root of 2 is in there, but pi is not) is absolutely sufficient.

@talumcatum8460 2 года назад

@@VisualMath thanks for the well thought out response! the way the reals admit nonconstructible values reminds me of the way types in computer programs often admit impossible implementations (e.g. one might have a type representing the reals even though in practice only the rationals or algebraic numbers will appear as instances when the program is executed). The types basically represent the algebra (in some languages we can specify the algebraic laws for them) and the instances represent the constructible elements of that algebra. It's useful mostly to simplify the specification like you say.

@beebag6861 2 года назад

Is this actually a normal number?

@VisualMath 2 года назад

Good question! The answer is "It depends" ;-) - Yes, it is. Roughly speaking, non-normal numbers can be compressed, but Chaitin's Omega is not compressible. - No it isn't. As Omega is not one constant but rather many. The precise statement depends on your preferred definition of it. See also: math.stackexchange.com/questions/1311792/when-is-chaitins-constant-normal - In other words, you should basically think that Chaitin's omega is normal, but then there are subtleties in the definition which might ruin the normality statement depending on the precise formulation and the integer base.

@srghma 2 года назад

what is "HP for all programs"?

@srghma 2 года назад

halting prob

@VisualMath 2 года назад

@@srghma Right, HP was my short hand for halting problem. Sorry if that wasn't clear enough!

@erawanpencil 9 месяцев назад

Is omega necessarily and exclusively defined with bits/binary 0-1 information? Would brining qubits into the picture, e.g. info that can be a superposition of 0 and 1, change anything? I guess I don't follow what the probability of a random computer halting has to do with the entire basis of mathematics... wouldn't such a probability merely tell you how quickly/smoothly information flows in your local part of the universe?

@VisualMath 9 месяцев назад

Excellent question! As far as I know, so far nobody has discussed Chaitin's constant for quantum computers. As of now, Chatin's constant is a 0-1-thingy. I would love to know more about this ☺

@Viggobrun 16 дней назад

Your explanation is a bit incorrect. The statement that every even number can be expressed as the sum of two prime numbers is the Goldbach Conjecture. In other words, the statement that every integer can be expressed as the sum of three prime numbers is the Goldbach Conjecture.

@VisualMath 16 дней назад

Thanks for your comment! What I had in mind is this one: en.wikipedia.org/wiki/Vinogradov%27s_theorem

@secretsecret1713 Год назад

What is the difference between constructable and algebraic ones?

@VisualMath Год назад

- Algebraic numbers are the roots of polynomials with rational coefficients, so for example 2^(1/3), the cube root of 2, is algebraic since it is a root of x^3-2. - Constructible numbers are those that can be constructed with compass and straightedge in a finite number of steps. This definition is a bit difficult to handle, which is the reason why it took a long time to get a good grip on them. Essentially you can think of these numbers as being roots of degree 2 polynomials with coefficients in a degree 2^(k-1) field extension of the rational numbers obtained recursively. (Note the appearance of only 2 and nothing else.) For example, a root of x^2-sqrt(2) would be constructible since we can construct sqrt(2)=2^(1/2) from x^2-2 first and are then allowed to use it as coefficients. - All constructible numbers are algebraic, but the converse is false: 2^(1/3) is not constructible because of the appearance of 3. I hope that helps!