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
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 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.
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.
To better understand why we can't solve for the first n bits of Omega: Say you have a program g of size n bits that you need to determine if it halts or not. This requires knowing Omega*, or Omega truncated to n-bits. Calculating Omega* requires knowing precisely how many programs of n bits or less halt and how many don't halt. Since g has n bits or less, you need to know if g halts or not to construct Omega*. As a result, Omega* is not a predictive oracle, but rather just a description of programs studied so far.
But probability does not mean exact fraction. Even if you know that a random program of length 100 halts with probability 0.19 and you've found 19 halting programs, it does not mean that there are no more halting programs of length 100.
This is a bad example, because since there are finitely many programs of fixed length, you actually can conclude that the share in the probability from an individual program is positive. If you look at the formulation in the problem, this is the property that they use to be able to do it even with an approximation. (There is another unclear hole that comes from their simplification, of course.)
Question: In the sequence 1,0,1,0,1,0,1,0,1,0 how can it be so that you can predict the next number? In my view, it could well be another zero. I'd guess that even if that sequence repeated 1 billion times, you still couldn't be certain of the next number. Therefore, I don't see how random can be indisputably detected. Either you have all of the facts or you don't. If you don't, you don't. Presuming them doesn't make a fact.
That's a fair point. Technically speaking, you can never know the next digit in any sequence. I guess in this example I'm relying more on human pattern matching than on philosophical certainty.
This halting problem is similar to that of solving for division by 0 based on the fraction N/D where N != 0 for all N over 0. We are commonly taught that division by 0 is undefined. Yet, I beg to differ on that. I do not think of it as being undefined. I think of it as being well defined. This series of expressions can express that it is well defined. { ..., -5/0, -4/0, -3/0, -2/0, -1/0, 1/0, 2/0, 3/0, 4/0, 5/0, ... } In the above sequence 0/0 is not a part of this set as 0/0 is a special case. With N being the Numerator or Dividend, and D being the Denominator or Divisor we have to understand what division actually is. We are taught that division is the inverse of multiplication since it has the ability to undo multiplication. This is true, but we need to dive deeper into its base construct or properties. What is multiplication? It is repeated addition. Since division is considered to be the inverse of Repeated Addition what is the Inverse of Addition? We can state that it is Subtraction. But what exactly is subtraction? Subtraction is still addition, except that it implies the addition via the Additive Inverse. We will need these few basic arithmetic properties to better understand this. Additive Identity: A+0 == 0+A = A And from above we can also see the Commutative Property: A + B = B + A. Multiplicative Identity: A * 1 = A. Multiplicative Inverse Identity: A * -1 or -A * 1 = -A Additive Inverse: A - A = 0. Multiplicative Cancelation: A * 0 = 0. From these we can construct Subtraction in terms of Addition by: A - B ==> A + (-B) Now we can define Division in terms of Repeated Subtraction or Addition. When we define division in terms of repeated subtraction, we are taking the denominator and subtracting it from its numerator. Then we are testing that temporary result to see how it compares to or its relationship with the Numerator. Here the numerator and denominator remain constant through the entire process. This temporary result continues to decrease until some type of criteria is met and depending on the state of its value and relation to both the numerator and denominator as well as a choice of action to either return with both a quotient and remainder (integer division) or to continue to produce a decimal or fractional value. The remainder is the minimal integer value that is left over that is in the range of: 0 < r < d. If r = 0 then we have perfect integer division, if r = d, we can subtract one more time and we will end up with 0 on the next iteration and thus we will have perfect integer division, otherwise we will either have an integer remainder terminating the loop or we continue to give us decimal (fractional) values. If we use the above steps or procedures (algorithm) to compute division by 0. We do not need to initially test if the denominator is 0. We can perform the first subtraction always. After that first subtraction we can then test to see if our accumulating temporary result (the remainder) is equal to the numerator or dividend. If these two are equal after the very first subtraction, then we know that we encountered the application of the Additive Identity: A + 0 = A, or A - 0 = A. We also know at this point that the loop of repeated subtraction (division(s)) will result in an infinite loop. The actual quotient or result of the division is an integral counter of how many times we performed the subtraction. Initially this quotient will be set to 0, and it will be incremented to 1 after the initial subtraction AND after the test to see if the result (remainder) and the numerator are equal. If the test fails, then we increment and continue into the loop. If the test is true, then we just set our quotient to Infinity and return early and in this case, the remainder will also be the numerator. Think of it like this using the simplest case from this expression: 1/0 1 -0 --- 1 -0 --- 1 ... If we continue with this repeated subtraction or addition of 0, the numerator will never change, it will never be reduced. The incremental counter (quotient) will extend towards infinity. We can represent this with the following summation for All N where N != 0. The summation from i = 0 to +infinity of: (N + 0)i In other word it would look like this where N = 1 in the base case: 1 + 0 + 0 + 0 + 0 + ... OR 1 - 0 - 0 - 0 - 0 - ... The above expressions, summations, sequences are exactly what Division by 0 is. The reason I left out 0/0 in the initial series at the beginning is because 0/0 is the Indeterminate Form, it is a special case because it is the origin or the zero vector (0,0). We can treat all divisions (fractional values) as a coordinate pair. We can treat them as N/D (numerator/denominator) as being the pair {denominator / numerator} If we take the fraction 0/1 we can see the result as being 0, and this has the coordinate pair (1,0) which is the vector that goes from the origin (0,0) to the point (1,0) If take this unitary vector and subtract two from it: 1-2 = (-1) arithmetically, but through vector component by: + + = this two-step horizontal translation of the vector in the opposing direction has the same exact result of taking the vector and rotating it by +/- 180 degrees or PI radians. So, what is division by then? Again using 1 as the simple base case: We know that 0/1 = 0 and this fractions reciprocal is 1/0. We can treat this again as a coordinate pair, vector: 1/0 ==> If we take the vector and rotate it by 90 degrees or PI/2 radians we end up with the vector Here these two vectors and are perpendicular, orthogonal to each other. This is the same exact thing as taking the vector and multiplying it by i. Taking and multiplying it by i gives: The only difference here is rotating by 90 degrees or PI/2 radians is keeping the vector within the XY plane, where multiplying it by i translates it into the Complex plane. How does this work? Well, the angle that is generated by the rotation is equally proportional to the fractional values and their relationships within the division. This fractional value is a slope or a gradient within y = mx+b where b = 0 and m is the slope, rise/run: m = deltaY/deltaX = sin(t)/cos(t) = tan(t). What's tan(90)? Please do not state undefined, that's the same argument of division by 0 being undefined. We can express tan(90) as being: sin(90)/cos(90) = 1/0 which gives us the vector or . Division by 0 or repeated addition or subtraction by 0 indefinitely is Vertical Slope, it is perpendicular to the horizontal. It is self-Identity. There are two forms of self-identity. The first being y = x where b = 0 and m = 1. Which is the diagonal line through XY with an angle of 45 degrees. The other is A/0 where A != 0. Because this is the same as tan(90) which is the same as the summation of repeatedly adding or subtracting 0 to itself which is preserved through Additive Identity. Division by 0 for me is not "undefined" it is actually well defined because I JUST DEFINED IT! Now when we look at the evaluation or the result of division by 0, it can be stated that it's Not a Number because it tends towards infinity Only When AND Where the Quotient is of Concern because the Quotient itself becomes Infinity. When we don't concern ourselves with the evaluation or result of the operation, but we concern ourselves with the properties and relationship it has between the Operands the imposed Operator. It is well defined and well behaved. Due to this perspective of observation, I do not like the idea of stating it is undefined. I do not mind stating that it is ambiguous. And yes, undefined and ambiguous are slightly related or almost synonymous, they are not the same and have different meanings and implications. Division by 0 is Verticality, it is Vertical Slope, it is Perpendicularity, it is Orthogonality, it is A Right Angle or a 90 Degree Rotation, it is the Multiplicative Identity of Some value A * i or A * sqrt(-1). That's division by 0. So, the halting problem, and other phenomena such a N vs NP, can be attributed to these properties. If we take the value 5 and divide it by 0, we end up having the following expression: 5 * sin(90)/cos(90) = 5 * tan(90) which when we take the vector and perform a 90-degree rotation onto it (division by 0) we end up with the vector or . This is where I like to express what we commonly call the set of all Reals as simply being the Horizontal Numbers and the set of Imaginaries as being the Vertical, Perpendicular or Orthogonal Numbers as they are Normal to the Reals or Horizontals and that their Intersection lies at , the zero vector, and that their Union is the set of Complex Numbers defined by a + bi, or (a, bi) which can be expressed as (cos(t), i * sin(t)). Instead of throwing around the idea that division by 0, tan(90), and vertical slope are "undefined", if we look at them intuitively, intelligently we can begin to better understand their properties and their behaviors based on their relationships with other values and the types of transformations that we can apply to them. Food for thought. I'm trying to challenge the way We tend to think about things.
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 RU-vid 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
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!
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 😄
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
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.
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!
