What I (Mechanical Engineer) was told in digital logic design: "Computers don't do amazing things. They do simple things amazingly fast." The people who break the complex problems into simple steps to be solved in this way are the ones who do amazing things.
The sound design in this is pretty good. The simple whiffs of paper when the little dudes are putting them on the machine is a nice attention to detail.
When I first watched this I thought "this doesn't prove H can't exist, it proves X can't exist." But after a look through the comments, I've realized that disproving X disproves H by extension because if H could exist, then we could theoretically build X, which was proved in this video to be impossible. Hope this helps anyone who is confused
I mean your argument is true, if X doent exist then H doesnt exist but the problem proves that H doesnt exist (and so X doesnt exist but that is not important). It's the other way around, logically speaking
Fletcher Helms "Oh, that was easy," says Man, and for an encore goes on to prove that black is white and gets himself killed on the next zebra crossing.” The joke is that if black is white, zebra crossings don't exist and he gets run over. I guess americans don't say zebra crossing?
Maybe H is just suffering from having such high expectations. Give the man a break, he was right every time until we actively did everything we could to confuse him. My man deserves better than this
@@bubbsterr4967 I've seen people get emotionally attached to hipothetical, not actually existent characters. But I feel like it's on a whole new level to get attached to a hipothetical, non existent character that not only doesn't exist, it also cannot possibly exist
@@want-diversecontent3887 The problem here is that the blueprint of X, which gets fed to H, contains H itself. With any other input, this can work, however, this would cause an infinite recursion, causing it to get stuck. This isn't a flaw in H, it's a flaw on X. Also, "if it doesn't work in one case it can't work in any case" simply isn't true.
About twice a year I come back to this video to watch again. I forget some aspects of the concept, but the way that they explain each axiom regarding the usage and logic of these examples is so interesting.
So it seems like a common misunderstanding among commenters here is thinking that machine X is merely "broken" or that it "fails". That is not what happens in this proof. X is not merely a broken machine, but a _full on paradox._ It's not that X does the wrong thing, it's that neither "halts" nor "doesn't halt" is a logically consistent answer for what X does. This is a contradiction, not merely a broken machine. That's why you can't just "remove the negator" or do anything else to fix X. X itself is a machine that cannot exist, and since every component besides H can obviously exist, and the way they are connected is together obviously fine, that leaves H as the impossible component. If X cannot exist, then H cannot exist, and so there is no algorithm that can solve the halting problem for all inputs.
Also consider that the H part of the x machine’s operation when fed its own blueprint would require infinite processing power to be accurate, because it would have to simulate an infinite nesting loop of X machines being fed their own blueprints and simulating themselves. Strange that wasn’t mentioned in the video.
@@canon-de-75 Well, it’s not mentioned in the video because it’s not true. There is no assumption that H has to actually evaluate its input step by step (in fact, we can immediately rule that out, because a machine that worked that way wouldn’t _ever_ be able to detect non-halting programs). The question is whether a machine can do some kind of clever analysis to solve the halting problem, sidestepping the problem of infinite evaluation time, and the answer the proof gives us is “no”. The beauty of this proof is that you don’t have to figure out _anything_ about how H would actually do its job. Simply by its definition, we can see that it’s logically impossible. We don’t have to think about how much processing power it would take, or how it would reason about its inputs. All we have to know is “solves the halting problem”, and we can immediately demonstrate that it’s impossible. And that’s also why this is so useful. We can take other problems and notice that they have the “shape” of solving the halting problem, and if we can prove that connection, we can show that those problems are also unsolvable - again, sidestepping any further reasoning about how a machine would try to solve those problems.
@@chaumas One thing I've always wondered about this proof is, what happens if we remove the assumption that machine H is, itself, a Turing device? In other words, what if we prove the existence of algorithms that exist, but cannot be represented with Turing-compatible logic? Then this particular proof would break, since it would be plausible for H to analyze only Turing algorithms, machine X cannot be assembled in the first place, and nobody is implying that there exists a Turing algorithm for solving the halting problem of Turing algorithms. Or what if we go the other way, and say that H can analyze code that only runs on some subset of its own code? Even if we had a single opcode that is required for H to run, yet H cannot analyze any code which includes that opcode, does the proof still hold true? Kind of like when someone says "3 * 0 = 2 * 0, divide both sides by 0, we get 3 = 2!" we do not say "we've proven division cannot exist!" but instead we say "DON'T DO THAT!" The proof does not disprove the possibility of H existing. It only disproves the possibility of an H that, itself, cannot halt.
@@rawlaalawr9009 Yeah, you can solve the Halting problem over Turing machines using something more powerful than a Turing machine, as I understand it. There’s a whole subfield of study about hypothetical machines that can execute a countably infinite number of steps in a finite amount of time. I’m not super well versed on this topic. We have no reason to believe that anything close to these machines is physically possible, so it’s getting way out into the realm of theory for theory’s sake. But my understanding is that while these hypothetical machines can decide the halting problem over Turing machines, they have their _own_ halting problem which is similarly undecidable by themselves.
@@chaumas I thought so. Now that I think more deeply about it, the thing that bothers me most about the classic proof is that it fails to produce an algorithm that cannot be analyzed. It only ever ends up saying "This algorithm cannot exist, because it contains itself, which is an algorithm that cannot exist". Which... well, isn't actually saying anything substantial, is it? It seems like a more intuitive way of proving the halting problem impossible to solve, is to write a working algorithm which is impossible to analyze. Rather than the classic proof, which only defines, then subsequently fails to provide, an algorithm which cannot be analyzed. So I wonder, does there exist a block of C++ code that works, produces expected results with certain inputs, yet becomes utterly indeterminate when given other inputs? I feel like I've run into these before. The game of life comes to mind, which can apparently simulate itself. But when you force the problem into the realm of practicality, you by necessity need to introduce limitations. Given infinite memory, the game of life might be indeterminate for some inputs... but do any such inputs exist if we limit the size of the board, and say the program will halt if it tries to overflow? And if there exist no such inputs, is a purely theoretical H-solver of any use to us whatsoever, when every single working system in the world operates under definable constraints?
All of the people saying that you have to just “remove h or n from the problem” are COMPLETELY missing the point. The point isn’t “how do we make a computer that doesn’t mess up/halt”, it’s “is there a case where a computer can’t solve a problem”. The fact that people are specifically saying to remove something from the equation to work are PROVING that the halting problem is true. That’s why we can’t just remove n or h from the problem, if x is a computer that can logically exist but h fundamentally causes it to not provide a logical solution, that in itself is a contradiction. If we didn’t have the need to remove it, there would be no problem and it would theoretically be possible for computers to do everything. But the fact that it can’t do something in a specific case proves that this is wrong via “proof by contradiction”, we assume something to be true, then say there’s a contradiction which occurs from it being true, meaning it can’t be true, and is therefore false.
I think the problem is the title uses 'everything', and uses it by a literal definition. Nothing can do everything, because not everything is possible. But the video itself claims 'H' cannot exist because it is impossible to never be wrong, which is untrue. 'H' would simply get stuck, and therefore not be incorrect. It likely would do this before even arriving at the negator since it isn't possible for something to perfectly simulate itself and something else without having infinite complexity.
@@Pihsrosnec The definition of H is a machine that is perfect in solving the halting problem. If perfection cannot be achieved, then H cannot exist, proving the video's point yet again.
@@Quasar0406 It's more like: I have a stick that can be anywhere. I use logic to prove it can't be in place A. If my logic is valid, then the assumption that the stick can be anywhere is false. Therefore any sticks that "can be anywhere" cannot exist.
Why does this matter? Because reducibility. There's a trick you can pull in mathematics where you can "reduce" one problem to another, which basically means "If this problem can be solved, than this other problem can also be solved". Since we know the Halting Problem is unsolvable, it's impossible for any other solvable problem to reduce to it. So if the problem you're trying to solve is reducible to the Halting Problem, you should just give up now because you're never going to find a solution. This can catch even very smart computer scientists off guard sometimes, because there are a lot of problems that really feel like they should be solvable, but end up being reducible to the Halting Problem.
interesting. what would be the reduction in words (instead of saying it reduces to the halting problem). I mean, what is exactly the contradiction or the unsolvable aspect of this problem? Is it that if you wondering if your machine can get every answer right it wont or what? i cant figure out
@@LuckLekLeo I'm not entirely sure what you're asking, but maybe an example will help. Wang Tiles (en.m.wikipedia.org/wiki/Wang_tile ) are a type of square tile with colored glue on each side. To fill a grid with Wang Tiles, the colors of adjacent tiles need to match. So if you're given a specific set of Wang Tiles and a grid with a specific size, is it possible to fill the grid completely with valid tiles? Now, some combinations of tiles will obviously fail. It's not hard to deliberately pick a tile set and grid that makes this impossible. Likewise, some combinations are obviously possible. If you include a Wang tile with the same color on all 4 sides, you can just repeat that tile on every square of the grid and easily fill it up. But let's say you don't know in advance what tiles or grid shape you're going to be given. Can you write an algorithm that, no matter what combination you give it, will spit out a "Yes" or "No" answer telling you whether or not the grid can be tiled? This, as it turns out, cannot be done. People have demonstrated (using some pretty creative math) that if a Wang Tile decider machine *could* be made, you could use it to solve the Halting Problem. And since the Halting Problem is unsolvable, then the Wang Tile problem is also unsolvable. It doesn't look like it has anything to do with the Halting Problem at first glance, but math takes some weird twists and turns sometimes.
@@galoomba5559 For the sake of this problem, you don't know what grid you'll be given. It could be finite, it could be infinite. But yes, a finite grid could be easily brute-forced, and for that reason most formulations of this problem restrict it to an infinite grid.
So, basically, all we need is a machine that when gets "stuck" with an unsolvable task will just drop a "well, who cares anyway?" and goes on with a wrong solution sequence picked randomly until it says "Ah, f*ck, my mistake" and tries something else. Yep, perfectly human.
(SECOND PARA IS IMPORTANT, don't skip) A lot of people do not seem to be following the argument rigorously enough. This is a proof by contradiction; we assume something to be true, and use this assumption to arrive at a logical contradiction, thus proving that our initial assumption was incorrect. In this case, our assumption is that such a machine as H exists, with the key thing about H being that it is perfect, and always gives the right answer. We then use this assumption to see if we can find a logical contradiction. We might engineer a situation that seems needlessly unfair, but this is the whole idea. Once we run into the logical contradiction (the fact that H was wrong, even though it is by definition never wrong), we know our assumption MUST be false, our assumption being that such a machine as H exists. Nothing remains of H; even though it was just one, cleverly designed situation that it couldn't handle, the fact that it couldn't handle it, completely eradicates any trace of it. This is a very general form of proof. The realisation through a proof like this, is that the assumption you made, does not even make sense as a logical concept. Because that fact is not obvious, we have to do some work to reveal it, but if we were insanely smart, we would know that H doesn't make sense as a concept, just like we know now that a '4 sided triangle' is nonsensical. It's not that H is too hard to build, it's that it is literally an incoherent idea, but one whose incoherence is far from obvious and requires formal proof. This was originally commented by - J Thomas 7 months ago (edited) (256 likes) th-cam.com/channels/Tq8Xel3cF7GYnIxBBBhM9Q.html thought it should not get lost in all the trifle jokes .....
I dont understand what H is but this video is really long and i dont want to watch it... I want a tldr for the video snd i dont know who to ask. This was a very interesting comment regardless of my lack of understanding though
@@dracibatic2433 well it really is not that easy and 8 minutes are not that long compared to an whole lecture for a semester about computation and complexity that we have to take at our university
damej elyas If H existed, it could detect if other computers lock up when trying to play Crysis. It probably can't tell if that other computer will actually play Crysis fail to play Crysis or outright refuse to play Crysis. Only if it will actually freeze up if you feed it a copy of Crysis and the player input.
It’s more like, if you feed X and X, H will make a contradiction, proving H cannot exist. Nothing gets “stuck” because H is stated to never get stuck, and the state of X is ambiguous.
You can program a computer system when it detects that the problem would create a logic loop that is unnecessary. Or if it would get stuck that it would just say the program is not compatible with the machine/software
@@JonathanSteadman2003 This is one of the few TH-cam videos where a high number of dislikes actually indicates ignorant viewers, not a bad video. Seems to be more common with science videos unfortunately.
@@JonathanSteadman2003 dislikes were kinda meaningless. And if a video was really disliked you can easily get to that conclusion when reading the top few comments.
This is gold! For anyone struggling with the abstractions in theoretical computer science courses, this video would be a treasure! I wish I watched it when I was struggling to grasp the abstraction. Thank you very much for this amazing animation. I bet it takes a lot of time put it all together.
This is an infinite recursion problem that can't be solved by anyone, computer or otherwise. Obviously, a machine that has to recursively simulate itself simulating itself will fail not because of any limitations of computers, but because it's a logical paradox.
@@Greg-ku7rn even if it wasnt a logical paradox, we cannot build a computer with infinite memory and infinitely fast processing power, so both reasons prove the Halting theorem
@@trustytrojan But isn’t this solved by Ai rules? Like rather than comparing EVERYTHING it has “neurons” at distances measured by weights. In that case it might not be able to answer PERFECTLY because even we haven’t defined anything perfectly?
@@trustytrojan Is it relevant if we can record the speed of light by using multiple cameras? This question is really breaking me lol, is it because we can’t perfectly define the weights of something to a computer or it can’t discover this on its own
@@Gomer._. to be perfectly honest, bringing the topic of artificial intelligence to programming theory is just a bit extra; probably cause i don't know a thing about ai theory 😂
@@LegendLength To my understanding, the point is just to prove that there are some programs out there that can't be computed. Gödel's Incompleteness is basically the same thing except it's just saying that there are some mathematical truths that can never be proven to be true.
@Ezekiele Hurley I agree, I think that's why I thought this video was stupid when I first watched it years ago. It wasn't until I understood the theory behind the halting problem that I understood what this video was trying to do. I think the problem is that it attempts to give a concrete representation of a very theoretical problem
@@Axodus The only way to avoid the halting problem is to not attempt to decide on a problem that doesn't have an answer ;) Humans can do that. And that makes us superior over machines. Remember that computer from the "War Games" movie? The only way to win that game (a paradox) is not to play ;)
When she said "what you think happen if you feed X with its own blueprint?" I remembered how I felt when I started learning about how the brain works in a deeper detail.
The Halting problem is just one problem that computers can't solve, in fact, there is an uncountably infinite amount of problems computers can't solve, and we can't even describe them. At least we can sleep peacefully knowing that there's also an infinite number of problems computers CAN solve, but this amount is countable, thus decidedly smaller than the amount we can't solve.
@@SunShine-xc6dh In this context, countable is a mathematical term meaning you can describe a procedure by which you can list them all. For instance, to list all the natural numbers, simply start at 0, then keep adding 1. This gives you a countably infinite set of numbers. If you can map a set one-to-one with this countable infinite set, then that set is also countable. However, some sets are uncountable. For example, theres no way to map the real numbers one to one onto the natural numbers, so the reals are uncountable. If you'd like to learn more about this, look up the diagonalization argument for the real numbers.
@@fanrco766 Just to tweak your wording: A set is countable if you can describe a procedure for listing them, so that given enough time, you’ll reach any member of the set you want. You’ll never finish listing them, but you can pick any item in the set, and following your procedure, you’ll eventually get to it.
I guess people feel like tom scott is a bit more credible with how he explains the basis in how this problem came about? And the intuitive but incorrect answer of changing the machine itself doesn't look so obvious in his video
Partly because this came out well before Tom's video, and probably partly because of audience and how well Tom explains things/people are willing to accept what he says.
I was going to ask the same exact thing. Tom Scott cut some corners and one of the corners was that he skipped the whole photocopier! Like, what the hell? That's a crucial component and it was skipped. This video proof does it justice. I guess we'll need to offset the dislikes with more likes... but it's silly that there are that many in the first place.
@@MikehMike01 Firstly, what do you mean by that? Secondly, I don't really agree. It depends on what you're comparing with but people definitely used to accept newspaper content as truth (and, of course, it wasn't that straightforward by any margin)
It makes sense. It is simply impossible to get a machine that can magically account for any scenario. You could make a hypothetical machine, that specifically resolves the A/C machine issue. But other issues need to be handled differently
The real question is, did anyone think it would be possible to do that to begin with? I understand that this proves that point, but who needed to be proven wrong lol? I don't exactly see the value of knowing that it's impossible to create an omniscient computer, because it seems obvious. I've never taken a computer course and I know that, so idk. I do write a lot of code though, so computers aren't a total mystery to me.
@@moderator_man H isn't exactly an omniscient machine. It takes an input, a machine blueprint, and prints an output, if the machine would get stuck or not, but it doesn't need to be able to solve every problem. Since you write code, H is basically like a magical IDE that can always tell if your code could crash. Some IDEs can do that to an extent, but they will never be able to catch everything. This proves it.
@@thepiratepeter4630 but this is what I'm trying to say: I don't think anyone actually believes that was possible to begin with. I'm not disagreeing that it proves that point. I'm saying I don't think the point needs to be proven in the first place, and that it's explained poorly in the video. Who actually thought it was possible to build a machine that could do that? I've never needed to be taught this, personally. I ain't no genius by any stretch of the imagination
@@moderator_man It doesn't matter if you feel it's intuitively obvious. Good for you, but, from a mathematical/theoretical point of view, knowing for sure that this is impossible is very useful. An example: if there is another problem that you think is impossible, but you are not sure, you can just prove that an algorithm for that problem would solve the halting problem as a side effect, and now you know for sure it's impossible. Also, better be safe than sorry: imagine if this was possible, but everyone had your attitude and thought: "that sounds impossible" without even trying. That would be a dumb move right? Now we know for sure.
If H can simulate other machines, using X (which contains H) simply creates an infinite loop of H simulating itself simulating other Hs. The real H would simply get stuck, and thus never create a wrong answer, since it will never give an answer when simulating itself.
Ignore the word “simulate”. Ignore any idea you have about how H would work inside. We don’t know or care about that. All we assume is that H somehow gets the right answer. And that’s all it takes to show that H is impossible.
@@nugget4814 3:03 "H solves the halting problem perfectly. It always prints the right answer." The video is clear about this. A machine can't print the right answer if it gets stuck.
@@nugget4814 Nope. Again the use of "simulating" was misleading. Usually, this demonstration explains that H through clever algorithms has the power to determine if a specific code would get struck or would return a result. Analysing itself never was an issue. If what you take from this video is some sort of infinite recursive loop you've missed the point.
Sudden incongruence with the rest of the video. Everything earlier was some abstract "computing machine" with a formally defined function. Aaaand then there's a photocopier lol, of course you already know what that does.
A lot of people do not seem to be following the argument rigorously enough. This is a proof by contradiction; we assume something to be true, and use this assumption to arrive at a logical contradiction, thus proving that our initial assumption was incorrect. In this case, our assumption is that such a machine as H exists, with the key thing about H being that it is perfect, and *always* gives the right answer. We then use this assumption to see if we can find a logical contradiction. We might engineer a situation that seems needlessly unfair, but this is the whole idea. Once we run into the logical contradiction (the fact that H was wrong, even though it is by definition *never* wrong), we know our assumption MUST be false, our assumption being that such a machine as H exists. Nothing remains of H; even though it was just one, cleverly designed situation that it couldn't handle, the fact that it couldn't handle it, completely eradicates any trace of it. This is a very general form of proof. The realisation through a proof like this, is that the assumption you made, does not even make sense as a logical concept. Because that fact is not obvious, we have to do some work to reveal it, but if we were insanely smart, we would know that H doesn't make sense as a concept, just like we know now that a '4 sided triangle' is nonsensical. It's not that H is too hard to build, it's that it is literally an incoherent idea, but one whose incoherence is far from obvious and requires formal proof.
@The good Fellow by computer here I am pretty sure they mean Turing complete systems and since we are Turing complete systems we have those limitations too.
H can't output the right answer but it can still find it. What the problem proves is that nothing can give the right answer if it's a part of a machine that negates its answer. So basically, if there was a separated answer output not used as an input H could give the right answer.
The point of N IS to create a paradox , yes. The whole point of this video is to prove that computers can get stuck in paradoxes. This is obviously a simple, fixable example, but it's very easy to understand. Would you rather they have showed you an incredibly complicated real-world paradoxical problem and you have gotten lost in it? I hate that this video has so many dislikes because people can't stop to think about the purpose of things.
I think it would have been more useful to point out the fact that paradoxes are the incremental issue at hand. However, wouldn't you think it to be possible for a program to discern what would cause the paradox, and be able to work from there?
No, that's not what the video is about at all. The negator leads to a CONTRADICTION, showing that a certain problem is undecidable. It has nothing to do with computers and paradoxes.
If they just used the word "paradox" somewhere, it would've made it more clear. Or they could use the infamous "unstoppable force, immovable object" paradox to make it even more simpler. Or the "omnipotence paradox" - which would've tripped everyone who blindly believes in a supernatural God(Although there could a natural God).
It's a bit frustrating to see how so many people don't understand this video and think they have "simple" arguments why this doesn't work and H can exist.
Knowing their channel, and seeing that dislike bar. Yea, I'm not surprised it goes over their heads. To be fair, it does require you to pause the video and think for a moment.
Assuming that computers can both exist and get stuck (Like A and C), H can exist. Feeding X with its own blueprint will make H get stuck, as H goes through the simulation an infinite amount of times. However, it cannot feed anything to the negator, because whatever H does, H will be wrong, and H is never wrong. Either that or I just redefined what H was, thus making it a different computer entirely, thus making the conclusion correct. I'm leaning toward the latter.
The problem is that people don't see the need of machine N(the one that's causing machine H to not exist) they see H did fine without N. And frankly I don't see the need for N either. Their all thinking 'well then get rid of N and the problem is gone'
@@thomasiobst8174 Yeah you redefined it, H is supposed to never get stuck or be wrong. It's easy to make a computer that is never wrong about the halting problem, just have it get stuck whenever it can't figure it out.
1:46 I love the implication that they’re just dropping these cards on the audience But seriously, great video! I think this explains this concept really well.
Here's a simpler scenario if you don't understand: 1. Let's say there's a fortune teller that is supposed to always be able to predict and tell you the future. 2. You dare him to predict, "In 10 seconds, am I going to say Black or White?" 3. It's impossible for the fortune teller to tell you the correct answer because if he predicts Black, you can just choose to say White, and he'll have been wrong. If he predicts White, then you can just say Black and then he will be wrong. 4. Therefore it is impossible for a computer (the fortune teller) to give you the correct answer for *everything* that you can ask him (the input).
Ben I would argue that personal choices aren’t unsolvable, since the brain is physical and therefore calculable. The point is by choosing heads or tails based on what the fortune teller says, you can act as the negator
I would say it is not impossible for the fortune teller to tell you the correct answer. After all, to predict the future doesn’t mean that the answer has to be made known to the other party. A mediator could pass the message to and from the fortune teller to the other party, making it possible for the fortune teller to tell you the correct answer.
Many commentators here simply assume that the program failed due to paradox and hence computers can't solve paradoxes. The conclusion here is a bit flawed. The proof shows that existence of the solution to a problem H creates paradox X. Hence H can not have a solution. You got a problem that can't be solved, not because it's a paradox but because the solution creates paradox .
so basically a paradox? H has 2 problems, the first is that when given the blueprints, H has to simulate H, this happens over and over again, creating a loop hole or paradox, H then realizes that because of this X cannot create an output, thus giving the answer of "stuck", now the second problem, N turns "stuck" into a smile, resulting in the machine to become not stuck, beating the purpose of H. H couldn't solve the paradox in the first place as H is a computer, that is the root of the problem, thus the point to be made that the point is computers cant solve paradoxes, thus they cant do everything.
What if the machine H _doesn't have_ to simulate the other machine in order to dedide whether it will halt or not? Let's suppose the number of inputs for that machine is some set, and this set can be "mapped" in some way and divided into two disjoint subsets: inputs that halt the machine and those that doesn't. Then suppose the machine H can somehow have acces to such a "map", so it doesn't have to _simulate_ the other machine - it's enough for it to look up the list for the given input and see in which subset of inputs it is to give its answer. I don't see how the halting problem _requires_ H to _simulate_ the other machine, so it might as well not, and do such a table lookup instead. In that case, we can't assume anything about how H does what it does. And perhaps we don't have to, because the proof doesn't seem to be dependent on the way H works, only on its results.
@@bonbonpony we know exactly what H does, it purely uses a diagram to recreate (simulate) the machine then reinactes what would happen if it were to be given specific inputs, we were told it wasnt given an imput table of some sort, on top of that even if it were given one it would have to be as complicated as designing a robot to be exactly human in every way, its simply almost impossible to prepare it for everything that will come to it, especially since we cant rely that this table takes every computer into account, op top of that even if it were it will still present the same problem, its predictions are proven wrong, proving computers cant do everything. Lets put it like this the fortune teller says "i can answer whatever question you have about the future" so the customer says "in 10 seconds am i going to say black or white" the fortune teller actually looks into the future and says he will say white so then the customer says black, proving the teller wrong creating the outer layer paradox the inner layer paradox is that with the fortune teller looking into the future, what do they see, him saying black or white? on top of that the teller would have to see themselve answring either black or white, the teller sees he answers white, so the customer says black, recreating the future thus creating a loop hole or a second paradox not only will the customer prove the teller to be wrong, but there is no answer what so ever thus with computer H constanly having to simulate itself as it is apart of computer X of which H is apart of, there will be no answer, thus no output of X, so it prints stuck, N takes it and prints a smile, making a output, thus it is not stuck, beating the purpose of H since H cannout go past simulating itself, it cannot comprehend N, thus beating its purpose, thus computers cannot do everything.
This video is amazing and I am very surprised by all the hate and confusion it has received over the years. I find it particularly surprising that there are people who believe the inverter causes the problem and not H. I'll give a similar example to what the video is trying to say to make it more clear. Suppose there is an almighty machine that can always precisely predict the future. I ask the machine what time my son will finish his homework today and the machine gives an answer, e.g. 7pm. My son, however, listens in to the machine's answer and, wanting to prove it wrong, purposely finishes his homework later than the machine said. Obviously, the machine's prediction was wrong. But, the machine is supposed to always predict the future correctly, so what happened? Saying "just remove the inverter" or "the inverter causes the problem" etc. is the same as saying that the kid messed up in the above example. But, that is blatantly wrong. The kid can do whatever he wants. He has every right to listen in to the machine's answer and react however he wants. The problem is obviously not the kid, it is that the almighty future-predicting machine cannot exist. Its mere existence defies the basic principles of human logic. The same thing is true about H in the video: its mere existence is illogical and creates a paradox. The only difference is that H is slightly more subtle about it, compared to the almighty future-predicting machine.
@LegoGuy2511 If the son doesn't then the machine is correct, but if he does it's wrong. Therefore the machine is not always correct, like we assumed. The fact that it might be correct sometimes doesn't mean anything. Also, yeah, by definition we didn't assume that the machine can modify its prediction. The prediction is supposed to be final and always correct.
so your premise is that the machine always precisely predicts the future, but that literally can't be the case if it's information can be contradicted. this is why i have such a big problem with this theorum, is that it always uses wildly unrealistic examples with machines that literally would never be built or exist in reality. how does the halting problem manifest itself in a real-life tower PC, if it all?
@@moderator_man I mean, that's the whole point, that it "literally can't be the case". I explained why this machine cannot exist. It seems like you just assume that its existence is absurd (and it is), but this is a legitimate proof about why that is the case. Similarly, the halting problem is something unsolvable. It's just an example of something that you real-life tower PC could never do, no matter the technological developments. EDIT (to clarify): What exactly is your definition of a machine that "literally would never be built or exist in reality"? If you described a TV or an airplane to someone from some centuries ago, they would probably think that it's something that can never exist. However, they would be wrong, obviously. That's the whole point. The future-predicting machine CERTAINLY cannot exist. It's not that we need more technology to build it, it's just paradoxical in its nature. Other absurd things, such as teleporters or flying cars possibly could exist, even if we never see them in our lifetime. The perfect future predicting machine, on the other hand, will never exist, not in millions of years. Same goes for the halting problem machine.
@@moderator_man The halting problem manifests all the time. Sometimes PCs don't crash, they get stuck in an infinite loop and freeze completely while the architecture is unaware that it should panic or throw an error. Sometimes those conditions are detected and the computer can safely crash and save a bunch of logging data about its state for debugging but the Halting Problem tells us that there cannot exist a perfect predictor of the machine getting stuck or not. It's a very loose connection to the halting problem I admit but hopefully it makes it more grounded for the more "practical"-centered people.
catlover Iuraduri the red side would win c just plays the best it could I think that they will get stuck with no moves because each one will stay away and thus making it not stuck but an infinite loop of escaping
I think perhaps the reason many people take issue with this explanation is the title. Depending on the tone in which you read it, it could seem like it's implying "computers cannot replace humans in every task", when in reality it is saying "computers cannot solve problems with no correct answer". The video illustrates that there is a problem a computer cannot successfully solve. This is reasonable, because a person cannot correctly solve the problem, even theoretically. A person who can answer any yes or no question correctly becomes a paradox if asked "will I be standing in 10 seconds?" by someone who insists on proving them wrong.
I agree with what you say, but of what you wrote "...becomes a paradox if asked "will I be standing in 10 seconds?" by..." that paradox can be beaten if you apply to answer it on written instead of verbally to the person in question, or recorded on a video without the questioner seeing it before the end result. This will have a proper result if they will indeed be standing in 10 seconds. To make your paradox, you would have to give the answer to the questioner beforehand, therefore giving them the freedom of your result.
*compter A does arithmetic!* Me: next is B?" *Computer C Does checkers!* Me: "Wait, what? where's B?" *Computer H does the halting problem!* Me: "Oh... A for arithmetic, C for checkers, H for halting problem."
You're smarter than me, all I managed to think was C must mean checkers, A must mean... uh, A, the first one. And H must mean... feeling hungry or something. Never mind trying to solve what X means, probably eXistenz or something...
Maybe for that round. But checkers is a game where you have to think ahead. He can immediatly take back the opponents piece and is in quite a good position afterwards. In checkers it is very common that you go for 1 for 1 trades, especially early in the game. Traps where you sacrifice a piece are very common.
White has a pre-set jump limit. With this in mind, red sent wave after wave of its own men until the pre-set limit was reached, and the white team shut down.
The interesting thing is that if H existed, a whole lot of mathematics would become uninteresting. Take Fermat's last theorem. We build a machine F that systematically searches for a counterexample. If there is no such counterexample, it becomes stuck, never finishing. If we had a machine H, we could easily prove or disprove Fermat's last theorem by having it check machine F. Or the zeta function conjecture. Or lots of things. But it seems doing math can't ever be boiled down to mechanically applying some rules. Nice to know.
The existence of the machine H doesn't have anything to do with what you just stated.. You can simply look at F to see if it eventually doesn't get stuck. If you're assuming that this will take too long and machine H will quickly tell if it gets stuck or not, then there's no reason why H would compute the exact simulation of F faster than F itself. In essence, what you're saying is that if there was infinite computing power available, which machine H uses to test the infinite possibilities of Fermat's last theorem through brute force, then maths would be ruined. I agree, but thankfully no computer can compute an infinite amount of problems in finite time, so I guess we can consider ourselves lucky.
"You can simply look at F to see if it eventually doesn't get stuck." The difficulty with that is that when you are dealing with an *infinite* loop, there is no "eventually". Machine H doesn't simply run some other machine "forever" and check to see if at the end of forever it gets stuck. It does it in a finite time. That is: "then there's no reason why H would compute the exact simulation of F faster than F itself" doesn't make sense if the question is "does F run forever?".
I'll try to be more clear: Machine F runs a possibly infinite loop. We can never know if it gets stuck, because the machine runs forever. My point is that there's no way machine H could simulate machine F and give a result, since the simulation would last forever, just like the actual Machine F. Just imagine the thought bubble in the animation, where the machine runs "in the head" of the machine H. If you are in fact saying that Machine H can compute, let's say theoretically, that Machine F get's stuck after infinite trials of Fermat's Last Theorem, then either you're assuming that Machine H can complete infinite processes in finite time, which makes it not applicable to real-life, or you're saying that it has a non-brute-force method of trial and error and is more clever, which would imply that it works like a mathematician, and not a calculator.
Yes, machine H could not *simulate* machine F and get a result, but it doesn't necessarily follow that no possible machine could work out whether F gets stuck. If F is running while(true) { /* do nothing */ } I can see it runs forever without having to simulate it. Likewise, if I keep track of all the memory and state F uses and it exactly reduplicates some prior state, I can know then and there that it is stuck without having to simulate it further. That is, it's not obvious that the general case is impossible. Maybe there's a celver algorithm that can do it without actually simulating the machine, just by analyzing the code. Gödel proved that there is no such algorithm, that it actually is definitely impossible.
The problem here actually lies on a different level. In order for H to simulate X it must first be able to simulate itself since H is part of X. A computer trying to simulate itself with it's own input is logically impossible since it would end an infinite recursive loop. This is not a problem with computers. You can't blame the computer for not getting a logical answer to a problem which by definition has no logical solution to begin with. It's like asking a person "What is the answer to this question?" and expecting them to give you a logical answer.
The problem is recursion. When the answer depends on the answer you have a catch 22 in that you can't calculate the answer without having the answer. It's actually a fairly important result from CS and shows that not all functions can be computed.
TheMegatomicDragon I think you and I are using the word computation differently. The halting problem is a result of computabily theory, and says that it is possible write valid programs which can not be computed. To oversimplify, there are valid questions which cant be answered.
Hellothere _1 I agree that it would enter a loop while trying to determine what it's own output would be, but the video did seem to say that in the simulation H runs, it chooses what its own output can be, and as a result, whether or not it prints a smiley. The only thing I don't understand is why they decided to even use the N machine. It seems to me that the result of the entire X machine, it's existence, solely depends on whether or not N is used. It's akin to a person saying "Solve 4 + 5", the person solves the problem and comes up with 9, but then you tell them that the actual answer is anything but 9. It doesn't make any sense why N is even included lol
I watched this exact video many years ago and today, October 2023 I wanted to remember what the halting problem was. I *still* had the memory of this video and I was looking for it! I didn't understand other videos but this one. Very good 👍🏼.
And here is computer G: the computer that plays as a bot on CSGO. It can no scope headshot half way across de_dust2 and never stops flicking when awping.
Man if only this channel had all the stuff I needed to know for my foundations of computer science class. I struggled so hard with that class but these videos make these topics so easy to understand
GUYS. X is the term for the whole machine - the big huge combination machine. _That_ is the machine whose blueprint we're feeding back into the machine. This is the key realization I was missing. When we feed X's blueprint into itself, we're telling H exactly what the whole machine is, and the machine _still_ fucks up. The middle part of the machine, H(X,X), literally means "If this whole machine will halt at any point when we put its own blueprint through it, print so". If H produces "stuck" in that middle part of the chain, then that statement literally means "This whole big machine gets stuck when feds its own input" - yet we see that it prints that it's fine because the output is a smiley face - which means that H and the overall machine X directly contradict each other, because H said we'd be fine, even though we told it in advance that N was going to mess it all up. If, however, H produces "Not stuck", this literally means "The machine, fed with its own blueprint, will not get stuck". We see that in this case (because of N), it does indeed get stuck, even though H said that it wouldn't, even though H _knew_ that N was part of the machine it was analyzing! So H and the overall machine X yield contradictory results, proving that this machine cannot exist, yet again. We know for a fact that P and N can exist, because they're super straightforward & anyone could go write a program to do what they do in like thirty seconds. The fact that H is wrong about the whole machine that it's part of a human centipede for here proves that the only part we can't easily design ourselves _cannot_ possibly exist - and we proved it with a recursive definition of the mystery machine itself. We can't just remove N from screwing it up at the end, because all we need to do is devise _one_ instance that proves H can't exist to prove it can't exist at all. We defined the whole machine, X, as P->H->N, and that's the blueprint we fed it. We fed the machine with the blueprint of _all_ _three_ _components_ of itself, so the fact that it gets all messed up (even though it only happens _because_ of N at the end) means that H failed its own little portion of the experiment. The output from H was wrong about the machine whose information it was given. So we've proven that a perfect machine like H can't exist, by showing one situation in which it just physically could not do what it's defined to do. When you're reading a formally written statement of this proof, it's SUPER hard to wrap your head around all the interlocking components here, but the animation (and especially the frame showing everything at 6:49 ) really do help it all make more sense.
That was an excellent explanation from your side! It REALLY helped me clear up all the remaining clouds that were left after watching this video! Thank you!!
thNos: I am inevitable. H': And I am truly always right because if you are below me i will purposefully print the wrong answer *nothing happens* *N prints smile* P: *h m m m m*
It is a shame that people downvote videos they do not understand -.-. This is one of the best explanations of the halting problem and the proof of it... Great job!
It probably wouldn’t have so many downvotes if the title was “The Halting Problem: Explained” The title has the implication that there’s a realistic thing computers can’t do. Like, ok dude, computers can’t do things that are impossible, really got us.
yeah but i'm pretty sure back then people were in the state of mind that computers could "do everything". Even then, if people dislike a video because they don't like the title of the video, then yikes.
Wow i didn`t realised this video have so much dislikes. The halting problem is a real thing in computer science. For the creator: This is an awesome video and explanation. I really liked it.
Surprising. Here's a few questions. 1. Do you think people are desperately looking for solutions because we are obsessed with computers? 2. What's the song at the end? 3. What if H was designed to not always be correct? (Does its inputs correctly, but if a negator exists, it can get it wrong, just like all machines arent supposed to be perfect)
So, I guess lots of people misunderstood this video (including myself to be honest) and hence the number of dislikes. Let's break this down a little further. H: A machine that gets fed a machine's blueprint, and a certain input, and checks if this input running through this blueprint would halt or not. P: A photocopier, duplicates its input. N: A negating machine, that halts if fed "Stuck" and does not halt if fed "Not stuck" X: A combination of H, P, and N. So far, I did not say anything new to what was already said in the video, but here's the part where I think confusion occurs: The "X" machine now has two possible results: It either halts, or it does not. It should be regarded as any machine. It's a machine, it has an input, an output, and a blueprint. The "H" machine should therefore be able to process its blueprint and any input to check if this input is valid or not. Alright so, we now know the "X" machine is expected to either halt, or not. Let's feed the "X" machine _its own blueprint_ . This blueprint is then processed into the "H" machine, both as blueprint and as input. Why? Because that is what you just did. You fed the "X" machine with input: its own blueprint. Therefore the H machine should be taking the "X" machine's blueprint, as blueprint for "a machine to test" and as input fed to "that machine". Here we reach an unknown state: The output of the "H" machine isn't known, so we assume: It says the "X" machine will halt. If so, then the "X" machine by design actually does not halts, because of the component "N". But this means the "H" machine's output was wrong? Maybe this assumption is wrong, so let's assume it says the "X" machine will not halt instead. If so, then the "X" machine by design actually halts, making the "H" machine wrong again. Some might say "Well, the "X" machine's output depends on the "H" machine's output, which depends on the "X" machine's output, which dep- you get the point. It's an infinite loop". And so you said it, it's an infinite loop, i.e. it's not supposed to halt, and so the "X" machine should be able to have an output, since the "H" machine should be aware that it is an infinite loop! Some (including myself) might say "Well, this is a special case for the "X" machine cause of the stupid "N" component!" or "You can't use a modified "H" machine as input for the "H" machine!" Well the test here is to find if an "H" machine can exist for any possible program, and this theory aims to prove that the outcome of some machines or programs just can't be determined, whether they'd halt or not. It does not disprove the existence of an "H" machine entirely, rather it disproves that an "H" machine could work out any input. I hope this helps at all... For another approach (that's still quite similar) check computerphile's video: th-cam.com/video/macM_MtS_w4/w-d-xo.html
"It does not disprove the existence of an 'H' machine entirely, rather it disproves that an 'H' machine could work out any input" -- well that is the definition of the H machine, so yes it disproves its existence entirely. The point of the video is to show how and why the existence of an H machine would break logic. Therefore it literally can't exist
@@Favmir I think the problem is not not understanding the video itself, it's rather not understanding how the video's content is supposed to prove what it does
I remember when I was younger I used to post some very stupid comments in this comment section. Now I'm a CS student in the middle of my graduate studies and I feel very embarrassed. Thanks for the content folks!
@WungusBill can you explain this one to me? Because you're right, I can't get over my intuition that the negator could just be removed. I assume I'm wrong, but I don't know in what way.
@WungusBill To be honest I’m confused on what the negators purpose is in a real computer, and what it’s supposed to represent in the video. Is it supposed to represent the computer’s problem solving?
Took me awhile, but I think I get it. For anyone else like me, here's the way I see it: (X) is made to receive images, since the top part is a copier. (H) thinks "If (X) receives images, it won't get stuck." (N) negates this, and the machine gets stuck. Assuming (H) can learn from this experience and realize that being fed a blueprint specifically will cause it to get stuck, it guesses that (X) will get stuck, which it doesn't. It's a paradox. It doesn't matter how many problems (H) can solve, as long as there's one problem it can't solve, the Halting Problem is true.
H was wrong. But H is supposed to be always right. That's the problem, H can't be always right. Also, mathematical "machines" can't learn from their experiences. Msthematical "machines" also can't guess. And, we were guessing what H would output, instead of finding out what it would say, because H doesn't exist. We were just seeing what it could output. As it turns out, neither option worked.
H is possible because X wouldn't work due to N. when X gets a blueprint of X it will not jam because it would simulate its self jamming as a response. that would make H give the wrong response to N which would print out a ":-)".
I'm guessing part of the definition of H is that it never gets stuck itself? Because if it could, then getting stuck on 2 copies of X would be one way it could skate around the paradox.
if we think about this in more concrete terms, if you wanted to analyze some possibly malicious input to see if your computer would freeze forever, it wouldn't do you much good if your analyzer could also freeze this means that any such analyzer is going to have to restrict the capabilities that the inputs are allowed to use, e.g., no looping. then it can guarantee that everything will finish eventually. however this means you might reject programs that wouldn't freeze see: Berkeley Packet Filter
I watched this video several years ago and the comments were full of people who didn't understand the proof and "disagreed" with the pure formal logic presented. I'm happy to see that the more recent comments are a lot more sensible.
Same! I have no idea how the general consensus has completely flipped. I got so frustrated reading all the comments from people who didn't understand that it was a proof by contradiction.
@@ZachAttack6089 I mean it is not shown in a comprehensive manner. At least to me. They made it in a way that seemed like you could pull apart X. Even though that’s not the case??? A more concise and clear example could be made, though I have no idea what that would be considering I do not understand the problem.
@dolores youtube now prioritizes more recent popular comments, so the past narrative of this video being "wrong" is gone to time. Now new viewers decide the new narrative, which is a complete 180
@@ianmitchell9044 This is a proof by contradiction. We start by making an assumption: that H, a program which solves the halting problem, exists. Then, if a logical contradiction arises, it proves that our assumption was false. That is exactly what was done in the second half of the video. You said it seems that the only reason it doesn't work is because of N. But that's not really the point. The problem isn't that the X machine doesn't work properly. We never made the assumption that X should do...well...anything in particular. We only made an assumption about H. X is made of P, H, and N. Notice that P and N are very simple programs, basically just a single line of code each. In other words, we don't need to assume they exist, because they definitely do. But by putting P, H, and N together in that order, we create a situation wherein H is incorrect, no matter which answer it gives. This contradicts our assumption that H, defined as a program which solves the halting problem, exists. Since our assumption led to a logical contradiction, it must be false. Therefore, H cannot exist. Basically, H, as defined, is always correct. But the video presents a situation in which it cannot be correct. It doesn't matter if it's "N's fault", that doesn't matter. If a situation exists where H can be wrong, then H does not exist as it was defined.
Looking back at this video, it's really weird how incredibly emotionally charged and confused the comment section is. I mean, compare it to Tom Scott's explanation of the Halting Problem. Everyone over there seems to understand well. I wonder why this specific explanation of the Halting Problem invokes such an aggressive/defensive response in people?
I think it's because it says "proof that computers can't do everything", and people want to defend the computers. "How dare you say that! Computers can do anything they want!"
This is an infinite recursion problem that can't be solved by anyone, computer or otherwise. Obviously, a machine that has to recursively simulate itself simulating itself will fail not because of any limitations of computers, but because it's a logical paradox.
@@imaginarystranger1974 Then you missed the point. I recently saw a practical example of the halting theory. People working on the Rust compiler were trying to add the ability to define a "constant" function. You write a function that always returns the same output, mark it as such, then the compiler evaluates it at *compile time* and then replaces the whole function with the constant, calculated result. The problem occurs when your "constant function" doesn't halt. Then, the compiler would get stuck forever trying to evaluate it and it wouldn't give you a useful error. Someone in the discussion said "just have it check for infinite loops", and there was a collective facepalm as everybody reminded them of the halting theorem. Instead, they need to use workarounds like running for a certain number of cycles and assuming the code doesn't halt if it doesn't finish by then.
I know this video is 9 years old, but excellent representation of computers! very easy to understand for normal people who don't have to look at blocks of text everyday
To some people, unfortunately. There are plenty of users confused about the explanation, as we can see in the comment section. It is, in fact, a great video.
As a mathematician and computer scientist who is familiar with this problem, I would first like to say I approve of this video. Secondly, I can understand why people might think that it is a bit silly. Your first thought might be "What's the big deal? You just showed how a machine that doesn't make sense can't exist?" Well, they don't make this explicit in the video, but there actually is a formal definition for the 'blueprint' for the machines. It's so formal, actually, that you can deterministically write it down into a sequence of 1's and 0's instructions for a turing machine. Now, the original question was, given any permutation of 1's and 0's as an input, is it possible for a machine to determine whether we can definitely compute and answer or not given all the time we need? That's like a super important question, actually, because it would allow for turing complete (fully 'smart') computers to essentially know themselves and algorithms completely when given enough resources. The crazy thing is that there are 1 and 0 sequence problems which we simply cannot make a program that determines the truth for whether they stop. There's no program, no matter how complex or clever, that you can just feed any sized program and its input to see if it stops. Some people believe with good reason that the turing machine essentially represents completely computation, which means that there are finite algorithms that the world or the whole universe and all its wisdom, even magically given infinite memory, cannot determine.
I'm pretty sure these comments lowered my IQ by 10 points just from reading them. There were 3 assumptions about machines existing in the video. Number one is a copy machine, which obviously can exist. Number two is a machine that responds to stuck/not stuck messages, which obviously can exist. There was only one other assumption made in the video: that H exists. The video showed that when you make that assumption, it lets you make a machine X that breaks logic. Therefore H existing is wrong. There definitely can be machines that can do what H does some of the time, but that can't do it for EVERY input, which is the point of the video.
![[Laser] Firing squad synchronization problem](http://i.ytimg.com/vi/xV1aKUdlljU/mqdefault.jpg)
![[Laser] Firing squad synchronization problem](/img/tr.png)
"H was wrong again but H is supposed to always be right"
Never have I ever been so emotionally attached to a theoretical machine
😂
Exactly like every code I make.
Hahaha same
;(
Girls be like :
i like how a and c turn into washing machines when they're given the wrong problems
Btw: They all do, not just specifically A and C
@@melvin3509 nice. also damn where did all those likes come from
Introducing W: The Washing-machine Simulator Unit
W always gets stuck when fed an input!
Do NOT let Lily anywhere near it.
H: I'm always right.
N : I'm gonna destroy his whole career.
yes
N: I'm gonna destroy his whole existence
Amar Naga no
I dont get the point of N existing in the X equation.
@@SrSeed the fact that n exists is the reason why h cant
What I (Mechanical Engineer) was told in digital logic design: "Computers don't do amazing things. They do simple things amazingly fast." The people who break the complex problems into simple steps to be solved in this way are the ones who do amazing things.
.,.
Isn't that amazing?
Oh, and the fact that most modern cpus have TRILLIONS of transistors.. 👁👁
But AI is kinda tricky
@@Maxy.waxyyy more like 100s of millions
The sound design in this is pretty good. The simple whiffs of paper when the little dudes are putting them on the machine is a nice attention to detail.
Does anyone know the music at 3:47
@@AkariInsko we dont
@@pisspants4629 ok
@@AkariInsko Un Demonio - Perro Patan
@@KornYellow th-cam.com/video/wpwpa098dGI/w-d-xo.html
Who else felt satisfied when all the machines connected perfectly
yep
someone made it do that on purpose so there's nothing satisfying about it (but satisfiability is NP complete so what do i know)
It dissatisfied me when the two covers of X left a tiny gap
yes
same
the smugness in her voice when she said "logically impossible" is so powerful
Yes
3:48
@@smuglife64gaming21 your username fits perfectly.
@@beefyblom awsome
_it's logically impossible_ 😏
When I first watched this I thought "this doesn't prove H can't exist, it proves X can't exist." But after a look through the comments, I've realized that disproving X disproves H by extension because if H could exist, then we could theoretically build X, which was proved in this video to be impossible. Hope this helps anyone who is confused
disproves H by Xtension
I mean your argument is true, if X doent exist then H doesnt exist but the problem proves that H doesnt exist (and so X doesnt exist but that is not important).
It's the other way around, logically speaking
No it actually proves H does not exist because H was fed the blueprint of X and its answer is always wrong.
@@sassoarancione Hey guys.......umm.....I was NOT confused earlier......but NOW I'm confused (by you guys)....so thanks a lot! LOL
X=P+H+N，and it’s pretty obvious P and N exist.
"Oh dear", says H, "I hadn't thought of that", and promptly vanishes in a puff of logic.
+Fletcher Helms I hear they actually used that translation in the american version, completely oblivious that they'd ruin the joke?
Fletcher Helms
"Oh, that was easy," says Man, and for an encore goes on to prove that black is white and gets himself killed on the next zebra crossing.”
The joke is that if black is white, zebra crossings don't exist and he gets run over. I guess americans don't say zebra crossing?
+Piorn I got the joke just fine
HAH
YES HHGTTG OH YES. fourty two nerd nerd nerd fall at the ground and miss sorry for the inconvenience white mice dolphins humans AAAAGH
I love how when the machine gets stuck it slowly starts to move like when a vibrating phone is on a table lol
old washing machines
@@CorporateShill ok true, but this guy was just making a joke lol no need to worry haha
@@CorporateShill every mathematics problems are made up :^)
@@CorporateShill are you facepalming because these people liked the animation in the video
yes
Later in 3019...
Robot: Let's assume that humans are useful
exactly lol
haha...ha...
wait.
Hahaha
@KvAT What means "biological"?
And then.... THE PROOF THAT HUMANS CAN'T DO EVERYTHING
"H was wrong again but H is supposed to always be right"
that just hits me in the heart, so emotional..
The betrayal 🤯
H doesn't exist? So it's The Alting Problem
actually it would be "te alting problem"
Crazy Vaclav: Put it in " "!
Stranger Danger Jake So that’s why I can’t work my alt key
Lmao
@@liamdoinsomething6017 commit alt+f4
Am I the only one that feels so bad for H? “H was wrong yet again, but H is supposed to always be right” like damn
Maybe H is just suffering from having such high expectations. Give the man a break, he was right every time until we actively did everything we could to confuse him. My man deserves better than this
@@bubbsterr4967 I've seen people get emotionally attached to hipothetical, not actually existent characters. But I feel like it's on a whole new level to get attached to a hipothetical, non existent character that not only doesn't exist, it also cannot possibly exist
@@tkaine7983 you are heartless
i know right? this video is the saddest video ever. H is suppost to be right!
Besides the pressure to always be right, they immediately tell him that he cannot exist because he's made a mistake, pretty brutal if you ask me.
Note that this doesn't mean we can't build a version of H that solves the Halting Problem _really well_ but not perfectly.
Just don't use N
@@Sleestiq
That is not how logic works
If in one case it's wrong, it's not perfect.
Or that we can't build a useful machine that is less capable than a Turing Machine for which a Turing Machine can solve the Halting Problem.
In baba is you's case, it checks to see if it has gone through 200 instructions in one movement. If so, cue the infinite loop screen.
@@want-diversecontent3887 The problem here is that the blueprint of X, which gets fed to H, contains H itself. With any other input, this can work, however, this would cause an infinite recursion, causing it to get stuck. This isn't a flaw in H, it's a flaw on X.
Also, "if it doesn't work in one case it can't work in any case" simply isn't true.
About twice a year I come back to this video to watch again. I forget some aspects of the concept, but the way that they explain each axiom regarding the usage and logic of these examples is so interesting.
Yesss same here
H: “Eat your food”
N: “No”
H: “Ok, then go to bed without dinner”
N: “No” *starts eating*
underrated comment
What really happened:
N: "No"
N: "No" *starts eating*
@@no-one-1 Why
@@theodriggers549 because H doesnt exists and N is a patient in the crazy-house .... sry for my english
N is literally me when I was a teenager 😭😭😭
So it seems like a common misunderstanding among commenters here is thinking that machine X is merely "broken" or that it "fails". That is not what happens in this proof. X is not merely a broken machine, but a _full on paradox._ It's not that X does the wrong thing, it's that neither "halts" nor "doesn't halt" is a logically consistent answer for what X does. This is a contradiction, not merely a broken machine. That's why you can't just "remove the negator" or do anything else to fix X. X itself is a machine that cannot exist, and since every component besides H can obviously exist, and the way they are connected is together obviously fine, that leaves H as the impossible component.
If X cannot exist, then H cannot exist, and so there is no algorithm that can solve the halting problem for all inputs.
Also consider that the H part of the x machine’s operation when fed its own blueprint would require infinite processing power to be accurate, because it would have to simulate an infinite nesting loop of X machines being fed their own blueprints and simulating themselves. Strange that wasn’t mentioned in the video.
@@canon-de-75 Well, it’s not mentioned in the video because it’s not true. There is no assumption that H has to actually evaluate its input step by step (in fact, we can immediately rule that out, because a machine that worked that way wouldn’t _ever_ be able to detect non-halting programs). The question is whether a machine can do some kind of clever analysis to solve the halting problem, sidestepping the problem of infinite evaluation time, and the answer the proof gives us is “no”.
The beauty of this proof is that you don’t have to figure out _anything_ about how H would actually do its job. Simply by its definition, we can see that it’s logically impossible. We don’t have to think about how much processing power it would take, or how it would reason about its inputs. All we have to know is “solves the halting problem”, and we can immediately demonstrate that it’s impossible. And that’s also why this is so useful. We can take other problems and notice that they have the “shape” of solving the halting problem, and if we can prove that connection, we can show that those problems are also unsolvable - again, sidestepping any further reasoning about how a machine would try to solve those problems.
@@chaumas One thing I've always wondered about this proof is, what happens if we remove the assumption that machine H is, itself, a Turing device? In other words, what if we prove the existence of algorithms that exist, but cannot be represented with Turing-compatible logic? Then this particular proof would break, since it would be plausible for H to analyze only Turing algorithms, machine X cannot be assembled in the first place, and nobody is implying that there exists a Turing algorithm for solving the halting problem of Turing algorithms.
Or what if we go the other way, and say that H can analyze code that only runs on some subset of its own code? Even if we had a single opcode that is required for H to run, yet H cannot analyze any code which includes that opcode, does the proof still hold true?
Kind of like when someone says "3 * 0 = 2 * 0, divide both sides by 0, we get 3 = 2!" we do not say "we've proven division cannot exist!" but instead we say "DON'T DO THAT!"
The proof does not disprove the possibility of H existing. It only disproves the possibility of an H that, itself, cannot halt.
@@rawlaalawr9009 Yeah, you can solve the Halting problem over Turing machines using something more powerful than a Turing machine, as I understand it. There’s a whole subfield of study about hypothetical machines that can execute a countably infinite number of steps in a finite amount of time. I’m not super well versed on this topic. We have no reason to believe that anything close to these machines is physically possible, so it’s getting way out into the realm of theory for theory’s sake. But my understanding is that while these hypothetical machines can decide the halting problem over Turing machines, they have their _own_ halting problem which is similarly undecidable by themselves.
@@chaumas I thought so. Now that I think more deeply about it, the thing that bothers me most about the classic proof is that it fails to produce an algorithm that cannot be analyzed. It only ever ends up saying "This algorithm cannot exist, because it contains itself, which is an algorithm that cannot exist". Which... well, isn't actually saying anything substantial, is it?
It seems like a more intuitive way of proving the halting problem impossible to solve, is to write a working algorithm which is impossible to analyze. Rather than the classic proof, which only defines, then subsequently fails to provide, an algorithm which cannot be analyzed. So I wonder, does there exist a block of C++ code that works, produces expected results with certain inputs, yet becomes utterly indeterminate when given other inputs? I feel like I've run into these before. The game of life comes to mind, which can apparently simulate itself.
But when you force the problem into the realm of practicality, you by necessity need to introduce limitations. Given infinite memory, the game of life might be indeterminate for some inputs... but do any such inputs exist if we limit the size of the board, and say the program will halt if it tries to overflow? And if there exist no such inputs, is a purely theoretical H-solver of any use to us whatsoever, when every single working system in the world operates under definable constraints?
All of the people saying that you have to just “remove h or n from the problem” are COMPLETELY missing the point. The point isn’t “how do we make a computer that doesn’t mess up/halt”, it’s “is there a case where a computer can’t solve a problem”. The fact that people are specifically saying to remove something from the equation to work are PROVING that the halting problem is true. That’s why we can’t just remove n or h from the problem, if x is a computer that can logically exist but h fundamentally causes it to not provide a logical solution, that in itself is a contradiction. If we didn’t have the need to remove it, there would be no problem and it would theoretically be possible for computers to do everything. But the fact that it can’t do something in a specific case proves that this is wrong via “proof by contradiction”, we assume something to be true, then say there’s a contradiction which occurs from it being true, meaning it can’t be true, and is therefore false.
I think the problem is the title uses 'everything', and uses it by a literal definition. Nothing can do everything, because not everything is possible.
But the video itself claims 'H' cannot exist because it is impossible to never be wrong, which is untrue. 'H' would simply get stuck, and therefore not be incorrect. It likely would do this before even arriving at the negator since it isn't possible for something to perfectly simulate itself and something else without having infinite complexity.
@@Pihsrosnec The definition of H is a machine that is perfect in solving the halting problem. If perfection cannot be achieved, then H cannot exist, proving the video's point yet again.
I have a stick that can be on the moon but I didnt put it on the moon so sticks cant be on the moon.
@@Quasar0406 a better comparison is "all sticks are on earth" "there is a stick on the moon" "well just ignore that one"
@@Quasar0406 It's more like:
I have a stick that can be anywhere. I use logic to prove it can't be in place A. If my logic is valid, then the assumption that the stick can be anywhere is false. Therefore any sticks that "can be anywhere" cannot exist.
Why does this matter? Because reducibility.
There's a trick you can pull in mathematics where you can "reduce" one problem to another, which basically means "If this problem can be solved, than this other problem can also be solved". Since we know the Halting Problem is unsolvable, it's impossible for any other solvable problem to reduce to it. So if the problem you're trying to solve is reducible to the Halting Problem, you should just give up now because you're never going to find a solution.
This can catch even very smart computer scientists off guard sometimes, because there are a lot of problems that really feel like they should be solvable, but end up being reducible to the Halting Problem.
interesting. what would be the reduction in words (instead of saying it reduces to the halting problem). I mean, what is exactly the contradiction or the unsolvable aspect of this problem? Is it that if you wondering if your machine can get every answer right it wont or what? i cant figure out
@@LuckLekLeo I'm not entirely sure what you're asking, but maybe an example will help.
Wang Tiles (en.m.wikipedia.org/wiki/Wang_tile ) are a type of square tile with colored glue on each side. To fill a grid with Wang Tiles, the colors of adjacent tiles need to match. So if you're given a specific set of Wang Tiles and a grid with a specific size, is it possible to fill the grid completely with valid tiles?
Now, some combinations of tiles will obviously fail. It's not hard to deliberately pick a tile set and grid that makes this impossible. Likewise, some combinations are obviously possible. If you include a Wang tile with the same color on all 4 sides, you can just repeat that tile on every square of the grid and easily fill it up. But let's say you don't know in advance what tiles or grid shape you're going to be given. Can you write an algorithm that, no matter what combination you give it, will spit out a "Yes" or "No" answer telling you whether or not the grid can be tiled?
This, as it turns out, cannot be done. People have demonstrated (using some pretty creative math) that if a Wang Tile decider machine *could* be made, you could use it to solve the Halting Problem. And since the Halting Problem is unsolvable, then the Wang Tile problem is also unsolvable. It doesn't look like it has anything to do with the Halting Problem at first glance, but math takes some weird twists and turns sometimes.
@@hoodiesticks it helped to elucidate perfectly, thanks you very much
@@hoodiesticks Doesn't this require an infinite grid? Any finite grid could be bruteforced
@@galoomba5559 For the sake of this problem, you don't know what grid you'll be given. It could be finite, it could be infinite. But yes, a finite grid could be easily brute-forced, and for that reason most formulations of this problem restrict it to an infinite grid.
"What won't be your next sentence?" the engineer asked the all-powerful computer.
Underrated comment
"I'm lying"
the computer takes the problem but doesn't solve it: "nice try, yuno"
"Your question" answered all-powerfull computer.
Ah My head hurts!!
So, basically, all we need is a machine that when gets "stuck" with an unsolvable task will just drop a "well, who cares anyway?" and goes on with a wrong solution sequence picked randomly until it says "Ah, f*ck, my mistake" and tries something else.
Yep, perfectly human.
I already know about that machine. Sadly it would take 9 months to make and years to improve it’s quality. It’s called a human.
@@Han_Solo6712 yeah also did you know those machines are very flammable so don't be AHEM do be careful
@@Wondercool923 yeah. I’m sorry if I sounded disrespectful I was exaggerating.
Wheatley moment
@@corbsshas2811
GLADoS: This sentence is false! (To self) DON’T THINK ABOUT IT. DON’T THINK ABOUT IT. DON’T THINK ABOUT IT....
Wheatley: Ummmm... yes.
(SECOND PARA IS IMPORTANT, don't skip)
A lot of people do not seem to be following the argument rigorously enough. This is a proof by contradiction; we assume something to be true, and use this assumption to arrive at a logical contradiction, thus proving that our initial assumption was incorrect. In this case, our assumption is that such a machine as H exists, with the key thing about H being that it is perfect, and always gives the right answer. We then use this assumption to see if we can find a logical contradiction. We might engineer a situation that seems needlessly unfair, but this is the whole idea. Once we run into the logical contradiction (the fact that H was wrong, even though it is by definition never wrong), we know our assumption MUST be false, our assumption being that such a machine as H exists. Nothing remains of H; even though it was just one, cleverly designed situation that it couldn't handle, the fact that it couldn't handle it, completely eradicates any trace of it. This is a very general form of proof.
The realisation through a proof like this, is that the assumption you made, does not even make sense as a logical concept. Because that fact is not obvious, we have to do some work to reveal it, but if we were insanely smart, we would know that H doesn't make sense as a concept, just like we know now that a '4 sided triangle' is nonsensical. It's not that H is too hard to build, it's that it is literally an incoherent idea, but one whose incoherence is far from obvious and requires formal proof.
This was originally commented by -
J Thomas
7 months ago (edited) (256 likes)
th-cam.com/channels/Tq8Xel3cF7GYnIxBBBhM9Q.html
thought it should not get lost in all the trifle jokes .....
I dont understand what H is but this video is really long and i dont want to watch it...
I want a tldr for the video snd i dont know who to ask. This was a very interesting comment regardless of my lack of understanding though
@@dracibatic2433 well it really is not that easy and 8 minutes are not that long compared to an whole lecture for a semester about computation and complexity that we have to take at our university
@@dracibatic2433 I'm a CS student and, r u fkin kidding me? You hadn't 8 minutes to watch what spoon-feeding looks like.
Hansel D'silva yes
I mean, i JUST spent 8 minutes watching a kurzgesagt video, so i guess that says a lot about me
William McDougal this video IS a tldr
Expectation: "It will always print the correct answer."
Reality:
INSTALLED INK CARTRIDGE CANNOT BE RECOGNIZED
OUT
OF
CYAN
*OUT*
*OF*
*CYAN*
*Incompatible* *Ink* *cartridges*
Black
[ Buy Now ]
But the really question can H play crysis
That's funny man
r/ihadastroke
I only jusy noticed that
Can it play minecraft with 4k Shader?
damej elyas If H existed, it could detect if other computers lock up when trying to play Crysis. It probably can't tell if that other computer will actually play Crysis fail to play Crysis or outright refuse to play Crysis. Only if it will actually freeze up if you feed it a copy of Crysis and the player input.
4:52 "this simple machine is called the negator"
Programmers: !
normal input: e or u
negator: ē or ū
lol
@It's Ken ! is a negation operator !(true) = false
False!
@@jonathanhanna9459 thatsifjdkofdsyhjnferhwiehfgbewhfoewienfocjshnfkeihfnrjokdpqadnoebfejsdhieuodshgiojnxbizgaopskjmnerbgidfhsuo
Exam Question: "Explain The Halting Program"
Answer: "H get stuck when you feed it with X"
PASS
Sure, just mention what they H & X are above
@Reggie Madison Did you watch the video?
😂 😂 😂 😂
It’s more like, if you feed X and X, H will make a contradiction, proving H cannot exist. Nothing gets “stuck” because H is stated to never get stuck, and the state of X is ambiguous.
You can program a computer system when it detects that the problem would create a logic loop that is unnecessary. Or if it would get stuck that it would just say the program is not compatible with the machine/software
it’s crazy how 9 year olds think they’ve solved a problem that’s been studied by experts for years
unfortunately i was one of those 9 year olds when i first watched this 10 years ago
Fun fact: the dislikes are all 12,000 H machines disliking before they disappear
Their dislikes have now faded with them (unless you have the return dislike extension)
yah just dont hald lmao
@@thatguybrody4819 I don't like it when TH-cam removed the dislike feature. Not a big fan. Now I can't tell if it's a good video or not. Lol
@@JonathanSteadman2003 This is one of the few TH-cam videos where a high number of dislikes actually indicates ignorant viewers, not a bad video. Seems to be more common with science videos unfortunately.
@@JonathanSteadman2003 dislikes were kinda meaningless.
And if a video was really disliked you can easily get to that conclusion when reading the top few comments.
This is gold! For anyone struggling with the abstractions in theoretical computer science courses, this video would be a treasure! I wish I watched it when I was struggling to grasp the abstraction. Thank you very much for this amazing animation. I bet it takes a lot of time put it all together.
This is an infinite recursion problem that can't be solved by anyone, computer or otherwise. Obviously, a machine that has to recursively simulate itself simulating itself will fail not because of any limitations of computers, but because it's a logical paradox.
@@Greg-ku7rn even if it wasnt a logical paradox, we cannot build a computer with infinite memory and infinitely fast processing power, so both reasons prove the Halting theorem
@@trustytrojan But isn’t this solved by Ai rules? Like rather than comparing EVERYTHING it has “neurons” at distances measured by weights. In that case it might not be able to answer PERFECTLY because even we haven’t defined anything perfectly?
@@trustytrojan Is it relevant if we can record the speed of light by using multiple cameras? This question is really breaking me lol, is it because we can’t perfectly define the weights of something to a computer or it can’t discover this on its own
@@Gomer._. to be perfectly honest, bringing the topic of artificial intelligence to programming theory is just a bit extra; probably cause i don't know a thing about ai theory 😂
ive seen this video at various points in my life. i like how i understand it more and more each time
I saw this vid for the first time when I was in middle school and I thought it was stupid. Now I'm a TA for a theoretical CS course
same bro same , each time i learn something new about the turing test
It makes no sense... why do you even need a negator
@@austinpage9463 The idea behind the video is that there's a counterexample to the idea that machines can solve everything.
@@airmanon7213 and?
basically the halting problem in a machine that negates itself is the same as "This sentence isn't true", thats so cool and interesting
Yeah it's so dumb
I noticed that. It's a paradox.
Me: it has a real decent animation for a video make in 2008
Me: *Realizes 8 years ago was 2014 and not 2008*
when you realize youre older than you think
like man
im 14 and i though i was 14
Dude this was a nice animation in 1994 during mortal Kombat and the birth of clippy. It looks stupid and the theory is very very simple.
I remember watching this video years ago and thinking it was stupid. Now I’ve actually taken some CS courses in college and I finally understand lol
@@LegendLength Goebbels Incompleteness? ಠ_ಠ
This video IS stupid and pointless..
@@LegendLength To my understanding, the point is just to prove that there are some programs out there that can't be computed. Gödel's Incompleteness is basically the same thing except it's just saying that there are some mathematical truths that can never be proven to be true.
@Ezekiele Hurley I agree, I think that's why I thought this video was stupid when I first watched it years ago. It wasn't until I understood the theory behind the halting problem that I understood what this video was trying to do. I think the problem is that it attempts to give a concrete representation of a very theoretical problem
@@mattrowlands5751 ok troller
R.I.P.
"H"
2013-never
"Won't be missed, because never existed"
you deserve all the thumbs
sounds kinky
R.I.P.
"Humans"
2013-never
"Couldn't solve paradoxes either so I guess we never exist too huh.."
why can paradox's not remain unsolved? that sounds ridiculous
@@Axodus The only way to avoid the halting problem is to not attempt to decide on a problem that doesn't have an answer ;) Humans can do that. And that makes us superior over machines. Remember that computer from the "War Games" movie? The only way to win that game (a paradox) is not to play ;)
I remember when I learned the Halting problem isn't named after some guy, it literally just means "the problem about halting", I felt so stupid.
you save me
2:11 my last 2 brain cells during the test
You made my day, thanks you.
What makes it better is that the guy is just watching them fail
LIKED
Does anyone know the music at 3:47
@@_deletus_ the guy is the third brain cell being confused why they are confused.
Argue all you want about the logic, but we can all agree that the sound the computers make when spitting out paper is really nice.
Agreed
No need to agree about the logic either, which works. It's just that some people don't get it
When she said "what you think happen if you feed X with its own blueprint?" I remembered how I felt when I started learning about how the brain works in a deeper detail.
If the brain were so simple that we could understand it, we would be so simple that we could not understand it!
I don't see anything - Bernard
that's unfortunate. i can understand how my useless brain works
@@hiigari5218 then your brain is bad
@@alejotassile6441 Sense knowledge stored as compact trees via neurons that react to stimuli. That's me guess.
The Halting problem is just one problem that computers can't solve, in fact, there is an uncountably infinite amount of problems computers can't solve, and we can't even describe them. At least we can sleep peacefully knowing that there's also an infinite number of problems computers CAN solve, but this amount is countable, thus decidedly smaller than the amount we can't solve.
True, but the set of problems that can't be written down is arguably pretty uninteresting in most contexts humans care about.
Infinite is by definition always uncountable...if I can count it its not infinite it is just some arbitrarily large number
@@SunShine-xc6dh no, the natural numbers are countably infinite, with time you could count them.
@@SunShine-xc6dh In this context, countable is a mathematical term meaning you can describe a procedure by which you can list them all.
For instance, to list all the natural numbers, simply start at 0, then keep adding 1. This gives you a countably infinite set of numbers. If you can map a set one-to-one with this countable infinite set, then that set is also countable.
However, some sets are uncountable. For example, theres no way to map the real numbers one to one onto the natural numbers, so the reals are uncountable.
If you'd like to learn more about this, look up the diagonalization argument for the real numbers.
@@fanrco766 Just to tweak your wording: A set is countable if you can describe a procedure for listing them, so that given enough time, you’ll reach any member of the set you want. You’ll never finish listing them, but you can pick any item in the set, and following your procedure, you’ll eventually get to it.
Why do this video get so many dislikes compared to Tom Scott's video when they're basically saying the same thing?
I guess people feel like tom scott is a bit more credible with how he explains the basis in how this problem came about? And the intuitive but incorrect answer of changing the machine itself doesn't look so obvious in his video
Partly because this came out well before Tom's video, and probably partly because of audience and how well Tom explains things/people are willing to accept what he says.
I was going to ask the same exact thing.
Tom Scott cut some corners and one of the corners was that he skipped the whole photocopier! Like, what the hell? That's a crucial component and it was skipped. This video proof does it justice. I guess we'll need to offset the dislikes with more likes... but it's silly that there are that many in the first place.
people are much more conditioned now to blindly accept what the internet tells them
@@MikehMike01 Firstly, what do you mean by that? Secondly, I don't really agree. It depends on what you're comparing with but people definitely used to accept newspaper content as truth (and, of course, it wasn't that straightforward by any margin)
A machine that always gets stuck can never be wrong
Damn thats right
... and never be right.
A machine that always gets stuck is also not machine H
That means its stuck. Meaning computers cant replace humans.
... and never be USEFUL.
An imperfect halting machine can exist. A perfect one cannot. Therefore computers can’t do everything. That’s all this video is saying.
The proof to the unsolvability of this problem is by contradiction
킹늅 i don’t think you understand
Finally, someone who gets this.
Are there people who don't understand the video?
Can something even do everything?
It makes sense. It is simply impossible to get a machine that can magically account for any scenario. You could make a hypothetical machine, that specifically resolves the A/C machine issue. But other issues need to be handled differently
The real question is, did anyone think it would be possible to do that to begin with? I understand that this proves that point, but who needed to be proven wrong lol?
I don't exactly see the value of knowing that it's impossible to create an omniscient computer, because it seems obvious. I've never taken a computer course and I know that, so idk. I do write a lot of code though, so computers aren't a total mystery to me.
@@moderator_man this is basically just a counter example saying there are thigg by a computers can’t do.
@@moderator_man H isn't exactly an omniscient machine. It takes an input, a machine blueprint, and prints an output, if the machine would get stuck or not, but it doesn't need to be able to solve every problem. Since you write code, H is basically like a magical IDE that can always tell if your code could crash. Some IDEs can do that to an extent, but they will never be able to catch everything. This proves it.
@@thepiratepeter4630 but this is what I'm trying to say: I don't think anyone actually believes that was possible to begin with. I'm not disagreeing that it proves that point. I'm saying I don't think the point needs to be proven in the first place, and that it's explained poorly in the video. Who actually thought it was possible to build a machine that could do that? I've never needed to be taught this, personally. I ain't no genius by any stretch of the imagination
@@moderator_man It doesn't matter if you feel it's intuitively obvious. Good for you, but, from a mathematical/theoretical point of view, knowing for sure that this is impossible is very useful. An example: if there is another problem that you think is impossible, but you are not sure, you can just prove that an algorithm for that problem would solve the halting problem as a side effect, and now you know for sure it's impossible. Also, better be safe than sorry: imagine if this was possible, but everyone had your attitude and thought: "that sounds impossible" without even trying. That would be a dumb move right? Now we know for sure.
Ok so, a is for arithmetic, c is for checkers, h is for halting problem, so x is for... xylophone, of course
Actually,X stands for X-container.
(to me)
Also, P is for Photocopier and N is for Negator.
X stands for xisuma
....
accumulator, counter, data, and base. the first four general registers of a processor.
no, X stands for X GONNA GIVE IT TO YA
If H can simulate other machines, using X (which contains H) simply creates an infinite loop of H simulating itself simulating other Hs. The real H would simply get stuck, and thus never create a wrong answer, since it will never give an answer when simulating itself.
Ignore the word “simulate”. Ignore any idea you have about how H would work inside. We don’t know or care about that. All we assume is that H somehow gets the right answer. And that’s all it takes to show that H is impossible.
You just demonstrate that H can't work by running the machine in a simulator. The point of the demonstration is that H can't exist at all.
Yeah, no where was it mentioned that H can not simply get stuck. This is the most logical outcome I think: H gets stuck simulating itself.
@@nugget4814 3:03 "H solves the halting problem perfectly. It always prints the right answer." The video is clear about this. A machine can't print the right answer if it gets stuck.
@@nugget4814 Nope. Again the use of "simulating" was misleading. Usually, this demonstration explains that H through clever algorithms has the power to determine if a specific code would get struck or would return a result. Analysing itself never was an issue. If what you take from this video is some sort of infinite recursive loop you've missed the point.
For some reason, "This is a photocopying machine" is really funny to me.
Does anyone know the music at 3:47
Dunno why you're asking in a random comment but here it is
th-cam.com/video/wpwpa098dGI/w-d-xo.html
@@TheMrLaito oh cool, thanks.
“This is a bucket.”
Sudden incongruence with the rest of the video.
Everything earlier was some abstract "computing machine" with a formally defined function.
Aaaand then there's a photocopier lol, of course you already know what that does.
love how it goes from computing to quantum phylosophy in one phrase
No, there's nothing quantum about this. These are simple, deterministic machines. What this proof shows is just a contradiction.
@@chaumas Mate, I think you’ve missed a joke.
@@chaumas😂😂😂😂 some people take stuff to serious
@@chaumas"QED"
@@chaumas dude is too literal, like a computer
So if we turn all our rubbish into an H machine, it will disappear in a puff of logic
But you can't
We can try but H is a machine that is always right but it got it wrong so H cannot be built but a close replica can
@@allencao4579 r/woooosh
@@j.hawkins8779 r/ihavereddit
@@_TedKaczynski *nnnnoooooooo*
A lot of people do not seem to be following the argument rigorously enough. This is a proof by contradiction; we assume something to be true, and use this assumption to arrive at a logical contradiction, thus proving that our initial assumption was incorrect. In this case, our assumption is that such a machine as H exists, with the key thing about H being that it is perfect, and *always* gives the right answer. We then use this assumption to see if we can find a logical contradiction. We might engineer a situation that seems needlessly unfair, but this is the whole idea. Once we run into the logical contradiction (the fact that H was wrong, even though it is by definition *never* wrong), we know our assumption MUST be false, our assumption being that such a machine as H exists. Nothing remains of H; even though it was just one, cleverly designed situation that it couldn't handle, the fact that it couldn't handle it, completely eradicates any trace of it. This is a very general form of proof.
The realisation through a proof like this, is that the assumption you made, does not even make sense as a logical concept. Because that fact is not obvious, we have to do some work to reveal it, but if we were insanely smart, we would know that H doesn't make sense as a concept, just like we know now that a '4 sided triangle' is nonsensical. It's not that H is too hard to build, it's that it is literally an incoherent idea, but one whose incoherence is far from obvious and requires formal proof.
This comment is gold
Wow, thank you very much, I finally understood everything
Beautiful explanation.
@The good Fellow by computer here I am pretty sure they mean Turing complete systems and since we are Turing complete systems we have those limitations too.
H can't output the right answer but it can still find it. What the problem proves is that nothing can give the right answer if it's a part of a machine that negates its answer.
So basically, if there was a separated answer output not used as an input H could give the right answer.
H: **exists**
N: Oh, I don't think so.
For anyone wondering, the name of the song is " Un Demonio (feat. Mala K) " (Perro Patan)
Thank you
The point of N IS to create a paradox , yes. The whole point of this video is to prove that computers can get stuck in paradoxes. This is obviously a simple, fixable example, but it's very easy to understand. Would you rather they have showed you an incredibly complicated real-world paradoxical problem and you have gotten lost in it? I hate that this video has so many dislikes because people can't stop to think about the purpose of things.
I think it would have been more useful to point out the fact that paradoxes are the incremental issue at hand. However, wouldn't you think it to be possible for a program to discern what would cause the paradox, and be able to work from there?
No, that's not what the video is about at all. The negator leads to a CONTRADICTION, showing that a certain problem is undecidable. It has nothing to do with computers and paradoxes.
Depending on what definition you're going by, a paradox can refer to 'a contradicting conclusion.'
If they just used the word "paradox" somewhere, it would've made it more clear. Or they could use the infamous "unstoppable force, immovable object" paradox to make it even more simpler. Or the "omnipotence paradox" - which would've tripped everyone who blindly believes in a supernatural God(Although there could a natural God).
H: Stuck
N: No u
that's an underrated comment right there
Adir Barak It’s not overrated. Do you even know what “underrated” means?
H: not stuck
N:
N:
It's a bit frustrating to see how so many people don't understand this video and think they have "simple" arguments why this doesn't work and H can exist.
Knowing their channel, and seeing that dislike bar. Yea, I'm not surprised it goes over their heads. To be fair, it does require you to pause the video and think for a moment.
Assuming that computers can both exist and get stuck (Like A and C), H can exist. Feeding X with its own blueprint will make H get stuck, as H goes through the simulation an infinite amount of times. However, it cannot feed anything to the negator, because whatever H does, H will be wrong, and H is never wrong.
Either that or I just redefined what H was, thus making it a different computer entirely, thus making the conclusion correct.
I'm leaning toward the latter.
The problem is that people don't see the need of machine N(the one that's causing machine H to not exist) they see H did fine without N. And frankly I don't see the need for N either. Their all thinking 'well then get rid of N and the problem is gone'
@@thomasiobst8174 Yeah you redefined it, H is supposed to never get stuck or be wrong. It's easy to make a computer that is never wrong about the halting problem, just have it get stuck whenever it can't figure it out.
@@andrewsauer2729 Aka being semidecidable instead of decidable
1:46 I love the implication that they’re just dropping these cards on the audience
But seriously, great video! I think this explains this concept really well.
Looks like they're dropping the cards on the orchestra
@@barneylaurance1865 yeah
Here's a simpler scenario if you don't understand:
1. Let's say there's a fortune teller that is supposed to always be able to predict and tell you the future.
2. You dare him to predict, "In 10 seconds, am I going to say Black or White?"
3. It's impossible for the fortune teller to tell you the correct answer because if he predicts Black, you can just choose to say White, and he'll have been wrong. If he predicts White, then you can just say Black and then he will be wrong.
4. Therefore it is impossible for a computer (the fortune teller) to give you the correct answer for *everything* that you can ask him (the input).
Brilliantly put.
Andrew Nguyen I say that is not a good example. Obviously personal choice questions like that are unsolvable...
Ben I would argue that personal choices aren’t unsolvable, since the brain is physical and therefore calculable. The point is by choosing heads or tails based on what the fortune teller says, you can act as the negator
I would say it is not impossible for the fortune teller to tell you the correct answer. After all, to predict the future doesn’t mean that the answer has to be made known to the other party. A mediator could pass the message to and from the fortune teller to the other party, making it possible for the fortune teller to tell you the correct answer.
Ben just functions the same way as in the video lol
Many commentators here simply assume that the program failed due to paradox and hence computers can't solve paradoxes. The conclusion here is a bit flawed.
The proof shows that existence of the solution to a problem H creates paradox X. Hence H can not have a solution. You got a problem that can't be solved, not because it's a paradox but because the solution creates paradox .
so basically a paradox? H has 2 problems, the first is that when given the blueprints, H has to simulate H, this happens over and over again, creating a loop hole or paradox, H then realizes that because of this X cannot create an output, thus giving the answer of "stuck", now the second problem, N turns "stuck" into a smile, resulting in the machine to become not stuck, beating the purpose of H. H couldn't solve the paradox in the first place as H is a computer, that is the root of the problem, thus the point to be made that the point is computers cant solve paradoxes, thus they cant do everything.
What if the machine H _doesn't have_ to simulate the other machine in order to dedide whether it will halt or not? Let's suppose the number of inputs for that machine is some set, and this set can be "mapped" in some way and divided into two disjoint subsets: inputs that halt the machine and those that doesn't. Then suppose the machine H can somehow have acces to such a "map", so it doesn't have to _simulate_ the other machine - it's enough for it to look up the list for the given input and see in which subset of inputs it is to give its answer. I don't see how the halting problem _requires_ H to _simulate_ the other machine, so it might as well not, and do such a table lookup instead.
In that case, we can't assume anything about how H does what it does. And perhaps we don't have to, because the proof doesn't seem to be dependent on the way H works, only on its results.
@@bonbonpony we know exactly what H does, it purely uses a diagram to recreate (simulate) the machine then reinactes what would happen if it were to be given specific inputs, we were told it wasnt given an imput table of some sort, on top of that even if it were given one it would have to be as complicated as designing a robot to be exactly human in every way, its simply almost impossible to prepare it for everything that will come to it, especially since we cant rely that this table takes every computer into account, op top of that even if it were it will still present the same problem, its predictions are proven wrong, proving computers cant do everything.
Lets put it like this
the fortune teller says "i can answer whatever question you have about the future"
so the customer says "in 10 seconds am i going to say black or white"
the fortune teller actually looks into the future and says he will say white
so then the customer says black, proving the teller wrong
creating the outer layer paradox
the inner layer paradox is that with the fortune teller looking into the future, what do they see, him saying black or white? on top of that the teller would have to see themselve answring either black or white, the teller sees he answers white, so the customer says black, recreating the future thus creating a loop hole or a second paradox
not only will the customer prove the teller to be wrong, but there is no answer what so ever
thus with computer H constanly having to simulate itself as it is apart of computer X of which H is apart of, there will be no answer, thus no output of X, so it prints stuck, N takes it and prints a smile, making a output, thus it is not stuck, beating the purpose of H
since H cannout go past simulating itself, it cannot comprehend N, thus beating its purpose, thus computers cannot do everything.
oh come on......H is trying it's best. Give it a break.
this is the only reason people dislike this video
but... it never existed in the first place... :O
a BREAK lol
This video is amazing and I am very surprised by all the hate and confusion it has received over the years. I find it particularly surprising that there are people who believe the inverter causes the problem and not H. I'll give a similar example to what the video is trying to say to make it more clear.
Suppose there is an almighty machine that can always precisely predict the future. I ask the machine what time my son will finish his homework today and the machine gives an answer, e.g. 7pm. My son, however, listens in to the machine's answer and, wanting to prove it wrong, purposely finishes his homework later than the machine said. Obviously, the machine's prediction was wrong. But, the machine is supposed to always predict the future correctly, so what happened?
Saying "just remove the inverter" or "the inverter causes the problem" etc. is the same as saying that the kid messed up in the above example. But, that is blatantly wrong. The kid can do whatever he wants. He has every right to listen in to the machine's answer and react however he wants. The problem is obviously not the kid, it is that the almighty future-predicting machine cannot exist. Its mere existence defies the basic principles of human logic. The same thing is true about H in the video: its mere existence is illogical and creates a paradox. The only difference is that H is slightly more subtle about it, compared to the almighty future-predicting machine.
@LegoGuy2511 If the son doesn't then the machine is correct, but if he does it's wrong. Therefore the machine is not always correct, like we assumed. The fact that it might be correct sometimes doesn't mean anything. Also, yeah, by definition we didn't assume that the machine can modify its prediction. The prediction is supposed to be final and always correct.
so your premise is that the machine always precisely predicts the future, but that literally can't be the case if it's information can be contradicted. this is why i have such a big problem with this theorum, is that it always uses wildly unrealistic examples with machines that literally would never be built or exist in reality. how does the halting problem manifest itself in a real-life tower PC, if it all?
@@moderator_man I mean, that's the whole point, that it "literally can't be the case". I explained why this machine cannot exist. It seems like you just assume that its existence is absurd (and it is), but this is a legitimate proof about why that is the case. Similarly, the halting problem is something unsolvable. It's just an example of something that you real-life tower PC could never do, no matter the technological developments.
EDIT (to clarify): What exactly is your definition of a machine that "literally would never be built or exist in reality"? If you described a TV or an airplane to someone from some centuries ago, they would probably think that it's something that can never exist. However, they would be wrong, obviously. That's the whole point. The future-predicting machine CERTAINLY cannot exist. It's not that we need more technology to build it, it's just paradoxical in its nature. Other absurd things, such as teleporters or flying cars possibly could exist, even if we never see them in our lifetime. The perfect future predicting machine, on the other hand, will never exist, not in millions of years. Same goes for the halting problem machine.
@@moderator_man The halting problem manifests all the time. Sometimes PCs don't crash, they get stuck in an infinite loop and freeze completely while the architecture is unaware that it should panic or throw an error. Sometimes those conditions are detected and the computer can safely crash and save a bunch of logging data about its state for debugging but the Halting Problem tells us that there cannot exist a perfect predictor of the machine getting stuck or not.
It's a very loose connection to the halting problem I admit but hopefully it makes it more grounded for the more "practical"-centered people.
Oooohh, I get it now. Thanks a ton!
So, the moral of the story is not to play a game of checkers with a calculator.
Dacoool! No.
What would happen if two c machines went up against each other who would win (if one machine had a black ant the other a red)
@@kodethecoder depends who goes first, although I'm not sure if the first or second player wins in checkers if both are playing perfectly
catlover Iuraduri the red side would win c just plays the best it could I think that they will get stuck with no moves because each one will stay away and thus making it not stuck but an infinite loop of escaping
yoo dacool?
The bowling ally screen when you get a strike
LMAO
Damn, I also remember the bowling alley condensing an entire lecture on basic computer science into one easy to watch video when I got a strike
I think perhaps the reason many people take issue with this explanation is the title. Depending on the tone in which you read it, it could seem like it's implying "computers cannot replace humans in every task", when in reality it is saying "computers cannot solve problems with no correct answer".
The video illustrates that there is a problem a computer cannot successfully solve. This is reasonable, because a person cannot correctly solve the problem, even theoretically. A person who can answer any yes or no question correctly becomes a paradox if asked "will I be standing in 10 seconds?" by someone who insists on proving them wrong.
I agree with what you say, but of what you wrote "...becomes a paradox if asked "will I be standing in 10 seconds?" by..." that paradox can be beaten if you apply to answer it on written instead of verbally to the person in question, or recorded on a video without the questioner seeing it before the end result. This will have a proper result if they will indeed be standing in 10 seconds.
To make your paradox, you would have to give the answer to the questioner beforehand, therefore giving them the freedom of your result.
You know you understand when you start maniacally laughing as soon as they say they're going to feed X its own blueprint
Gaming.
Doing this should be prohibited.
You don’t have many friends, do you?
@@kaiserredgamer8943 engineer gaming
@@cheshire1Where's the real civil engineer when you need him?
*compter A does arithmetic!*
Me: next is B?"
*Computer C Does checkers!*
Me: "Wait, what? where's B?"
*Computer H does the halting problem!*
Me: "Oh... A for arithmetic, C for checkers, H for halting problem."
Ironsnake345ify thank you.
You're smarter than me, all I managed to think was C must mean checkers, A must mean... uh, A, the first one. And H must mean... feeling hungry or something. Never mind trying to solve what X means, probably eXistenz or something...
a for arithmetic h for halting problem
then what is X
*ACH!*
Amazing animation, helped me to understand the halting problem right away. Also amazed by how smart Alan Turing was to think up such situation!
Computer Science: * shows device that breaks halting problem *
Commenters: "But if you don't make it halt you stop the problem"
*local youtube man (re)solves the halting problem*
Does anyone know the music at 3:47
@@AkariInsko
Bro I wish I did
Your FAQ link really helped me get past my discrpencies with the existence of N. Thankyou for the great content!
1:16 "C plays checkers so well it will never lose a game!"
*moves into optimal position to get taken out*
It's an equal sacrifice on both sides. Also, you sometimes need to be aggressive it games like chess and checkers.
Maybe for that round.
But checkers is a game where you have to think ahead. He can immediatly take back the opponents piece and is in quite a good position afterwards. In checkers it is very common that you go for 1 for 1 trades, especially early in the game. Traps where you sacrifice a piece are very common.
but can then take away one of the enemy's stones
Does anyone know the music at 3:47
White has a pre-set jump limit. With this in mind, red sent wave after wave of its own men until the pre-set limit was reached, and the white team shut down.
The interesting thing is that if H existed, a whole lot of mathematics would become uninteresting. Take Fermat's last theorem. We build a machine F that systematically searches for a counterexample. If there is no such counterexample, it becomes stuck, never finishing. If we had a machine H, we could easily prove or disprove Fermat's last theorem by having it check machine F. Or the zeta function conjecture. Or lots of things.
But it seems doing math can't ever be boiled down to mechanically applying some rules. Nice to know.
+Paul Murray Yep, but even if it existed, we would yet have to find an implementation of the algorithm... =)
The existence of the machine H doesn't have anything to do with what you just stated..
You can simply look at F to see if it eventually doesn't get stuck. If you're assuming that this will take too long and machine H will quickly tell if it gets stuck or not, then there's no reason why H would compute the exact simulation of F faster than F itself.
In essence, what you're saying is that if there was infinite computing power available, which machine H uses to test the infinite possibilities of Fermat's last theorem through brute force, then maths would be ruined. I agree, but thankfully no computer can compute an infinite amount of problems in finite time, so I guess we can consider ourselves lucky.
"You can simply look at F to see if it eventually doesn't get stuck."
The difficulty with that is that when you are dealing with an *infinite* loop, there is no "eventually". Machine H doesn't simply run some other machine "forever" and check to see if at the end of forever it gets stuck. It does it in a finite time.
That is: "then there's no reason why H would compute the exact simulation of F faster than F itself" doesn't make sense if the question is "does F run forever?".
I'll try to be more clear:
Machine F runs a possibly infinite loop. We can never know if it gets stuck, because the machine runs forever.
My point is that there's no way machine H could simulate machine F and give a result, since the simulation would last forever, just like the actual Machine F. Just imagine the thought bubble in the animation, where the machine runs "in the head" of the machine H.
If you are in fact saying that Machine H can compute, let's say theoretically, that Machine F get's stuck after infinite trials of Fermat's Last Theorem, then either you're assuming that Machine H can complete infinite processes in finite time, which makes it not applicable to real-life, or you're saying that it has a non-brute-force method of trial and error and is more clever, which would imply that it works like a mathematician, and not a calculator.
Yes, machine H could not *simulate* machine F and get a result, but it doesn't necessarily follow that no possible machine could work out whether F gets stuck. If F is running
while(true) { /* do nothing */ }
I can see it runs forever without having to simulate it. Likewise, if I keep track of all the memory and state F uses and it exactly reduplicates some prior state, I can know then and there that it is stuck without having to simulate it further.
That is, it's not obvious that the general case is impossible. Maybe there's a celver algorithm that can do it without actually simulating the machine, just by analyzing the code. Gödel proved that there is no such algorithm, that it actually is definitely impossible.
The problem here actually lies on a different level. In order for H to simulate X it must first be able to simulate itself since H is part of X.
A computer trying to simulate itself with it's own input is logically impossible since it would end an infinite recursive loop.
This is not a problem with computers. You can't blame the computer for not getting a logical answer to a problem which by definition has no logical solution to begin with.
It's like asking a person "What is the answer to this question?" and expecting them to give you a logical answer.
Proof that not all questions can be answered
What is the opposite of the answer of this question?
The problem is recursion. When the answer depends on the answer you have a catch 22 in that you can't calculate the answer without having the answer.
It's actually a fairly important result from CS and shows that not all functions can be computed.
TheMegatomicDragon I think you and I are using the word computation differently. The halting problem is a result of computabily theory, and says that it is possible write valid programs which can not be computed. To oversimplify, there are valid questions which cant be answered.
Hellothere _1 I agree that it would enter a loop while trying to determine what it's own output would be, but the video did seem to say that in the simulation H runs, it chooses what its own output can be, and as a result, whether or not it prints a smiley. The only thing I don't understand is why they decided to even use the N machine. It seems to me that the result of the entire X machine, it's existence, solely depends on whether or not N is used. It's akin to a person saying "Solve 4 + 5", the person solves the problem and comes up with 9, but then you tell them that the actual answer is anything but 9. It doesn't make any sense why N is even included lol
You can imagine an H that can solve H's blueprint but this shows H can not solve N's blueprint.
I watched this exact video many years ago and today, October 2023 I wanted to remember what the halting problem was. I *still* had the memory of this video and I was looking for it! I didn't understand other videos but this one. Very good 👍🏼.
And here is computer G: the computer that plays as a bot on CSGO. It can no scope headshot half way across de_dust2 and never stops flicking when awping.
+Tao Tao Ah, so bot Vitaliy.
+Tao Tao NiP bot GeT_RiGhT
Man if only this channel had all the stuff I needed to know for my foundations of computer science class. I struggled so hard with that class but these videos make these topics so easy to understand
Based pfp
GUYS. X is the term for the whole machine - the big huge combination machine. _That_ is the machine whose blueprint we're feeding back into the machine. This is the key realization I was missing. When we feed X's blueprint into itself, we're telling H exactly what the whole machine is, and the machine _still_ fucks up.
The middle part of the machine, H(X,X), literally means "If this whole machine will halt at any point when we put its own blueprint through it, print so". If H produces "stuck" in that middle part of the chain, then that statement literally means "This whole big machine gets stuck when feds its own input" - yet we see that it prints that it's fine because the output is a smiley face - which means that H and the overall machine X directly contradict each other, because H said we'd be fine, even though we told it in advance that N was going to mess it all up.
If, however, H produces "Not stuck", this literally means "The machine, fed with its own blueprint, will not get stuck". We see that in this case (because of N), it does indeed get stuck, even though H said that it wouldn't, even though H _knew_ that N was part of the machine it was analyzing! So H and the overall machine X yield contradictory results, proving that this machine cannot exist, yet again. We know for a fact that P and N can exist, because they're super straightforward & anyone could go write a program to do what they do in like thirty seconds. The fact that H is wrong about the whole machine that it's part of a human centipede for here proves that the only part we can't easily design ourselves _cannot_ possibly exist - and we proved it with a recursive definition of the mystery machine itself.
We can't just remove N from screwing it up at the end, because all we need to do is devise _one_ instance that proves H can't exist to prove it can't exist at all. We defined the whole machine, X, as P->H->N, and that's the blueprint we fed it. We fed the machine with the blueprint of _all_ _three_ _components_ of itself, so the fact that it gets all messed up (even though it only happens _because_ of N at the end) means that H failed its own little portion of the experiment. The output from H was wrong about the machine whose information it was given. So we've proven that a perfect machine like H can't exist, by showing one situation in which it just physically could not do what it's defined to do.
When you're reading a formally written statement of this proof, it's SUPER hard to wrap your head around all the interlocking components here, but the animation (and especially the frame showing everything at 6:49 ) really do help it all make more sense.
Tysm
@@brohamletmeusethishandle ♥
That was an excellent explanation from your side! It REALLY helped me clear up all the remaining clouds that were left after watching this video! Thank you!!
@@dheeraj3281 ♥
X is a machine specifically made to not work. So technically it still functioned as intended.
Error: task failed successfully
Props for chaumas for getting here everyday just to correct some peeps out there
H: Mr Stuck I don’t feel so good
thNos: This does put a smile on my page
Elian Garcia underrated comment
r/unexpectedthanos
*tanos
thNos: I am inevitable.
H': And I am truly always right because if you are below me i will purposefully print the wrong answer
*nothing happens*
*N prints smile*
P: *h m m m m*
3:45 I feel like this has meme potential
Yeah
get some meme vibes here, too
Yes
Probably because she sounds like a certain robot
Me talking to my parents about my future 3:45
It is a shame that people downvote videos they do not understand -.-. This is one of the best explanations of the halting problem and the proof of it... Great job!
I honestly didn't really get it when tom Scott explained it, but this is really well demonstrated.
edit: thanks for the reddit gold
It probably wouldn’t have so many downvotes if the title was “The Halting Problem: Explained” The title has the implication that there’s a realistic thing computers can’t do. Like, ok dude, computers can’t do things that are impossible, really got us.
yeah but i'm pretty sure back then people were in the state of mind that computers could "do everything". Even then, if people dislike a video because they don't like the title of the video, then yikes.
This seems to be more of an indication that machines are easily manipulated, which is kind of the point.
This video is pure art, I keep coming back to it.
Yeah but why
because he doesn't understand it in one go.@@atomicnumber202
Wow i didn`t realised this video have so much dislikes. The halting problem is a real thing in computer science. For the creator: This is an awesome video and explanation. I really liked it.
Thanks!
And we shall never see a response from @@udiprod ever again
No, why? I'm still around :)
Surprising. Here's a few questions.
1. Do you think people are desperately looking for solutions because we are obsessed with computers?
2. What's the song at the end?
3. What if H was designed to not always be correct? (Does its inputs correctly, but if a negator exists, it can get it wrong, just like all machines arent supposed to be perfect)
@@udiprod im sorry if i hurt your feelings but i just want some answers, we can be friends ;_;
So, I guess lots of people misunderstood this video (including myself to be honest) and hence the number of dislikes.
Let's break this down a little further.
H: A machine that gets fed a machine's blueprint, and a certain input, and checks if this input running through this blueprint would halt or not.
P: A photocopier, duplicates its input.
N: A negating machine, that halts if fed "Stuck" and does not halt if fed "Not stuck"
X: A combination of H, P, and N.
So far, I did not say anything new to what was already said in the video, but here's the part where I think confusion occurs:
The "X" machine now has two possible results: It either halts, or it does not. It should be regarded as any machine. It's a machine, it has an input, an output, and a blueprint.
The "H" machine should therefore be able to process its blueprint and any input to check if this input is valid or not.
Alright so, we now know the "X" machine is expected to either halt, or not.
Let's feed the "X" machine _its own blueprint_ .
This blueprint is then processed into the "H" machine, both as blueprint and as input. Why? Because that is what you just did. You fed the "X" machine with input: its own blueprint. Therefore the H machine should be taking the "X" machine's blueprint, as blueprint for "a machine to test" and as input fed to "that machine".
Here we reach an unknown state: The output of the "H" machine isn't known, so we assume: It says the "X" machine will halt.
If so, then the "X" machine by design actually does not halts, because of the component "N". But this means the "H" machine's output was wrong? Maybe this assumption is wrong, so let's assume it says the "X" machine will not halt instead.
If so, then the "X" machine by design actually halts, making the "H" machine wrong again.
Some might say "Well, the "X" machine's output depends on the "H" machine's output, which depends on the "X" machine's output, which dep- you get the point. It's an infinite loop".
And so you said it, it's an infinite loop, i.e. it's not supposed to halt, and so the "X" machine should be able to have an output, since the "H" machine should be aware that it is an infinite loop!
Some (including myself) might say "Well, this is a special case for the "X" machine cause of the stupid "N" component!" or "You can't use a modified "H" machine as input for the "H" machine!"
Well the test here is to find if an "H" machine can exist for any possible program, and this theory aims to prove that the outcome of some machines or programs just can't be determined, whether they'd halt or not. It does not disprove the existence of an "H" machine entirely, rather it disproves that an "H" machine could work out any input.
I hope this helps at all...
For another approach (that's still quite similar) check computerphile's video: th-cam.com/video/macM_MtS_w4/w-d-xo.html
"It does not disprove the existence of an 'H' machine entirely, rather it disproves that an 'H' machine could work out any input" -- well that is the definition of the H machine, so yes it disproves its existence entirely. The point of the video is to show how and why the existence of an H machine would break logic. Therefore it literally can't exist
Ohh yes it made sense to me! Thanks to both of you!
Honestly there's no way people unable to understand this intuitive video with visual aid would be able to understand half of what you said.
@@Favmir I think the problem is not not understanding the video itself, it's rather not understanding how the video's content is supposed to prove what it does
Goddamn I didn't think about how H's whole point of existence is that it's able to solve any problem. Thank you for the helpful perspective!
I remember when I was younger I used to post some very stupid comments in this comment section. Now I'm a CS student in the middle of my graduate studies and I feel very embarrassed. Thanks for the content folks!
Haha, it's very nice to see someone coming back to this video to say this. Good on you for admitting your past mistakes. Kudos.
character development
Lol I wanna know what you remember saying so I can have a good laugh
@WungusBill can you explain this one to me? Because you're right, I can't get over my intuition that the negator could just be removed. I assume I'm wrong, but I don't know in what way.
@WungusBill To be honest I’m confused on what the negators purpose is in a real computer, and what it’s supposed to represent in the video. Is it supposed to represent the computer’s problem solving?
Took me awhile, but I think I get it. For anyone else like me, here's the way I see it:
(X) is made to receive images, since the top part is a copier. (H) thinks "If (X) receives images, it won't get stuck." (N) negates this, and the machine gets stuck.
Assuming (H) can learn from this experience and realize that being fed a blueprint specifically will cause it to get stuck, it guesses that (X) will get stuck, which it doesn't. It's a paradox. It doesn't matter how many problems (H) can solve, as long as there's one problem it can't solve, the Halting Problem is true.
Basically...
(H): Not stuck.
(N): The exact opposite.
H was wrong. But H is supposed to be always right. That's the problem, H can't be always right.
Also, mathematical "machines" can't learn from their experiences. Msthematical "machines" also can't guess.
And, we were guessing what H would output, instead of finding out what it would say, because H doesn't exist. We were just seeing what it could output. As it turns out, neither option worked.
It’s not a paradox, it’s a contradiction
What happens if you remove N, I wonder 🧐
@@moderator_man from what?
4:50 lift / lower with your legs, and not with your back. this stick dude will have good back health in his aging years
Also it's easier to animate. :)
The music between scenes slaps
Does anyone know the music at 3:47
@@AkariInsko Darude Sandstorm I believe
@@jacobpeters5458 haha
Reading the comment section physically pains me...
I want to kill myself :(
"AHHHHW I DONT UNDERSTAND THIS" *dislikes video*
this is bad...
Reading your comment physically "pains" me too.
H is possible because X wouldn't work due to N. when X gets a blueprint of X it will not jam because it would simulate its self jamming as a response. that would make H give the wrong response to N which would print out a ":-)".
Chaumas I just wanna say again you're a legend for still responding to these 9 year olds. Big respect
I'm guessing part of the definition of H is that it never gets stuck itself? Because if it could, then getting stuck on 2 copies of X would be one way it could skate around the paradox.
That’s correct. H always answers correctly, and getting stuck would prevent it from doing that.
if we think about this in more concrete terms, if you wanted to analyze some possibly malicious input to see if your computer would freeze forever, it wouldn't do you much good if your analyzer could also freeze
this means that any such analyzer is going to have to restrict the capabilities that the inputs are allowed to use, e.g., no looping. then it can guarantee that everything will finish eventually. however this means you might reject programs that wouldn't freeze
see: Berkeley Packet Filter
If H would get stuck and 2 copies of X then that means that whole X gets stuck and that means it dosen't get stuck etc.
@@M_1024 But there would be no output.
This is a new problem altogether :D
@@BaseNAND if you can predict that X would get stuck than H can also predict it
I watched this video several years ago and the comments were full of people who didn't understand the proof and "disagreed" with the pure formal logic presented. I'm happy to see that the more recent comments are a lot more sensible.
Same! I have no idea how the general consensus has completely flipped. I got so frustrated reading all the comments from people who didn't understand that it was a proof by contradiction.
@@ZachAttack6089 I mean it is not shown in a comprehensive manner. At least to me.
They made it in a way that seemed like you could pull apart X. Even though that’s not the case??? A more concise and clear example could be made, though I have no idea what that would be considering I do not understand the problem.
@dolores youtube now prioritizes more recent popular comments, so the past narrative of this video being "wrong" is gone to time.
Now new viewers decide the new narrative, which is a complete 180
I don’t understand. Can you explain it? From what I can tell, the only reason it doesn’t work is because of the negator.
@@ianmitchell9044 This is a proof by contradiction. We start by making an assumption: that H, a program which solves the halting problem, exists. Then, if a logical contradiction arises, it proves that our assumption was false. That is exactly what was done in the second half of the video.
You said it seems that the only reason it doesn't work is because of N. But that's not really the point. The problem isn't that the X machine doesn't work properly. We never made the assumption that X should do...well...anything in particular. We only made an assumption about H. X is made of P, H, and N. Notice that P and N are very simple programs, basically just a single line of code each. In other words, we don't need to assume they exist, because they definitely do. But by putting P, H, and N together in that order, we create a situation wherein H is incorrect, no matter which answer it gives. This contradicts our assumption that H, defined as a program which solves the halting problem, exists. Since our assumption led to a logical contradiction, it must be false. Therefore, H cannot exist.
Basically, H, as defined, is always correct. But the video presents a situation in which it cannot be correct. It doesn't matter if it's "N's fault", that doesn't matter. If a situation exists where H can be wrong, then H does not exist as it was defined.
Who else hates it when your NES vibrates after putting a Wii game in?
Looking back at this video, it's really weird how incredibly emotionally charged and confused the comment section is. I mean, compare it to Tom Scott's explanation of the Halting Problem. Everyone over there seems to understand well. I wonder why this specific explanation of the Halting Problem invokes such an aggressive/defensive response in people?
I think it's because it says "proof that computers can't do everything", and people want to defend the computers. "How dare you say that! Computers can do anything they want!"
Maybe people are more likely to react this way to cute animated robots than a talking human. Nobody cares about what is said, but how it is said.
Pinocchio's nose when he says "My nose will grow":
What do you think happened to Voldemort's nose?
Nose : Ight imma head out
Nose: Confused screeching
This has an absurd amount of dislikes for what it is, glad people are appreciating it more now
This is an infinite recursion problem that can't be solved by anyone, computer or otherwise. Obviously, a machine that has to recursively simulate itself simulating itself will fail not because of any limitations of computers, but because it's a logical paradox.
Anyone who disliked didnt understand what was proved in the video
@@Greg-ku7rn That is the limitation of a computer.
@@xMrPhantofulx No, not computer. Just like we can recognise infinite recursion, computers can be programmed check for it as well.
@@imaginarystranger1974 Then you missed the point.
I recently saw a practical example of the halting theory. People working on the Rust compiler were trying to add the ability to define a "constant" function. You write a function that always returns the same output, mark it as such, then the compiler evaluates it at *compile time* and then replaces the whole function with the constant, calculated result.
The problem occurs when your "constant function" doesn't halt. Then, the compiler would get stuck forever trying to evaluate it and it wouldn't give you a useful error. Someone in the discussion said "just have it check for infinite loops", and there was a collective facepalm as everybody reminded them of the halting theorem. Instead, they need to use workarounds like running for a certain number of cycles and assuming the code doesn't halt if it doesn't finish by then.
I love how these videos are basically computer science veggie tales.
I know this video is 9 years old, but excellent representation of computers! very easy to understand for normal people who don't have to look at blocks of text everyday
To some people, unfortunately. There are plenty of users confused about the explanation, as we can see in the comment section.
It is, in fact, a great video.
@@sashagornostay2188 That's where Chaumas comes in clutch
As a mathematician and computer scientist who is familiar with this problem, I would first like to say I approve of this video. Secondly, I can understand why people might think that it is a bit silly. Your first thought might be "What's the big deal? You just showed how a machine that doesn't make sense can't exist?" Well, they don't make this explicit in the video, but there actually is a formal definition for the 'blueprint' for the machines. It's so formal, actually, that you can deterministically write it down into a sequence of 1's and 0's instructions for a turing machine. Now, the original question was, given any permutation of 1's and 0's as an input, is it possible for a machine to determine whether we can definitely compute and answer or not given all the time we need? That's like a super important question, actually, because it would allow for turing complete (fully 'smart') computers to essentially know themselves and algorithms completely when given enough resources. The crazy thing is that there are 1 and 0 sequence problems which we simply cannot make a program that determines the truth for whether they stop. There's no program, no matter how complex or clever, that you can just feed any sized program and its input to see if it stops. Some people believe with good reason that the turing machine essentially represents completely computation, which means that there are finite algorithms that the world or the whole universe and all its wisdom, even magically given infinite memory, cannot determine.
+Tim-J.Swan I wanted to calculate the proof that the halting problem doesn't exist, but I'm still too busy calculating Ack(4,5)........
+Tim-J.Swan I want you to teach me in a class. You kept my attention AND you challenged my imagination for coming up with a solution in one post.
+dannass5 My brain.
'finite algorithms' I was talking about the algorithms each being finitely lengthed, not that there are finitely many of them.
great comment and it should be stickied.
I'm pretty sure these comments lowered my IQ by 10 points just from reading them.
There were 3 assumptions about machines existing in the video. Number one is a copy machine, which obviously can exist. Number two is a machine that responds to stuck/not stuck messages, which obviously can exist. There was only one other assumption made in the video: that H exists. The video showed that when you make that assumption, it lets you make a machine X that breaks logic. Therefore H existing is wrong.
There definitely can be machines that can do what H does some of the time, but that can't do it for EVERY input, which is the point of the video.
Wow. The production value is through the roof. Felt like I was sitting in the theatre right there
3:01 i find it so stupid that the metal bar man puts the same machine blueprint in twice as if it isn’t already in there
That function (or in this case, machine) needs 2 inputs. You can't say "use the input that you already have", usually.