Hi everyone, I'm here to express my extreme gratitude for the amazing comments. We're clearly blessed with a cool and wholesome community. You all rock! I can tell you that my dad was extremely moved by all of your wishes. He asked me to convey this message, straight from him to all of you: " I want to thank you all for the many birthday wishes. It is an exceptional and unexpected gift. Also, my heart warms up when I see your appreciation for the work of my son. I would like to complement his motto 'keep learning' with mine: 'keep teaching'. Knowledge has this peculiar property that the more of it you give away, the more of it you have left. Have a goof life. "
BTW, we won't be able to solve *all* maths problems with Omega because Omega has no information about programs that have access to omega. This is the hierarchy of hyper computation or something like that, and it's really neat. But yes realistically all problems we care about are problems about programs that don't have access to omega
Well that is why omega is uncomputable, if it could be computed, we’d have that problem, we also actually know it’s irrational, because if it was rational it would be computable
Happy Birthday, All Angles's Dad! I too am a software engineer. I have an 18 month old little boy. I think there are many, ways in which I could succeed as a parent, but if in two decades time, my boy is making RUclips videos (or whatever has replaced them) which challenge me to think and learn in the same way that your boy has done for me today, I will feel super proud of what he has achieved. And if he traces any part of his love of learning and his willingness to challenge himself back to me, then I in turn will trace it back to videos like this one that have helped and inspired me. Thank you so much for helping to create a world filled with the passion and curiosity
Doesn't omega depend on the system being used? So it's not really a constant like pi, unless you specify the system you are working in (some specific lambda calculus, for example)
You're right, the exact value will depend heavily on all the choices we make along the way. I didn't want to get bogged down in the details, so I skipped over it. But well spotted.
I think that to compute the number to a certain accuracy would require you to know the answers to all the problems it could solve, so it's less of an oracle and more of a compression algorithm. And an optimal one too, since it's not compressible further!
I just turned 75 too, and I'm also a Dad, so happy birthday to both us Dads! I found an interesting pattern for the composites of Euler's quadratic. Perhaps you can find it too.
The halting problem is decidable for finite deterministic systems, so it's theoretically possible to calculate omega for some systems. Unfortunately, any problem worth solving with omega would require massive amounts of computational power
Oh, it's my dad's birthday today as well. I think he's 76, I always forget whether it's my mum or dad was born in 48 or 49. What a nice coincidence. :) Happy b'day to both our dads.
Belated happy birthday to your Dad from France. Good work getting your (now grown) child interested enough in these topics that now they are making videos for the engineers like me who didn't get to learn the spicy bits of the math.
Happy birthday to your dad from Poland! By the way, I believe even if we knew the value of omega, running all possible programs at once could be tricky - at a trillion in, we would still be looking at programs that print random constants
Happy birthday from Russia🎉 About hauling problem - had anyone proved that it's the same number for any Turing-complete language? Cuz if it's not true, we could state the opposite problem - choose number between 0 and 1. For said number construct a programming language in a way that it's hauling constant would be this arbitrary number.
A key step in our journey to figuring out if a program halts or not is using omega-n, where n is the "length" of our program and then used to take the first n digits of omega. A few questions I've been thinking about as a result of this and my thoughts (feel free to chime in): Questions - Is it possible that omega has less than n digits? I.e. does omega have infinitely many digits? Does a random number have to have infinitely many digits? Why is omega "random"? Thoughts - From the video, a key point is that a number is random if (and only if?) it is incompressible. Thus, if a number is not random, we could write a program to write out its digits. If it is random, we could not do that. So, if a number has finitely many digits, we should be able to write a program with finitely many steps to write out the digits of that number. So a random number must have infinitely many digits. Secondly, Turing proved through the halting problem that we can't have a program determine whether all programs will halt or not. Thus, we can't compress the probability that a random program halts, and so omega must be random. Since omega is random, it must have infinitely many digits, meaning we could always take the first n digits for arbitrary n. I'm little shaky on that second jump. Let me know if I'm missing something or can think about it in a different way. Great video and happy birthday to dad!
Hi, nice explanation video ! I'm currently working on a video on the exact same subject and I have some remarks, especially on the part "how the oracle works": The Omega that you describe in your video is not defined on a prefix computing model which mean that it is possible that your Omega can be greater than 1 for example if the 2 programs of length 1 (the ones encoded by 0 and 1) both halts they will both add a wheight of 0.5 which will make the total already equals to 1. And by your defenition that would mean that even if there are only thoses two programs which halts the probability of any programs to halts will be 1 (Omegas can be seen as a probability but not in a direct way) . At 17:48 you said that you work only on the shorts programs which means that you can only compute a lower bound of that omega because there are programs on size greater than n that can have an impact of the first bits. To do so you have to not work only on the programs of size n but all programs of your computing model. Since there is an infinity of programs you can't do the trick of "I do one step of each programs and I start again" because that would mean that you can only performs at most one step of each program, to get over this you can use what we call a "Dovetailling" which works like the bijection between N and N^2. I know i am being really pedantic about theses little details but as I said, this is a nice explanation video that probably make the whole concept understandable for a person that don't know about it already and all of thoses details can take a while to explain and might hurt your audience retention so keep it that way 😄
Just to clarify: the reason why we can't know omega is not because you can't write it down, but rather that it is impossible to *prove* that that number is indeed omega. Similar to how it's impossible to prove the continuum hypothesis, or gödel's incompleteness theorem
No - if we could write it down (compute it with finite means) then there would be a halting function. We might not be able to prove that it is actually the halting function, but it would work all the same. Since the existence of the halting function leads to contradicition this number cannot be computed.
@@sataincsushipowerCOUNT THE CONTRADICTION AS A HALF. THE CONTRADICTORY ONE IS ONLY ONE PROGRAM OUT OF QUADRILLIONS AND QUADRILLIONS SO IT WON'T AFFECT THE ESTIMATE FOR OMEGA BY THAT MUCH IF YOU DON'T COUNT IT. I AM EXCITED TO SEE IF YOU MATH NERDS CRACK IT ONE DAY!
If you Like this video and topic, you should DEFINETLY go and buy yourself a copy of Gregory Chaitin's book - "Meta Math". It is an amazing book for math and computer nerds in general, but covers the story behind the exploration of Omega coming straight from the man himself, and gives insight into his thought process on discovery and knowledge.
This is all theoretical though. Because between at the boundary of halting programs, there lie the busy beavers. I.e. program of length n that runs the largest possible number of steps before halting. The number of steps a busy beaver runs before stopping, BB(n), is finite but absolutely insanely humongous - because in some way, it is the largest numbers that you can ever describe if you were the cleverest person. So even if you knew Omega, you would need to wait an almost indescribably long time before the scale tips over, way, way, unimaginably larger than age of the universe or anything we can describe easily.
There is a better and simpler number than Omega that has the same properties described here in this video. 1. List all programs. Not just n bits, btw, list all of them. 2. Construct a binary number whose kth digit is 0 if the kth program in your list halts, otherwise 1. It has the same properties as Omega (i.e. it exists, not compressible, not knowable etc.), and you don't need to go through hoops to prove that it solves all the open questions.
Nice one. But if I understand it correctly, your number wouldn't be totally random. Since most programs halt, you could easily win money by betting that each bit is a 0. The weird property of Omega is that it's definable-but-random.
@@AllAnglesMath Change the construction slightly then. 1. write a list of all halting programs in lexicographical order (list H) and do the same for all non-halting programs (list NH) 2. begin your decimal expansion of the constant starting at "0." 3. randomly choose between the 2 lists 4. if you chose list H, concatenate 1 to your number, otherwise concatenate 0. You can then map each bit in the number: 1. note the value of b_n 2. counting the number of b_n' (0 < n' < n) that match b_n (call this i_n) 3. then b_n is mapped to the i_n'th entry list H if b_n is 1, otherwise it's mapped to the i_n'th entry of list NH This results in a number with the same properties as OP described (trivially tells you whether a program halts or not), but with added randomness. Also since there are a countably infinite number of both halting and non-halting programs, saying "most programs halt" is incorrect. You can easily take any haling program and make it non-halting by adding a no-op infinite loop at the start of the program. Since there are a countable infinity of both, you can say (in some sense) that there are the same number of both types since you can always pair a program of one class to a program of the other class.
Great video, very well explained; the topic choice is perfect and carries a nice philosophical thought at the end, "I compress; therefore, I understand." is my favorite line. Btw I think there is a mistake at 10:36 since a perfect number equals HALF the sum of its divisors, not twice (actually, quite a bummer that it's not twice the sum, as that would make the problem of proving that an odd one doesn't exist pretty easy lol). Also, happy birthday to your dad. Maybe he can wish for the first 2^75 digits of omega as he blows out the candles on the birthday cake.
Good video! I'm seeing quite a few people questioning the reasoning and results of the last section of the video. While I'm certainly no expert I wanted to give some notes on where this video is skipping over details (some I think are a bit crucial). This isn't to discredit the video! I understand that some simplifications must occur so the video is accessible: 1. If we actually allow all binary sequences to define a program and add 1/2^k whenever that program halts, notice that this number can be as large as n, when considering just the sequences of length n. This number therefore isn't a probability. I would urge watchers to think about how you might actually describe the probability over an infinite sequence of options. The answer is to define a measure, which is where the 1/2^k thing comes from. 2. The only reason the 1/2^k thing works is because the constant is defined with respect to a *prefix-free*, *universal* turing machine. You might think of this as the 'programming language', which leads to the different values of omega, but this language has restrictions, namely that if one program p halts, then any program which has p as a prefix (is just p with some extra characters added on) then this program *cannot* halt. With this restriction, and this restriction only, the 1/2^k computation step makes sense, (what would that mean if these values summed more than 1, how would we know a prefix has contributed?) 3. The way the 'simulate all programs' step is animated wouldnt work, because we would have to execute a countably infinite set of '1st steps' before returning to the 2nd step of the first program. The solution here is to use a diagonal approach, only executing the xth step of the yth program once all previous programs have computed at least the x+1th step. (Search dovetailing on wikipedia and the subsection on infinite sequences if confused) I found this set of slides helpful for further reading: Search for 'Computation and Thermodynamics - UCR Math' Again to reiterate - I liked the video! But just wanted to add more detail for eager viewers looking to better understand the concept.
Hi everyone,
I'm here to express my extreme gratitude for the amazing comments. We're clearly blessed with a cool and wholesome community. You all rock!
I can tell you that my dad was extremely moved by all of your wishes. He asked me to convey this message, straight from him to all of you:
"
I want to thank you all for the many birthday wishes. It is an exceptional and unexpected gift.
Also, my heart warms up when I see your appreciation for the work of my son.
I would like to complement his motto 'keep learning' with mine: 'keep teaching'.
Knowledge has this peculiar property that the more of it you give away, the more of it you have left.
Have a goof life.
"
BTW, we won't be able to solve *all* maths problems with Omega because Omega has no information about programs that have access to omega. This is the hierarchy of hyper computation or something like that, and it's really neat. But yes realistically all problems we care about are problems about programs that don't have access to omega
Well that is why omega is uncomputable, if it could be computed, we’d have that problem, we also actually know it’s irrational, because if it was rational it would be computable
@@ianweckhorst3200It’s even transcendental, as all algebraic numbers are computable.
Happy birthday to your Dad from Boston! 75 is a big one, congratulations!
Happy Birthday, All Angles's Dad!
I too am a software engineer. I have an 18 month old little boy. I think there are many, ways in which I could succeed as a parent, but if in two decades time, my boy is making RUclips videos (or whatever has replaced them) which challenge me to think and learn in the same way that your boy has done for me today, I will feel super proud of what he has achieved. And if he traces any part of his love of learning and his willingness to challenge himself back to me, then I in turn will trace it back to videos like this one that have helped and inspired me. Thank you so much for helping to create a world filled with the passion and curiosity
Thank you so much for that uplifting comment. Let's keep spreading knowledge!
Doesn't omega depend on the system being used? So it's not really a constant like pi, unless you specify the system you are working in (some specific lambda calculus, for example)
You're right, the exact value will depend heavily on all the choices we make along the way. I didn't want to get bogged down in the details, so I skipped over it. But well spotted.
I was wondering about this, neat to hear.
It'd be fun to try and calculate a few trivial bits of omega :)
Happy cake day for you dad 🎉
found the redditor
Happy anniversary from Spain, and thank you for inspiring your son!! We absolutely love his incredible videos.
Muchas gracias!
Creía totalmente que sería el único español aquí. Me alegra saber que no.
I think that to compute the number to a certain accuracy would require you to know the answers to all the problems it could solve, so it's less of an oracle and more of a compression algorithm. And an optimal one too, since it's not compressible further!
Thank you sir for making my day! This video was absolutely incredible. Happy birthday to your Dad from Düsseldorf, Germany!
Danke schön!
I just turned 75 too, and I'm also a Dad, so happy birthday to both us Dads!
I found an interesting pattern for the composites of Euler's quadratic. Perhaps you can find it too.
Congratulations on your recent birthday!
Fijne verjaardag vake! (Best wishes from Belgium)
Happy birthday from Marseilles, France, from a fellow software engineer. :))
The halting problem is decidable for finite deterministic systems, so it's theoretically possible to calculate omega for some systems. Unfortunately, any problem worth solving with omega would require massive amounts of computational power
Happy birthday from France!
Happy 75th birthday from the Blue ridge Mountains of North Carolina! May it and the days that follow be wonderful 💕
Happiness and many more years of life for your dad!
From Brazil!
Obrigado!
HBD to your dad from Korea!
Happy birthday to your dad from Texas! Congratulations on the big 75!
This was one of the best videos i have watched in the couple of weeks on RUclips, thank you!
Happy 75th birthday! Thank you for having such a great son! From Brazil!
Happy birthday to your dad!!
Happy birthday from France !! Take care of yourself, hoping everything's going great !
Happy Birthday from Indonesia
Happy Birthday to your dad from Brazil!
Happy birthday mr. Dad, from central Michigan.
Happy Birthday to your dad from India 🎊
Today is my mom's birthday too
Thank you, and happy birthday to your mother. Wish her all the best from us!
@@AllAnglesMath ❤️
Happy birthday to your dad from india🎉
Happy Birthday from Columbus, Ohio, USA! ❤
Oh Ω, not ω. That's not so surprising, but I'll watch anyway, 😀. Chaitin's work is always worth revisiting!
Oh, it's my dad's birthday today as well. I think he's 76, I always forget whether it's my mum or dad was born in 48 or 49.
What a nice coincidence. :) Happy b'day to both our dads.
Our best wishes to your dad as well!
@@AllAnglesMath He was 75 as well. :) Had a big bbq with the grandkids in the evening. Was really good!
Happy birthday to your dad from Italy!
Happy Birthday from South Florida!
Happy birthday from Egypt 🎉
Happy birthday to your dad! Mine will be 75 next week!
Thanks, and send your dad our best wishes in turn!
Happy birthday to your Dad from Quebec, Canada!
Happy birthday from Houston, TX!
happy birthday from Canada!
Happy Birthday from Chicago...
Belated happy birthday to your Dad from France. Good work getting your (now grown) child interested enough in these topics that now they are making videos for the engineers like me who didn't get to learn the spicy bits of the math.
Happy birthday from New Zealand
Happy birthday to your dad from Poland!
By the way, I believe even if we knew the value of omega, running all possible programs at once could be tricky - at a trillion in, we would still be looking at programs that print random constants
You're right, the entire idea of omega is mostly theoretical, not very practical.
HAPPY BIRTHDAY, MR. ANGLES! from Atlanta, USA
Thanks! Would be weird if that were really our last name. Like the Paul Simon song: You can call me All 😉
Happy (3 * 5^2)-th birthday to your Dad from Poland!🎉
Yup, that seems to work out to 75. Thanks!
A big happy birthday to your Dad from another software engineer in the beautiful Wicklow hills of Ireland.
happy birthday for your dad from Turkey 🎉
Such a beautiful country. Thanks!
Best wishes from Poland - Cracow !
Happy birthday padre! Blessings from Colorado!
Muchas thanks!
Happy Birthday to your Dad from the panhandle of Florida
Woah we are very close. I'm from the panhandle of Texas. Happy birthday to you, All Angle's dad!
My country has no panhandle, but we do have some funky bits flying off in the north.
Hey! This is also my mother's birthday
Congratulations to your mother!
Happy birthday from South Africa!❤ 2:15
Happy birthday from Russia🎉
About hauling problem - had anyone proved that it's the same number for any Turing-complete language? Cuz if it's not true, we could state the opposite problem - choose number between 0 and 1. For said number construct a programming language in a way that it's hauling constant would be this arbitrary number.
Happy birthday from Berlin!
I like the Idee of omega. Happy birthday from Switzerland to your father.
Thank you! Switzerland is one of our favorite hiking countries.
happy bday from the southern USA! great video!
A key step in our journey to figuring out if a program halts or not is using omega-n, where n is the "length" of our program and then used to take the first n digits of omega.
A few questions I've been thinking about as a result of this and my thoughts (feel free to chime in):
Questions -
Is it possible that omega has less than n digits? I.e. does omega have infinitely many digits?
Does a random number have to have infinitely many digits?
Why is omega "random"?
Thoughts -
From the video, a key point is that a number is random if (and only if?) it is incompressible. Thus, if a number is not random, we could write a program to write out its digits. If it is random, we could not do that. So, if a number has finitely many digits, we should be able to write a program with finitely many steps to write out the digits of that number. So a random number must have infinitely many digits.
Secondly, Turing proved through the halting problem that we can't have a program determine whether all programs will halt or not. Thus, we can't compress the probability that a random program halts, and so omega must be random.
Since omega is random, it must have infinitely many digits, meaning we could always take the first n digits for arbitrary n.
I'm little shaky on that second jump. Let me know if I'm missing something or can think about it in a different way.
Great video and happy birthday to dad!
Happy birthday to your dad!
Happy birthday to your dad from the east of Spain!
Gracias!
Hi, nice explanation video !
I'm currently working on a video on the exact same subject and I have some remarks, especially on the part "how the oracle works":
The Omega that you describe in your video is not defined on a prefix computing model which mean that it is possible that your Omega can be greater than 1 for example if the 2 programs of length 1 (the ones encoded by 0 and 1) both halts they will both add a wheight of 0.5 which will make the total already equals to 1. And by your defenition that would mean that even if there are only thoses two programs which halts the probability of any programs to halts will be 1 (Omegas can be seen as a probability but not in a direct way) .
At 17:48 you said that you work only on the shorts programs which means that you can only compute a lower bound of that omega because there are programs on size greater than n that can have an impact of the first bits. To do so you have to not work only on the programs of size n but all programs of your computing model. Since there is an infinity of programs you can't do the trick of "I do one step of each programs and I start again" because that would mean that you can only performs at most one step of each program, to get over this you can use what we call a "Dovetailling" which works like the bijection between N and N^2.
I know i am being really pedantic about theses little details but as I said, this is a nice explanation video that probably make the whole concept understandable for a person that don't know about it already and all of thoses details can take a while to explain and might hurt your audience retention so keep it that way 😄
Thanks for the interesting feedback. As soon as your video is ready, feel free to post a link here. Looking forward to learning more!
Happy birthday from Baltimore!
Happy birthday to your dad from France :)
happy birthday to your dad from minnesota 🎉
Happy Birthday to your Dad from Tennessee
Happy birthday to a lucky father, from the Sonoran Desert
Best wishes to your dad from Tennessee! (And California)
Happy birthday from Duluth Minnesota!
Happy Birthday from New Mexico.
Just to clarify: the reason why we can't know omega is not because you can't write it down, but rather that it is impossible to *prove* that that number is indeed omega. Similar to how it's impossible to prove the continuum hypothesis, or gödel's incompleteness theorem
No - if we could write it down (compute it with finite means) then there would be a halting function. We might not be able to prove that it is actually the halting function, but it would work all the same.
Since the existence of the halting function leads to contradicition this number cannot be computed.
@@sataincsushipowerCOUNT THE CONTRADICTION AS A HALF. THE CONTRADICTORY ONE IS ONLY ONE PROGRAM OUT OF QUADRILLIONS AND QUADRILLIONS SO IT WON'T AFFECT THE ESTIMATE FOR OMEGA BY THAT MUCH IF YOU DON'T COUNT IT. I AM EXCITED TO SEE IF YOU MATH NERDS CRACK IT ONE DAY!
If you Like this video and topic, you should DEFINETLY go and buy yourself a copy of Gregory Chaitin's book - "Meta Math".
It is an amazing book for math and computer nerds in general, but covers the story behind the exploration of Omega coming straight from the man himself, and gives insight into his thought process on discovery and knowledge.
Thanks for the tip!
Happy birthday to you dad - he must be very proud of you!
He is, and it's mutual. Thanks!
Happy birthday to your dad from Oregon!
happy birthday dad, from koper, slovenia
Happy B birthday from Antibes in France
I have fond memories of walking along the Cap d'Antibes. Thanks for the wishes!
happy 75th from Luxembourg! 🎉
Happy birthday from Canada!
Happy birthday!
happy birthday from Cochrane Canada
This is all theoretical though.
Because between at the boundary of halting programs, there lie the busy beavers. I.e. program of length n that runs the largest possible number of steps before halting.
The number of steps a busy beaver runs before stopping, BB(n), is finite but absolutely insanely humongous - because in some way, it is the largest numbers that you can ever describe if you were the cleverest person.
So even if you knew Omega, you would need to wait an almost indescribably long time before the scale tips over, way, way, unimaginably larger than age of the universe or anything we can describe easily.
Agreed. Omega is purely theoretical in many ways, but still fun to think about.
HB from Boulder, CO, USA! coder dads are important!
happy birthday from sweden
Happy birthday from Germany ❤
Happy birthday from Finland, Angle Dad
HB to your dad from France ;)
Merci beaucoup
Happy birthday from the Americas
Happy b-day from belgium!
Dankjewel / merci bien!
@@AllAnglesMath geen probleem/no problem
Happy birthday to your Dad from Dunoon, Scotland. I will have a wee dram to toast you!
Cheers!
Happy birthday from London and a 68 year old retired software engineer.
Happy birthday from Russia!
Happy birthday from USA!
Happy birthday from Ukraine. I'm software engineer as well, love math
Happy Birthday from Hawaii!!🥳🥳🥳
Happy birthday to your dad from canada :D
There is a better and simpler number than Omega that has the same properties described here in this video.
1. List all programs. Not just n bits, btw, list all of them.
2. Construct a binary number whose kth digit is 0 if the kth program in your list halts, otherwise 1.
It has the same properties as Omega (i.e. it exists, not compressible, not knowable etc.), and you don't need to go through hoops to prove that it solves all the open questions.
Nice one. But if I understand it correctly, your number wouldn't be totally random. Since most programs halt, you could easily win money by betting that each bit is a 0. The weird property of Omega is that it's definable-but-random.
@@AllAnglesMath Change the construction slightly then.
1. write a list of all halting programs in lexicographical order (list H) and do the same for all non-halting programs (list NH)
2. begin your decimal expansion of the constant starting at "0."
3. randomly choose between the 2 lists
4. if you chose list H, concatenate 1 to your number, otherwise concatenate 0.
You can then map each bit in the number:
1. note the value of b_n
2. counting the number of b_n' (0 < n' < n) that match b_n (call this i_n)
3. then b_n is mapped to the i_n'th entry list H if b_n is 1, otherwise it's mapped to the i_n'th entry of list NH
This results in a number with the same properties as OP described (trivially tells you whether a program halts or not), but with added randomness.
Also since there are a countably infinite number of both halting and non-halting programs, saying "most programs halt" is incorrect. You can easily take any haling program and make it non-halting by adding a no-op infinite loop at the start of the program. Since there are a countable infinity of both, you can say (in some sense) that there are the same number of both types since you can always pair a program of one class to a program of the other class.
Happy Birthday to your dad!
Great video, very well explained; the topic choice is perfect and carries a nice philosophical thought at the end, "I compress; therefore, I understand." is my favorite line. Btw I think there is a mistake at 10:36 since a perfect number equals HALF the sum of its divisors, not twice (actually, quite a bummer that it's not twice the sum, as that would make the problem of proving that an odd one doesn't exist pretty easy lol). Also, happy birthday to your dad. Maybe he can wish for the first 2^75 digits of omega as he blows out the candles on the birthday cake.
You're absolutely right about the perfect numbers. My mistake.
Good video!
I'm seeing quite a few people questioning the reasoning and results of the last section of the video.
While I'm certainly no expert I wanted to give some notes on where this video is skipping over details (some I think are a bit crucial). This isn't to discredit the video! I understand that some simplifications must occur so the video is accessible:
1. If we actually allow all binary sequences to define a program and add 1/2^k whenever that program halts, notice that this number can be as large as n, when considering just the sequences of length n.
This number therefore isn't a probability. I would urge watchers to think about how you might actually describe the probability over an infinite sequence of options. The answer is to define a measure, which is where the 1/2^k thing comes from.
2. The only reason the 1/2^k thing works is because the constant is defined with respect to a *prefix-free*, *universal* turing machine. You might think of this as the 'programming language', which leads to the different values of omega, but this language has restrictions, namely that if one program p halts, then any program which has p as a prefix (is just p with some extra characters added on) then this program *cannot* halt.
With this restriction, and this restriction only, the 1/2^k computation step makes sense, (what would that mean if these values summed more than 1, how would we know a prefix has contributed?)
3. The way the 'simulate all programs' step is animated wouldnt work, because we would have to execute a countably infinite set of '1st steps' before returning to the 2nd step of the first program. The solution here is to use a diagonal approach, only executing the xth step of the yth program once all previous programs have computed at least the x+1th step. (Search dovetailing on wikipedia and the subsection on infinite sequences if confused)
I found this set of slides helpful for further reading: Search for 'Computation and Thermodynamics - UCR Math'
Again to reiterate - I liked the video! But just wanted to add more detail for eager viewers looking to better understand the concept.
Thank you for clarifying! I must admit that I didn't catch all those details myself.
Happy birthday to papa from England
Happy birthday from Italy
Happy birthday to your father from Leuven!
Mijn geboortestad!
Happy Birthday from Washington State.
Proficiat!