WHOOPS 1 isn't a prime. The computer would have stopped at (2+2), my bad! Thanks for pointing that out everyone :) I can be a bit ignorabimus sometimes.
Hehehe ahh yea, I'm imagining someone casting that spell on Crabbe and Goyle. Since they are already idiots... they'd be hilariously stupid. Actually half the plot of chamber of secrets could have been bypassed cause when Ron suggests tricking them into telling them what Malfoy knows, Hermione's response is something like, "not even they are that stupid". But if she had such a spell they wouldn't have had to spend half the semester brewing polyjuice.
there is its called "is Australia op?" ruclips.net/video/TrsaXzmqShM/видео.html also there is a "spider tier list": ruclips.net/video/lOfUZvOZ400/видео.html and "Optimizing the Snake Build": ruclips.net/video/bWOe2Znb74I/видео.html
Mark Daniel a Turing machine is a model for how a storage device, a table of instructions encoded into the storage device and a machine that follows the instructions to modify the data on that storage device based on those instructions. It’s a model that was proven to be able to solve any problem that’s solvable by a computer given enough time and storage. And it’s ideas like this that made computers possible in the first place
they might not of have a modern computer, but before electrical computers there was mechanical computing machines. then punch card computers with no screens.
An electrical system is a basic computer and the transistor is loosely based on the on/off switch on=1 off=0 vaccuum tube was the first automatic switching device at 1903 a solid thirty years before Turing made his machine then the transistor debuted in 1947 Turing made the first automatic sorting algorithm in a machine in 1936
@@markhaus no. the vacuum tube was the first step into modern computing. Turning made a sort function algorithm and had a mechanical machine sort using if thens cards until the sequence completed.
Seems a few people are either trolling or missing a fundamental detail of the particular proof. Hal is assumed to be a *general purpose* program that can be run on *any* input program and it always provides the correct answer. Because Hal is defined to work on all programs, it must be able to work on itself since Hal is, itself, a program. The thing I think a lot of people are missing is that this is a proof that the halting problem cannot be solved in the *general* case. To prove that the general case cannot be solved, you just need to find *one* counterexample. This says nothing about specific cases. There are plenty of specific cases where it is possible to identify if a program will halt. The existence of those cases does not invalidate the proof. The proof is simply telling us that there is no magic box that will work on every possible program. Basically, it means there isn't a magic shortcut for solving Goldbach and other problems.
thanks for your comment because the video doesn't explain this at all! Still, I don't know what this all has to do with a program that has to test all numbers to infinity (like the goldbach problem). Of coure, it runs forever.
@@Falkdr The "Goldbach solver" program will stop if it finds an even number that cannot be represented as 2 primes. So if you could run "Hal" with the goldback program as input and it returns that the program never halts, the goldbach conjecture is proven true. If "Hal" returns that the goldbach program does halt, that can only happen because the goldbach program found a contradiction - an even number that cannot be represented by two primes - and stopped, and you have proven the goldbach conjecture false.
@@uchian No, Hal would never return anything because it has to go through all the numbers that are, to test them (so infinite). You'll have to wait forever for the answer. It sounds Up&Atom was just asking "does Magic exist?". As far as we know, it doesn't, so there doesn't seem to be all to much behind this video.
@@Falkdr In the halting problem, 'Hal' does not run the program to determine whether it halts or not. It would determine it through some (unspecified) analysis of the instructions in the program that returns a yes or know answer as to whether the program halts or not. The proof discussed in the video means that the the "unspecified" bit of the above statement is mathematically impossible in the general case.
I got that, by unspecified you mean 'magic'. Its not that bold to set up an impossible claim and proof that it is impossible, imho. I don't think the 'halting problem' would've been huge riddle in modern days, back then it might have been a great analysis, though.
Studied this back in the 70s in Cambridge when the people who had known Turing were still lecturing. This video brought back some wonderful memories. Thanks. BTW the entire university computing service ran on an IBM 370/165 with 3 megabytes of RAM back then.
I remember in the good old days studying computer science and first hearing about "The halting problem" it seemed odd and trivial to me at first... that is because I didn't understand it, I mean... I didn't understand why it was such a big deal. The proof done by contradiction was brilliant ploy by Turing, I'll never forget how astonished that I actually got understood it on the first run-through (that rarely happens!)... but you made me feel sad for the way poor Hilbert was broken hearted in your animation... but, as you rightly pointed out, he does have his own space named after him, so there is that...
Hilbert KNEW about Gödel's Theorems, but rejected their conclusions, proving that even the most logical mind (Hilbert's) has an logical conclusion that it cannot accept. Even the King of Mathematical Reasoning had his weak points.
“Will I ever stop being a disappointment to my family?” A’ight Jade, I’m gonna need you to stop recording me while I’m “working”, we’ve talked about this.
It’s amazing how smart and ahead of his time Turing was. I wonder what was his thought process to even fathom such concepts and ideas in an era where computing was still primitive in comparison.
Using the halting problem, we can answer the original problems that Hilbert posed, and not with resounding yeses. "Is mathematics complete?" If mathematics was complete, a computer could prove everything that was true, answering all problems, because it could return a 1 for true and a 0 for if it wasn't true, but a computer cannot solve all problems, so mathematics must be incomplete. Is mathematics consistent? Again, if mathematics could be counted on to be consistent, computers should not be halted by the halting problem, because the math used by computers wouldn't be able to create a paradox. "Is mathematics decidable?" Again, if mathematics were decidable, we would be able to create a program that could take that method to determine if a statement was true or not, so all three of Hilbert's questions were answered decidably "no" by Turing's computers.
In fact, a Turing machine has been created with, I believe, 29 states that halts if and only if the Goldbach conjecture is false. The step function S is the maximum number of steps a Turing machine can run before it must either halt or run forever. So, if you ran the machine for S(29) steps and it didn't halt, you'd know the conjecture was true! Of course, the halting problem proves that S cannot be computed by a Turing machine, so we can't actually know what S(29) is. However, we do know that S(17) is greater than *Graham's number*, so the age of the universe isn't even pocket change compared to it.
Turing was inspired by Gödel. I was disappointed she mentioned Hilbert, but didn't give Gödel credit. Still, I can see making the decision to keep the video under ten minutes.
Scott Busby: And that's no coincidence. Turing's Halting Problem, Gödels incompleteness theorems and Church's Lambda Calculus are functionally equivalent. You can convert one model into all of the others.
Turings halting problem was a rephrasing of gödels incompleteness theorem.. gödel was the first one to see it and the real genius.. Turing was a big fan of gödel btw.. this video is misleading!
I really love your way of explaining complex knowledge/theorms in very simple words along with cool animations. 😍😍 I always hated thoery of computation, but now I don't 😊
What if we put the Barrie program on a quantum computer where it is potentially both running and halting simultaneously, in a state of superposition. I think I have solved it. ;-) Great videos, keep them coming.
Funny that you should say that actually, but it turns out that not even quantum computers can solve the halting problem and that the proof for it has some major implications throughout physics and maths: www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/
@@shadiester I carefully and slowly read the article you posted and if I'm honest my understanding of it far from complete. If my view is correct, without entanglement the proof would remain unsolved. Cheers
It's a great problem. I remember I loved the proof when I first heard about it. I also really like another problem that can't be solved called Post Correspondence Problem and that's because while the halting problem at least sounds like something really hard to do, PCP is a problem that seems like something easy. Something we can do by hand when given an example input. And how the hell can there be no step by step method solving something like that for any input, given unlimited amount of time and resources? It still blows my mind that there isn't, but I've seen the proof. But way more complicated than this one. And PCP can be applied to proving a bunch of other things aren't decidable. Darn, the laws of our universe are harsh! It's not enough we don't know the answers to so many things and going to keep trying to answer for thousands of years to come, but we already know there are things we'll never answer! That's just depressing!
Greetings from a brazilian fan, i love your channel! Looking forward to videos about the mathematics behind machine learning (backpropagation derivatives, error function parameters, random minibatches, what is matrix calculus and why GPU's parallel process is a great solution for this, etc) can't wait to see them =) sorry my bad english
@@DavidFMayerPhD But consider, in a quantum system, superposition gives 'Hal' a third option to return, where it is both running and halted, simultaneously.
Bruce Lee said in the Tao of Jeet Kune Do, "The solution to any problem is understanding it. Once you understand the problem, the problem dissolves." What that means to me is, if a problem doesn't have a solution, the reason is because we don't fully understand it yet.
I've had programming ide's pop up a warning saying a subroutine would run forever. its more along the lines of it not having something that would end the loop rather than it never finding an answer. you would need a program that predicts the future in order to know if it would halt.
Because of you, I finally somehow understood the halting problem. The recursive representations feed onto itself of your video did it - brilliant I believe. Maybe a way out of the halting problem is the impossibility of feeding back a decider into itself, an ultimate decider that cannot be fed back into the programs - beyond the Turing machines. At that level, though it can take in programs and make a decision, it cannot be called program or computer, a totally different category. What is that thing, which is not a program itself, that could take in programs and evaluate them? Or we have a third option, we endow Barrie a recognition that it itself is inputted into the same evaluation, so Barrie could halt, loop or return 'not like this, not like this, we will run into a paradox.'
The halting problem exists because of the nature of the universe itself. The halting problem essentially asks a computer to predict the future without having to simulate it first, and that's not how the this particular universe works. It's not a problem restricted to computers.
Hi mam I am an Computer science engineer and from last 2 years finding a perfect video for Halting Problem... write now I can say that "I got that perfect video"..
Hi there, I was thinking of starting my own channel and I like this kind of topic. But when I saw the video I think you could have an error on it. I should check on the original paper, but I think you are missing something important which is the input of the input. For instance, in 4:19 you are talking about the program Randy, the program Randy could Stop or Run forever without having into account the input of Randy, which implies that Randy parameters are not important on if the program Randy will run forever or not. But you have programs that its input decides if they will run Foverer or not. When you state the proof, your say in 4:45: You said that Halt receives Halt as an Input, in an explicit way is: The program HALT receives as Input a HALT program. But you are missing one parameter there, which is the Input of the Input, Halt can say if the Input will stop or not because The input program could receive inputs that makes HALT or NOT. I know its confusing, but maybe I Skipping something. Thanks
I initially got confused about the same thing. Took me a while to realize what I have missed. The key is at 4:08. HAL can answer the question: will a program X with input Y halt or not? So HAL has 2 inputs, the program (X) and the input to that program (Y). BARRIE is different, it only takes one input, a program (X). It then asks the question: what would HAL answer given program X with input X, and then does the opposite. That is, the input to X is X itself.
@@AdrianTaga ok but if X is a program that needs an input Y to run, X is not a valid input for X itself, at a minimum it's not complete, there has to be a Y input, of the appropriate domain, at the end of the chain.
@titusfx not quite, at 4:45 it is BARRIE not Halt that receives itself as input. (And unlike Halt, Barrie only takes one input.) Also, Randy would later similarly received itself as input, that's why she wrote "Randy(Randy)". At 4:19 it is merely shown that the "X" that Barrie receives as input will in this case be Randy, then Barrie will work on it as in the description: "Do the opposite of what Hal predicts *about program X and input X."* :-B
@@AdrianTaga as @Daniele Messina says, Barrier will have the input X, which is Barrier, so the input X will need another input (and that will be forever if you just put Barrier as argument). I have got this doubt for years, since University. And I have the same problem understanding the paper and this exact point. I could be skipping something...
@@irrelevant_noob What you said is correct. But that's not what I'm trying to say (I wrote about Halt, trying to "expand" Barrier). What you said about randy is correct. So, instead of thinking on Randy, try to change Randy with Barrier, which is what Turing did. Barrier will have the input X, which is Barrier, so the input X will need another input (why? Because is Barrie, so it needs another input, which that input can not be, Barrier, because it will need another one, and so on, until the infinity)
The proof idea is similar to Russell’s paradox where you construct “the set of all sets that don’t contain itself as an element” (after arguing it’s neither empty nor the “set of all sets”), and then ask “does this set contain itself as an element?”.
The halting problem doesn't just mean there are problems "we" can't solve. It means there are problems that are impossible to solve - by anything - ever. It means omniscience is impossible.
your conclusion isn't necessarily true. while it's true that there are problems that we cannot in principle find a solution for, that doesn't mean the solution cannot be known.so for example, i (imagine i am a magical being outside of time) could know all the digits of PI, but you, in your finite universe, because you don't have infinite energy and time, cannot determine them. you have to stop at some point. then there are problems that have no solution in principle. those don't disprove omniscience. this would be like saying "god cannot create a triangle with 4 sides" and say "ha! no omnipotence!"
No. That's my point. It proves that nothing - not even a magical superbeing outside of time and space - could know everything. By the way, a magical being outside of time is, by definition, impossible. For something to exist, it has to be in time and space.
Hmmmm... "For something to exist, it has to be in time and space." What about 1+1=2? That and all the rest of math, can math not exist without space time?
Math is a concept. Concepts aren't real in any material sense - they require an intelligent being to conceive of them. If you're arguing that god is merely a concept, I agree. But that doesn't mean he actually exists as a real being. Fairies are concepts too - they also don't exist as "real beings". I think it's about time we grew up and accepted that magical beings don't actually exist.
What about the multi-verse, our space-time doesn't connect to the whole thing otherwise they wouldn't talk about universes colliding and popping like bubbles. So IF that theory is true then not only is there something outside our space time, pretty much everything is out there.
the contradiction only happens when self referencing loops are involved, but most functions we use in real life are not self referencing, being able to decide if they halt or not are still very valuable, has anyone done any work on that?
Every loop is self-referencing by its very nature. A loop is equivalent to a function that calls itself recursively, with varying inputs. The program can be self-referencing in a very obfuscated non-obvious way. There is plenty of theoretical research that goes into this. In practice, the halting problem and its cousins come up in areas where self-referencing is desired behavior. For example, in compilers. It would be rather useless to have a compiler that can't even compile itself.
There's a simple solution to the problem of Barry. Make him time independent. What I mean to say is that the computer will execute code in order, that is, it will take time between executions. If you run all the code for Barry simultaneously, you can achieve a superposition of Barry running and staying still. It's similar to what happens when you connect your camera via analog to a tv and then point it at the tv. In that sense, it is looking at itself
@@upandatom 'G0LDbAcH wuz a L00zer' had me chuckling :)) Only proves that even the smarty-pants computer that can solve the halting problem would still struggle with grammar :p
The Turing Problem reminds me of the thought experiment you did during your free will video. Where a computer computes whether a person will be invited but can't tell them without changing the result.
I think the halting problem has a fundamental problem, which makes it much less general than it might appear. Now don't get me wrong, given its assumptions the logic is perfectly valid - but that's where the problem lies, in its assumptions. The only possible return values of our hypothetical decider-program are true and false. What happens if we add a third option: self-referential The only time the halting problem occurs, is when the algorithm is fed with a modified version of itself. So what happens if a new version of the decider-program can detect versions of itself in the input, and when it does so it simply returns "self-referential? Now any type of manipulation of its outputs is utterly useless - Hal will simply always return "self-referential". The paradox is solved. This doesn't mean that we've proven that a Hal program is possible, but the proof that he is _impossible_ now doesn't work. A program that can predict if _any program_ will halt, and always returns a boolean, except when the input program contains its own code (which is in only a very small amount of inputs), is completely possible by this logic. To me the problem seems similar to saying computers can never solve division by zero. And it's true, if you define the division as a operation which takes a rational number (floating point for computers) and always returns _the rational number_ which is 1 divided by the input. This doesn't work, but the problem is that the definition itself contains the paradox: The output of one of the inputs, namely 0, is not defined, and thus does not lie in the defined output space of the rational numbers. Does this mean computers have to crash whenever they have to divide by zero? Of course not. The fix is simply defining the output space as "some rational number _or_ Not_a_Number". Paradox solved, a program which takes any rational number and returns 1 divided by this number _is_ possible.
That's boggling me, too. It's always so easy to think of cases that don't work to avoid doing them. Ok, you can't write that program with a yes/no output, granted. Doesn't seem to be a great leap to me. Just write a program with 3 outputs, problem solved. Does barry halt? "self-refrential", will goldbach series halt? yes/no.
This is a solution, technically. HOWEVER, such a thing would contradict what it was actually about, because of the thing where if the problem were to be solved for all cases, meaning we world not need this code. You are thinking actually of a workaround because of the issue that arises, and I like that. But, this is not programming for realities sake, rather what this is is magic computer science land, and also math land. Let's not think of what it means for the problem itself, but rather of analogous things to the halting problem. How about you try those?
Azmeriah no. A quantum computer can do the exact same stuff as a normal computer. In fact, you can simulate a quantum computer with a normal computer. A quantum computer is just faster for certain algorithms. So both are formal turing machines.
Diego Antonio Rosario Palomino I don‘t know. Tbh. Depends on if you can simulate s normal computer with a quantum computer. Could be that it can do less, because normal computers theoretically always give the right answer (or none) and you probably cant simulate that with a quantum computer. But we neeed an expert in complexity theorie for that
I think that the conclusion that the video apparently forces us to draw is that there are some problems that the human mind cannot solve.However Godel would have answered this apparent dilemma differently. Godel was a mathematical Neo-platonist and he asserted in one of his lectures that "Either mathematics is too big for the human mind or the human mind is more than a machine" and he agreed with the latter. What do you think? @Fabio Duarte
Well, I decided I can't just think through Goldbach's conjecture and say it is true... (I've been working on that one for over 14 years)... I'm halting my program you could say. Hahaha. However on a meta mathematics level I came to believe it is true. I don't think our minds are more than fantastically complicated machines, yet we aren't confined to the rigid rules of linear programming. But maybe we could be reduced to the equivalent of lots of simpler programs?
M of L: All living things from Man to virus seek only one thing, to increase the incidence of their genes. They behave in ways and display traits which, in the past, have tended to do so, according to a genetic strategy which, in the case of animals, is flexibly enforsed by a pain/pleasure program.
Wooow hi, just wanted to congratulate you! This video is PERFECT! It helped me to understand the Halting Problem so much better. For real, thanks :). Wish you all the best and yeah, keep going with this amazing content!!
Just imagined a thought experiment that might help: Barrie does the opposite of what Hal predicts another program will do in terms of "run forever" or "halt". If Hal assesses any other program than Barrie then it will output a "run forever" or "halt", Barrie will do the opposite of this prediction, and there is no issue. If Hal assesses Barrie's reaction to Hals assessment of a program that isn't a Barrie, then that has an end too. The Hals will run and the Barrie's will "run forever" or "halt" as they have a defined starting/ending point. It doesn't matter how many layers we add to this, because Hal doesn't actually "execute" or "run" Barrie, it only works out if Barrie would "run forever" or "halt" then outputs that like a binary variable. If the end of the chain is not Barrie then this will work and the final Barrie will "run forever" or "halt". If it is "Hals assessing Barrie's all the way down" then it will never be able to start the process because it will be endlessly checking what Barrie would be doing based on Hals assessment of what Barrie would do ad infinitum.
My reply was to be about the earlier comment, not this one specifically. (The one that starts with "Barrie3, N, Barrie. It's inconsequential. Can you link to any source that explicitly states that an equivalent of Barrie is as you describe?") Also, i'll make it as a separate reply, to have this one as a place to add comments should my replies start disappearing again.
"If Hal assesses any other program than Barrie then [...] there is no issue." What about if Hal assesses Carrie, which does 99% of the same things as Barrie but has a different way of achieving the ending conditional? Barrie = Barrie1 (DuplicateInput) then Barrie2 (Hal) then Barrie3 (PerformNegation). Carrie = Carrie1 (DuplicateInput) then Carrie2 (Hal) then Carrie3 (AnotherPerformNegation). Say, Barrie3 = "if computedBehaviour == programHalts then { do NOP while (true) } else exit" and Carrie3 = "if computedBehaviour == programLoops then exit else { do counter++ while (counter>=0) }" Now, for me it's obvious that Carrie is equivalent to Barrie, down to each state transition (until the conditional), and i'm sure it could be proven if necessary. What if we focus on what happens for Carrie( barrie )? It would ask Hal about Barrie (barrie), then perform the opposite way. And because of the equivalence, Barrie( barrie ) will perform the same way, opposite of what Hal has said.
![Felix "Unfair" | [Stray Kids : SKZ-PLAYER]](http://i.ytimg.com/vi/Oswujxm2Ag0/mqdefault.jpg)
WHOOPS 1 isn't a prime. The computer would have stopped at (2+2), my bad! Thanks for pointing that out everyone :) I can be a bit ignorabimus sometimes.
Ignorabimus maximus should be a harry potter spell. :)
We luv u nevertheless.
haha where the subject becomes stupid for a while?
Hehehe ahh yea, I'm imagining someone casting that spell on Crabbe and Goyle. Since they are already idiots... they'd be hilariously stupid. Actually half the plot of chamber of secrets could have been bypassed cause when Ron suggests tricking them into telling them what Malfoy knows, Hermione's response is something like, "not even they are that stupid". But if she had such a spell they wouldn't have had to spend half the semester brewing polyjuice.
Up and Atom woah u have only one dislike on this vid
Platypus wins, those venomous spines are no joke
i love you
haha there needs to be a video on aussie animals. Maybe even all the spiders and snakes o.O
there is its called "is Australia op?" ruclips.net/video/TrsaXzmqShM/видео.html
also there is a "spider tier list": ruclips.net/video/lOfUZvOZ400/видео.html
and "Optimizing the Snake Build": ruclips.net/video/bWOe2Znb74I/видео.html
No, the Wombat will just sit on the Platypus and squash it... 👍😊
Wait TierZoo, you’re into comp sci and math?
These guys didnt even had computers when this was proposed, I love it. Alan Turing was a visionary.
Does that name have to do with a turing machine
Mark Daniel a Turing machine is a model for how a storage device, a table of instructions encoded into the storage device and a machine that follows the instructions to modify the data on that storage device based on those instructions. It’s a model that was proven to be able to solve any problem that’s solvable by a computer given enough time and storage. And it’s ideas like this that made computers possible in the first place
they might not of have a modern computer, but before electrical computers there was mechanical computing machines.
then punch card computers with no screens.
An electrical system is a basic computer and the transistor is loosely based on the on/off switch on=1 off=0
vaccuum tube was the first automatic switching device at 1903 a solid thirty years before Turing made his machine then the transistor debuted in 1947
Turing made the first automatic sorting algorithm in a machine in 1936
@@markhaus no. the vacuum tube was the first step into modern computing. Turning made a sort function algorithm and had a mechanical machine sort using if thens cards until the sequence completed.
Seems a few people are either trolling or missing a fundamental detail of the particular proof. Hal is assumed to be a *general purpose* program that can be run on *any* input program and it always provides the correct answer. Because Hal is defined to work on all programs, it must be able to work on itself since Hal is, itself, a program. The thing I think a lot of people are missing is that this is a proof that the halting problem cannot be solved in the *general* case. To prove that the general case cannot be solved, you just need to find *one* counterexample.
This says nothing about specific cases. There are plenty of specific cases where it is possible to identify if a program will halt. The existence of those cases does not invalidate the proof. The proof is simply telling us that there is no magic box that will work on every possible program. Basically, it means there isn't a magic shortcut for solving Goldbach and other problems.
thanks for your comment because the video doesn't explain this at all!
Still, I don't know what this all has to do with a program that has to test all numbers to infinity (like the goldbach problem). Of coure, it runs forever.
@@Falkdr The "Goldbach solver" program will stop if it finds an even number that cannot be represented as 2 primes. So if you could run "Hal" with the goldback program as input and it returns that the program never halts, the goldbach conjecture is proven true. If "Hal" returns that the goldbach program does halt, that can only happen because the goldbach program found a contradiction - an even number that cannot be represented by two primes - and stopped, and you have proven the goldbach conjecture false.
@@uchian No, Hal would never return anything because it has to go through all the numbers that are, to test them (so infinite). You'll have to wait forever for the answer.
It sounds Up&Atom was just asking "does Magic exist?". As far as we know, it doesn't, so there doesn't seem to be all to much behind this video.
@@Falkdr In the halting problem, 'Hal' does not run the program to determine whether it halts or not. It would determine it through some (unspecified) analysis of the instructions in the program that returns a yes or know answer as to whether the program halts or not. The proof discussed in the video means that the the "unspecified" bit of the above statement is mathematically impossible in the general case.
I got that, by unspecified you mean 'magic'. Its not that bold to set up an impossible claim and proof that it is impossible, imho.
I don't think the 'halting problem' would've been huge riddle in modern days, back then it might have been a great analysis, though.
Studied this back in the 70s in Cambridge when the people who had known Turing were still lecturing. This video brought back some wonderful memories. Thanks.
BTW the entire university computing service ran on an IBM 370/165 with 3 megabytes of RAM back then.
5:07 "Barrie can't both run forever and halt" Schrödinger's cat is calling fake news on this one.
f. g Did you just actively interact with Schrodinger's experiment?
Ibraheem Al hadede Yeah, how do you think I am here? 😂
But Hal is "observing" barry
But what do you do with a dead program/cat?
@@Trident_Euclid interact*
3:53 - I'm sorry, Dave, I'm afraid I can't do that.
I remember in the good old days studying computer science and first hearing about "The halting problem" it seemed odd and trivial to me at first... that is because I didn't understand it, I mean... I didn't understand why it was such a big deal. The proof done by contradiction was brilliant ploy by Turing, I'll never forget how astonished that I actually got understood it on the first run-through (that rarely happens!)... but you made me feel sad for the way poor Hilbert was broken hearted in your animation... but, as you rightly pointed out, he does have his own space named after him, so there is that...
You have one of the best animations for science videos, period.
Ehm... 3blue1brown, need I say more?
Physicist in training here from NYC (third year). You've got such great content! Very concise, descriptive, and VERY entertaining. Keep it up :D !
I solved the halting problem by unplugging my computer and crying.
Melthornals computer halts. Must run forever.
Hilbert's Nemeses: Turing and Gödel :D
Hilbert KNEW about Gödel's Theorems, but rejected their conclusions, proving that even the most logical mind (Hilbert's) has an logical conclusion that it cannot accept. Even the King of Mathematical Reasoning had his weak points.
I just found your channel, your videos are great! Keep up the good educational videos! :)
Hey Keystone! Nice to see you here :D
MrWilliam932 hey! ;)
“Will I ever stop being a disappointment to my family?”
A’ight Jade, I’m gonna need you to stop recording me while I’m “working”, we’ve talked about this.
that shade tho
It’s amazing how smart and ahead of his time Turing was. I wonder what was his thought process to even fathom such concepts and ideas in an era where computing was still primitive in comparison.
Using the halting problem, we can answer the original problems that Hilbert posed, and not with resounding yeses. "Is mathematics complete?" If mathematics was complete, a computer could prove everything that was true, answering all problems, because it could return a 1 for true and a 0 for if it wasn't true, but a computer cannot solve all problems, so mathematics must be incomplete. Is mathematics consistent? Again, if mathematics could be counted on to be consistent, computers should not be halted by the halting problem, because the math used by computers wouldn't be able to create a paradox. "Is mathematics decidable?" Again, if mathematics were decidable, we would be able to create a program that could take that method to determine if a statement was true or not, so all three of Hilbert's questions were answered decidably "no" by Turing's computers.
In fact, a Turing machine has been created with, I believe, 29 states that halts if and only if the Goldbach conjecture is false. The step function S is the maximum number of steps a Turing machine can run before it must either halt or run forever. So, if you ran the machine for S(29) steps and it didn't halt, you'd know the conjecture was true! Of course, the halting problem proves that S cannot be computed by a Turing machine, so we can't actually know what S(29) is. However, we do know that S(17) is greater than *Graham's number*, so the age of the universe isn't even pocket change compared to it.
love the way you explain everything with such ease and smile.
Turing's use of self referential contradiction in the halting problem in (1936) reminds me of Gödel's incompleteness theorem (1931).
Scott Busby Yeah he was heavily inspired by Godel's approach to the completeness question
Turing was inspired by Gödel. I was disappointed she mentioned Hilbert, but didn't give Gödel credit. Still, I can see making the decision to keep the video under ten minutes.
Scott Busby: And that's no coincidence. Turing's Halting Problem, Gödels incompleteness theorems and Church's Lambda Calculus are functionally equivalent. You can convert one model into all of the others.
Turings halting problem was a rephrasing of gödels incompleteness theorem.. gödel was the first one to see it and the real genius.. Turing was a big fan of gödel btw.. this video is misleading!
This is so good Jade, probably the best explanation on this question I've ever seen!!
I really love your way of explaining complex knowledge/theorms in very simple words along with cool animations. 😍😍
I always hated thoery of computation, but now I don't 😊
Really like the variation of such intriguing topics you make videos on! Keep it up, super fresh!
"Am I still a disappointment to my family" - that hit home...
What if we put the Barrie program on a quantum computer where it is potentially both running and halting simultaneously, in a state of superposition. I think I have solved it. ;-) Great videos, keep them coming.
But even then it has to resolve to one state. ;)
Barrie and Hal are just entangled particles. Also, Einstein hates them!
@@zeeshanbhat What if it is a super-conducting barry?
Funny that you should say that actually, but it turns out that not even quantum computers can solve the halting problem and that the proof for it has some major implications throughout physics and maths:
www.quantamagazine.org/landmark-computer-science-proof-cascades-through-physics-and-math-20200304/
@@shadiester I carefully and slowly read the article you posted and if I'm honest my understanding of it far from complete. If my view is correct, without entanglement the proof would remain unsolved. Cheers
It's a great problem. I remember I loved the proof when I first heard about it. I also really like another problem that can't be solved called Post Correspondence Problem and that's because while the halting problem at least sounds like something really hard to do, PCP is a problem that seems like something easy. Something we can do by hand when given an example input. And how the hell can there be no step by step method solving something like that for any input, given unlimited amount of time and resources? It still blows my mind that there isn't, but I've seen the proof. But way more complicated than this one. And PCP can be applied to proving a bunch of other things aren't decidable. Darn, the laws of our universe are harsh! It's not enough we don't know the answers to so many things and going to keep trying to answer for thousands of years to come, but we already know there are things we'll never answer! That's just depressing!
This is absolutely the best explanation I've seen for this paradox! Thank you so much!
Great video, wonder if in a quantum world it could run and halt at the same time :)
3:03 1 is not a prime.
soz my bad
2+2, happy now?
i just want to wrote this
How would you write 3 though
Neither is a composite number poor number 1, 1 is the loneliest number.
This is just more complicated version of "this sentence is false".
This video is the best, I've searched a very long time but I did't understand anything, THANK YOU SO MUCH ❤
Greetings from a brazilian fan, i love your channel!
Looking forward to videos about the mathematics behind machine learning (backpropagation derivatives, error function parameters, random minibatches, what is matrix calculus and why GPU's parallel process is a great solution for this, etc)
can't wait to see them =)
sorry my bad english
Achei q n tinha br aqui
“Who do you think would win between a platypus and a wombat?”
That is the most Australian sentence I have heard all week.
5:07 Now I want someone to try this on a quantum computer.
Strangely enough, a quantum computer would not help: Halting Problem remains impossible.
@@DavidFMayerPhD But consider, in a quantum system, superposition gives 'Hal' a third option to return, where it is both running and halted, simultaneously.
@@twistedbard That is NOT an answer. A result means a SINGLE result, not a superposition of results.
@@twistedbard also, what would "both running and halted" even *_mean_* tho? Does the input machine stop or not?
Bruce Lee said in the Tao of Jeet Kune Do, "The solution to any problem is understanding it. Once you understand the problem, the problem dissolves." What that means to me is, if a problem doesn't have a solution, the reason is because we don't fully understand it yet.
Besides the cool topics and easy-to-follow explanations, I think what sets this channel apart from many similar channels is the animations :)
you said input X to barrie is X = "program with an input". What's the input with which you are passing barrie into barrie?
I've had programming ide's pop up a warning saying a subroutine would run forever.
its more along the lines of it not having something that would end the loop rather than it never finding an answer.
you would need a program that predicts the future in order to know if it would halt.
That could be as simple as making sure you don't have something the compiler compiles to the equivalent of while(true) {code}
Because of you, I finally somehow understood the halting problem. The recursive representations feed onto itself of your video did it - brilliant I believe. Maybe a way out of the halting problem is the impossibility of feeding back a decider into itself, an ultimate decider that cannot be fed back into the programs - beyond the Turing machines. At that level, though it can take in programs and make a decision, it cannot be called program or computer, a totally different category. What is that thing, which is not a program itself, that could take in programs and evaluate them? Or we have a third option, we endow Barrie a recognition that it itself is inputted into the same evaluation, so Barrie could halt, loop or return 'not like this, not like this, we will run into a paradox.'
The halting problem exists because of the nature of the universe itself. The halting problem essentially asks a computer to predict the future without having to simulate it first, and that's not how the this particular universe works. It's not a problem restricted to computers.
Started with value of infinity, where we have an infinite number of answers and so will run forever, then did a right turn into a paradox.
This channel deserves like 10X the subscriber count.
aww shucks ☺️
Hi mam
I am an Computer science engineer and from last 2 years finding a perfect video for Halting Problem...
write now I can say that "I got that perfect video"..
You can stop now, then.
Incredibly intriguing and took me a couple watches to actually understand it 😂.
I'm glad you were able to get it! It took me a whlie let me tell you haha
Wow that was so awesome. Your channel will become huge ,i just in love with your channel's content.
Brilliant! A simple way to describe a seemingly complex problem. Thank you.
Jade’s smile, Jade’s drawings, Jade’s outfits, Jade’s humour. This channel is just wonderful.
That is basically the computer equivalent to the age-old „This sentence is false.“ paradox.
Seems like if you want to disprove something, using a self-contradictory statement is the starting point :-D
Loved the Space Odyssey reference. Excellent video as always.
Hi there, I was thinking of starting my own channel and I like this kind of topic. But when I saw the video I think you could have an error on it. I should check on the original paper, but I think you are missing something important which is the input of the input.
For instance, in 4:19 you are talking about the program Randy, the program Randy could Stop or Run forever without having into account the input of Randy, which implies that Randy parameters are not important on if the program Randy will run forever or not. But you have programs that its input decides if they will run Foverer or not.
When you state the proof, your say in 4:45: You said that Halt receives Halt as an Input, in an explicit way is: The program HALT receives as Input a HALT program. But you are missing one parameter there, which is the Input of the Input, Halt can say if the Input will stop or not because The input program could receive inputs that makes HALT or NOT.
I know its confusing, but maybe I Skipping something. Thanks
I initially got confused about the same thing. Took me a while to realize what I have missed. The key is at 4:08.
HAL can answer the question: will a program X with input Y halt or not? So HAL has 2 inputs, the program (X) and the input to that program (Y).
BARRIE is different, it only takes one input, a program (X). It then asks the question: what would HAL answer given program X with input X, and then does the opposite. That is, the input to X is X itself.
@@AdrianTaga ok but if X is a program that needs an input Y to run, X is not a valid input for X itself, at a minimum it's not complete, there has to be a Y input, of the appropriate domain, at the end of the chain.
@titusfx not quite, at 4:45 it is BARRIE not Halt that receives itself as input. (And unlike Halt, Barrie only takes one input.) Also, Randy would later similarly received itself as input, that's why she wrote "Randy(Randy)". At 4:19 it is merely shown that the "X" that Barrie receives as input will in this case be Randy, then Barrie will work on it as in the description: "Do the opposite of what Hal predicts *about program X and input X."* :-B
@@AdrianTaga as @Daniele Messina says, Barrier will have the input X, which is Barrier, so the input X will need another input (and that will be forever if you just put Barrier as argument). I have got this doubt for years, since University. And I have the same problem understanding the paper and this exact point. I could be skipping something...
@@irrelevant_noob What you said is correct. But that's not what I'm trying to say (I wrote about Halt, trying to "expand" Barrier). What you said about randy is correct. So, instead of thinking on Randy, try to change Randy with Barrier, which is what Turing did.
Barrier will have the input X, which is Barrier, so the input X will need another input (why? Because is Barrie, so it needs another input, which that input can not be, Barrier, because it will need another one, and so on, until the infinity)
The proof idea is similar to Russell’s paradox where you construct “the set of all sets that don’t contain itself as an element” (after arguing it’s neither empty nor the “set of all sets”), and then ask “does this set contain itself as an element?”.
The halting problem doesn't just mean there are problems "we" can't solve. It means there are problems that are impossible to solve - by anything - ever. It means omniscience is impossible.
your conclusion isn't necessarily true. while it's true that there are problems that we cannot in principle find a solution for, that doesn't mean the solution cannot be known.so for example, i (imagine i am a magical being outside of time) could know all the digits of PI, but you, in your finite universe, because you don't have infinite energy and time, cannot determine them. you have to stop at some point.
then there are problems that have no solution in principle. those don't disprove omniscience. this would be like saying "god cannot create a triangle with 4 sides" and say "ha! no omnipotence!"
No. That's my point. It proves that nothing - not even a magical superbeing outside of time and space - could know everything.
By the way, a magical being outside of time is, by definition, impossible. For something to exist, it has to be in time and space.
Hmmmm... "For something to exist, it has to be in time and space." What about 1+1=2? That and all the rest of math, can math not exist without space time?
Math is a concept. Concepts aren't real in any material sense - they require an intelligent being to conceive of them. If you're arguing that god is merely a concept, I agree. But that doesn't mean he actually exists as a real being. Fairies are concepts too - they also don't exist as "real beings". I think it's about time we grew up and accepted that magical beings don't actually exist.
What about the multi-verse, our space-time doesn't connect to the whole thing otherwise they wouldn't talk about universes colliding and popping like bubbles. So IF that theory is true then not only is there something outside our space time, pretty much everything is out there.
the contradiction only happens when self referencing loops are involved, but most functions we use in real life are not self referencing, being able to decide if they halt or not are still very valuable, has anyone done any work on that?
Every loop is self-referencing by its very nature. A loop is equivalent to a function that calls itself recursively, with varying inputs. The program can be self-referencing in a very obfuscated non-obvious way. There is plenty of theoretical research that goes into this.
In practice, the halting problem and its cousins come up in areas where self-referencing is desired behavior. For example, in compilers. It would be rather useless to have a compiler that can't even compile itself.
@@KohuGaly thanks
Computer, which is better: Pirates or Ninjas? Star Wars or Star Trek? ... .... 42.
Let's call it "Hell"
Me: wut?
*Hal appears*
Oh
A platypus would obviously win in a fight! That's not even a question.
haha i dunno wombats are pretty strong and have sharp claws
Such a profound problem with such a simple, elegant and even funny solution! I am amazed how often genius and beauty follow the same tracks
The classic "Trust me! I'm a liar."
If you are always going to lie, people can trust you because they can know the truth. Otherwise it goes to probability theory.
I guess, i finally undertstand what halting problem is. Thank you so much.
Interesting fact: Perfect antivirus program is also imposible as proven by Fred Cohen, based on the halting problem.
that is an interesting fact :)
There's a simple solution to the problem of Barry. Make him time independent. What I mean to say is that the computer will execute code in order, that is, it will take time between executions. If you run all the code for Barry simultaneously, you can achieve a superposition of Barry running and staying still. It's similar to what happens when you connect your camera via analog to a tv and then point it at the tv. In that sense, it is looking at itself
Who makes your animations??
I do! 😊
impressive
0:40 - Me at the beginning of the semester
1:08 - Finals
Do you write your jokes by yourself??if so then you're a good comedian as well
haha well I'm glad someone thinks so...
@@upandatom 'G0LDbAcH wuz a L00zer' had me chuckling :)) Only proves that even the smarty-pants computer that can solve the halting problem would still struggle with grammar :p
The Turing Problem reminds me of the thought experiment you did during your free will video.
Where a computer computes whether a person will be invited but can't tell them without changing the result.
Turing was brilliant!
No Turing was GENIUS :-)
I'm high AF laughing my ass off at how the professor got fucking furious asking questions over the course of some frames.
"who even has a space of his own" ROFLLLLLLLL!
0:32 "has his own space named after him" ;-)
You broke my brain in the best way possible. Thank you ☺️ I really enjoyed watching the video.
Your videos speak volumes for your level of intelligence. ^_^
Very interesting explanation. Thank you.
1 is not a prime.
you're right. my bad.
That got interesting real fast 😮 Alan Turing truly was the God of Programming 😭♥️
I think the halting problem has a fundamental problem, which makes it much less general than it might appear. Now don't get me wrong, given its assumptions the logic is perfectly valid - but that's where the problem lies, in its assumptions. The only possible return values of our hypothetical decider-program are true and false. What happens if we add a third option: self-referential
The only time the halting problem occurs, is when the algorithm is fed with a modified version of itself. So what happens if a new version of the decider-program can detect versions of itself in the input, and when it does so it simply returns "self-referential? Now any type of manipulation of its outputs is utterly useless - Hal will simply always return "self-referential". The paradox is solved.
This doesn't mean that we've proven that a Hal program is possible, but the proof that he is _impossible_ now doesn't work. A program that can predict if _any program_ will halt, and always returns a boolean, except when the input program contains its own code (which is in only a very small amount of inputs), is completely possible by this logic.
To me the problem seems similar to saying computers can never solve division by zero. And it's true, if you define the division as a operation which takes a rational number (floating point for computers) and always returns _the rational number_ which is 1 divided by the input. This doesn't work, but the problem is that the definition itself contains the paradox: The output of one of the inputs, namely 0, is not defined, and thus does not lie in the defined output space of the rational numbers. Does this mean computers have to crash whenever they have to divide by zero? Of course not. The fix is simply defining the output space as "some rational number _or_ Not_a_Number". Paradox solved, a program which takes any rational number and returns 1 divided by this number _is_ possible.
That's boggling me, too. It's always so easy to think of cases that don't work to avoid doing them. Ok, you can't write that program with a yes/no output, granted. Doesn't seem to be a great leap to me.
Just write a program with 3 outputs, problem solved.
Does barry halt? "self-refrential", will goldbach series halt? yes/no.
This is a solution, technically. HOWEVER, such a thing would contradict what it was actually about, because of the thing where if the problem were to be solved for all cases, meaning we world not need this code. You are thinking actually of a workaround because of the issue that arises, and I like that. But, this is not programming for realities sake, rather what this is is magic computer science land, and also math land. Let's not think of what it means for the problem itself, but rather of analogous things to the halting problem. How about you try those?
Hahaha! I love it, it's a beautiful application of Russell's paradox!
Question: Could a quantum computer solve the halting problem?
Azmeriah no. A quantum computer can do the exact same stuff as a normal computer. In fact, you can simulate a quantum computer with a normal computer. A quantum computer is just faster for certain algorithms. So both are formal turing machines.
@@macrozone I thought quantum computers can do less than normal ones
Diego Antonio Rosario Palomino I don‘t know. Tbh. Depends on if you can simulate s normal computer with a quantum computer. Could be that it can do less, because normal computers theoretically always give the right answer (or none) and you probably cant simulate that with a quantum computer. But we neeed an expert in complexity theorie for that
I really enjoys your video. From Malaysia. It is really an eye opening.
I don't get it. I'll try watching it again.
Awesome video, very well explained for a math novice like myself.
You literally have an infinity like-to-dislike ratio right now.
This woman has like every quality you'd look for in a teacher/professor
Gödel... make a video about Gödel... pls
Would you kindly make a video about Gödel?
#BioshockStrategy
ok :)
Yay!
I think that the conclusion that the video apparently forces us to draw is that there are some problems that the human mind cannot solve.However Godel would have answered this apparent dilemma differently. Godel was a mathematical Neo-platonist and he asserted in one of his lectures that "Either mathematics is too big for the human mind or the human mind is more than a machine" and he agreed with the latter. What do you think? @Fabio Duarte
Well, I decided I can't just think through Goldbach's conjecture and say it is true... (I've been working on that one for over 14 years)... I'm halting my program you could say. Hahaha. However on a meta mathematics level I came to believe it is true. I don't think our minds are more than fantastically complicated machines, yet we aren't confined to the rigid rules of linear programming. But maybe we could be reduced to the equivalent of lots of simpler programs?
The best video that explained the halting problem in layman's terms!
Shut up and take my subscription!
The meaning of life is 42
Bruno Henrik
Are you sure? 42 is the ultimate answer for the ultimate question. Not a mere question like 'what is meaning of life?'
And the ultimate question IS...
37 + 5
M of L: All living things from Man to virus seek only one thing, to increase the incidence of their genes. They behave in ways and display traits which, in the past, have tended to do so, according to a genetic strategy which, in the case of animals, is flexibly enforsed by a pain/pleasure program.
@@brunohenrik8025 What is (-80538738812075974)^3 + (80435758145817515)^3 + (12602123297335631)^3 ?
Super good videos that you have made. Very clear and also entertaining. Good job.
you don't even need a computer 42 is the answer to life the universe and everything
This is one of the funniest Up and Atom video, and possibly the funniest video on the Halting problem.
There are some problems comuters can't solve?! That's so sad. Alexa make me happy somehow.
Great video! Your channel is amazing!
Barry runs in a superposition. *Drops mic*
Not sure about anyone else, but this video wore me out 😁🤣Great video Jade. Thank you for sharing. 🤗😘
You are not a disappointment
Wow, great explanation! Best one so far!
Your videos are a million times better than my lectures. Keep up the great work!!
this is such a great video! please make more on computer science topics please
_You are the best. Thank you! Lmao when you talk about Hal and Berrie. Love it so much hahahahaha_
Wooow hi, just wanted to congratulate you! This video is PERFECT! It helped me to understand the Halting Problem so much better. For real, thanks :). Wish you all the best and yeah, keep going with this amazing content!!
Why have I not seen your channel before!? I love it!
I just discovered this channel, and I just fell in love... Also, very good video, this is like a computing-version of the Gödel Theorem
Just imagined a thought experiment that might help:
Barrie does the opposite of what Hal predicts another program will do in terms of "run forever" or "halt".
If Hal assesses any other program than Barrie then it will output a "run forever" or "halt", Barrie will do the opposite of this prediction, and there is no issue.
If Hal assesses Barrie's reaction to Hals assessment of a program that isn't a Barrie, then that has an end too. The Hals will run and the Barrie's will "run forever" or "halt" as they have a defined starting/ending point.
It doesn't matter how many layers we add to this, because Hal doesn't actually "execute" or "run" Barrie, it only works out if Barrie would "run forever" or "halt" then outputs that like a binary variable. If the end of the chain is not Barrie then this will work and the final Barrie will "run forever" or "halt".
If it is "Hals assessing Barrie's all the way down" then it will never be able to start the process because it will be endlessly checking what Barrie would be doing based on Hals assessment of what Barrie would do ad infinitum.
My reply was to be about the earlier comment, not this one specifically. (The one that starts with "Barrie3, N, Barrie. It's inconsequential. Can you link to any source that explicitly states that an equivalent of Barrie is as you describe?")
Also, i'll make it as a separate reply, to have this one as a place to add comments should my replies start disappearing again.
"If Hal assesses any other program than Barrie then [...] there is no issue." What about if Hal assesses Carrie, which does 99% of the same things as Barrie but has a different way of achieving the ending conditional?
Barrie = Barrie1 (DuplicateInput) then Barrie2 (Hal) then Barrie3 (PerformNegation).
Carrie = Carrie1 (DuplicateInput) then Carrie2 (Hal) then Carrie3 (AnotherPerformNegation).
Say, Barrie3 = "if computedBehaviour == programHalts then { do NOP while (true) } else exit" and Carrie3 = "if computedBehaviour == programLoops then exit else { do counter++ while (counter>=0) }"
Now, for me it's obvious that Carrie is equivalent to Barrie, down to each state transition (until the conditional), and i'm sure it could be proven if necessary. What if we focus on what happens for Carrie( barrie )? It would ask Hal about Barrie (barrie), then perform the opposite way. And because of the equivalence, Barrie( barrie ) will perform the same way, opposite of what Hal has said.
I came here from an MITx class from Edx ( 6.00.1x). Your video is amazing!