Proof That Computers Can't Do Everything (The Halting Problem)
Вставка
- Опубліковано 26 вер 2013
- If you disagree or get confused by this video, read this FAQ: www.udiprod.com/halting-probl...
Visit my home page: www.udiprod.com
This video gives an informal presentation of Alan Turing's Halting Theorem, a serious, highly influential result in computer science.
A few more comments on this video:
1) This video skips a lot of technicalities for sake of simplicity. There are many rigorous descriptions of this proof easily found on the web.
2) There really is an unbeatable checkers machine. See here: en.wikipedia.org/wiki/Draughts... - Наука та технологія
![[Laser] Firing squad synchronization problem](http://i.ytimg.com/vi/xV1aKUdlljU/mqdefault.jpg)
![[Laser] Firing squad synchronization problem](/img/tr.png)
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
"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 :
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
"H was wrong again but H is supposed to always be right"
that just hits me in the heart, so emotional..
The betrayal 🤯
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
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.
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.
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.
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
"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
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 ]
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
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_ 😏
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.
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
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 😭😭😭
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
You know you understand when you start maniacally laughing as soon as they say they're going to feed X its own blueprint
Gaming.
@@kaiserredgamer8943 gamer
Doing this should be prohibited.
You don’t have many friends, do you?
@@kaiserredgamer8943 engineer gaming
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
"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!!
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
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
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, 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.
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.
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
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.
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 UA-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 UA-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.
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 ua-cam.com/video/wpwpa098dGI/v-deo.html
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
Props for chaumas for getting here everyday just to correct some peeps out there
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?
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.
it’s crazy how 9 year olds think they’ve solved a problem that’s been studied by experts for years
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?
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.
(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)
ua-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
Your FAQ link really helped me get past my discrpencies with the existence of N. Thankyou for the great content!
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 👍🏼.
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.
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 been almost 11 years and people still don't understand proof by contradiction.
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
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 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
I come back to this video from time to time to see if chaumas is still fighting in the comment section.
I mean, even superheroes need rest.
It’s less like fighting at this point, and more like quietly tending a garden every few days. I’m sure the algorithm will randomly decide to start putting this video in front of tons of people again someday, and the storm will return.
@@chaumas I didn't know this can be like a chill gardening work. Impressive.
@@FAFAA-ro3ve Depends as what you're work. You might be used to that, for example as a software developer, that many people don't understand it. And that's fine
Yeah. It kinda amuses me
H는 "모든" 문제를 해결할 수 있다가 포인트입니다.
H가 포함된 X를 실행했을 때 문제가 풀 수 없다는게 증명이 됐으므로 H는 모든 문제를 해결할 수 없습니다. 다만, 부분적으로 해결할 수 있는 문제가 있을 뿐
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.
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
ua-cam.com/video/wpwpa098dGI/v-deo.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.
Chaumas I just wanna say again you're a legend for still responding to these 9 year olds. Big respect
For anyone wondering, the name of the song is " Un Demonio (feat. Mala K) " (Perro Patan)
Thank you
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?
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.
This video is pure art, I keep coming back to it.
Yeah but why
because he doesn't understand it in one go.@@atomicnumber202
Stumbling upon this video a little drunk after a long Friday of work was the best thing today. The stage assistants, curtains and music were absolutely perfect hahaha
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?
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
Sometimes i must go through these kinds of videos to witness the ignorance people may get with their belief that AI is gonna solve a contradiction
Hey now, maybe AI will figure out how to physically build a machine that executes an infinite number of steps in finite time. The Church-Turing Hypothesis _is_ just a hypothesis after all.
@@chaumas the theory of computation is just a theory ;)
"AI will replace us bro!"
😂
AI doesn’t need to be infallible, omnipotent, or capable of solving the halting problem to do incredible things. It just needs to be marginally smarter than we are.
I don’t blame you for making this mistake though. As humans, it’s hard for us to fathom an intelligence greater than our own. So much so that some even conflate the possibility with the logically impossible.
But remember; our brains aren’t magic. They’re just doing computation at the end of the day. And we’ve used our meat computers to do incredible things. Now imagine a purpose built brain, clocked at several orders of magnitude faster than the human brain. What could that achieve?
Bottom line is, if advanced AGI were impossible, the human brain wouldn’t exist
You give a group of people a math problem to solve.
You tell everyone that if they can solve the problem, they must remain silent.
You then ask everyone if they can solve the problem, and then conclude that no one can solve the problem since no one speaks up.
Yeah, such a useless video
Me: it has a real decent animation for a video make in 2008
Me: *Realizes 8 years ago was 2014 and not 2008*
Jesus I just realized. Thought is was a video of 2007 or something. 2014? What?
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.
@@Romess1 "Very simple" you say? See the 20k comments who had big trouble understanding 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)
I don't understand why the "Negator" was even added. If that wasn't included, X would work perfectly and logically. The video basically says "Computers can't do things when there is a paradox built into it" which, obviously. That's like trying to prove a point by saying "See? Bicycles CAN'T take you from point A to point B, because I built one with no wheels!"
I may be missing something, but from what I understood, this video doesn't make a very good point.
Edit - I see, I misunderstood the reasoning behind the video. Thanks for the explanation:)
If H was actually possible to build, you COULDN'T make a contradiction by adding N.
The point is not that X doesn’t work. The point is that _H_ can’t work when fed X, even though, by definition, H should work on all inputs.
The song is "Funny Business" by "Haim Mazar"
Thanks man
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.
I wonder, will we ever full figure out how our own brain works? And if that's even possible?
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
For people in the comments who claim this is entirely theoretical, I say this: it is important for a programmer to recognise when they’re attempting to solve the halting problem. It comes up in disguise in a number of questions we might like to know about the code we write.
Can you specify some of those please?
Naruto- cs.stackexchange.com/a/32853
Thank you for the link laurie :)
True! A famous problem my professor gave us was this: Can you make a program that acts as a "teaching assistant" (for lack of a better phrase). The inputs are program P and specifications S and the output should be "correct" or "incorrect" depending if the program satisfies the specifications. This program is impossible to build, because it is possible to have this specification for S: Can it halt?
@@christianchan1144 In fact, it turns out that you can't write such a program for ANY specification -- that is, even if the specification is defined in advance rather than given as an input, you can't build that program because it would have to solve the halting problem anyway (as long as the specification is about the behavior of the program and is non-trivial, meaning it's not just always true or always false for any input program).
Think about an antivirus software that can examine a program and determine if it does anything malicious. This is exactly the problem you described with a fixed specification about the behavior of the input program that is non-trivial. What happens if you give it a program to examine that never halts, that has an infinite loop or something?
Let's say it calls that program "not malicious". Now all you have to do is package together any program followed by a purposely dangerous program that you know the antivirus software will properly detect as "malicious". If the first program halts, it continues to your hardcoded dangerous program and your antivirus says "malicious"; if it doesn't halt it will never move on and it says "not malicious" as defined above. Now your antivirus has solved the halting problem for the first program, which is not possible.
If we reverse the assumption above, so that the antivirus calls non-halting programs "malicious" (it has to be one or the other), then we just use a safe program instead of a dangerous one at the end. Now if the prefixed program halts it says "not malicious" and if it doesn't it says "malicious".
Either way, the point is that there can be no perfect antivirus software because of the halting problem. You may say "well if the program it is checking never halts, then it shouldn't decide malicious or not either way" and that is exactly the point. It can't decide malicious or not for every given arbitrary program.
And this is true for any non-trivial specification, as you might imagine. This is why the halting problem is so important, because it can pop up in all sorts of subtle ways... like how there can be no perfect antivirus that will always tell you if a given program is malicious or not for any program, or how you can't write a tool that will examine a server and tell you if it will ever crash, or even that you can't write a program that will always tell you if a given program multiplies input numbers by 2! All of these are equivalent to solving the halting problem, even if they don't seem like it.
Of course this is all talking about ideal programs, and obviously antivirus software does exist, and it may be correct most or even almost all of the time, but this is about knowing that it can never be perfect for all inputs. Not because we aren't good enough programmers, or because we haven't figured out the right algorithm yet, but because it is provably impossible.
(For those interested in learning more, check out the Wikipedia page for Rice's Theorem -- it's really interesting!)
By the way, look in the description, there is a link to neat FAQ.
H: **exists**
N: Oh, I don't think so.
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
So, in other words, a possible simple way of describing the Halting Problem is as a computer's inability to "truly" realize when it's been given an unsolvable task, and to break from it and move on rather than infinitely trying to do so and never succeeding?
I think that any time you talk about a computer “realizing” things, it’s just going to lead to confusion on this topic. The computer doesn’t realize anything; it follows through mechanical steps according to a precisely defined set of rules.
What the proof shows us is that there is no set of rules you can define which will result in a machine spitting out the correct answer to the halting problem no matter what inputs you give it.
If you _try_ to build a machine that does that, you’ll fail, but the proof doesn’t say what your failure will look like. Your machine could get stuck, or it could just give the wrong answer in an infinite number of cases, or some mix of the two.
All we know is that your machine _won’t_ give the right answer in every case, because we know precisely how to construct an input where it doesn’t.
H is supposed to be a computer that truly realizes when something would get stuck on an unsolvable task. We just proved that it would be entirely impossible for H to exist and be perfect.
If H is defined as finite, it can exist. If H is defined as infinite, which it is for the purpose of this proof (X contains H, but H must contain X in its expandable memory in order to not get stuck), then H cannot exist.
H and X are true Turing Machines, meaning they do have an infinite memory available to them, yes.
I'm going to assume that by "finite", you mean that H is a finite state machine. Such an H cannot solve the halting problem over Turing machines, trivially, because there are infinitely many Turing machines whose descriptions will not fit in H's memory to begin with.
H[FSM] which solves the halting problem only over FSMs can exist. The halting problem is _decidable_ over FSMs, but it's also PSPACE-complete, so the fact that it's decidable isn't particularly useful.
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?
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
Damn this brings back nostalgia for me, not because I saw it in school or something, I just saw it on my own
chaumas you are iconic
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.
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.
I'm adding a new machine S. It always gets stuck
lol
The halting problem is easy to prove using reduction.
Let the language Atm be the language consisting of every pair where T is a Turing machine and s is a string that T accepts.
Hypothesis 1: there exists a Turing machine Q that decides Atm.
Let R be a Turing machine that recognizes an undecidable language. We can build a decider for the language recognized by R as follows
"On input s where s is a string:
1. Run Q on , If it accepts, accept. Otherwise reject.
"
We have built a Turing machine that decides the undecidable language recognized by R, so L(R) is decidable and undecidable, which is a contradiction. Discharge hypothesis 1 and conclude Atm must be undecidable.
Now let HALTtm be the language consisting of every pair where T is a Turing machine and s is a string that T halts on.
Hypothesis 2: There exists a Turing machine Q that decides HALTtm
We can construct a decider for Atm as follows.
"On input where R is a Turing machine and s is a string:
1. Run Q on . If it rejects, reject.
2. Run R on s. If it accepts, accept. If it rejects, reject.
"
We have built a Turing machine that decides Atm, but Atm is undecidable. Atm is decidable and undecidable, so we have a contradiction. Discharge hypothesis 2 and conclude HALTtm must be undecidable.
The fact that HALTtm is undecidable is the halting problem.
*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!*
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?
this is one of my favorite classic UA-cam videos. I return here after a good whole just after hearing a guitarist called Max Ostro performing Rhumba, by a Russian guitarist called DiDuLa... which I believe is the same intriguing music here... how the world goes round...
The thing is there are algorithmically unsolvable problems that the human brain cannot tackle either such as experiencing another's experience, while we could get very close with the future of brain mapping and neurostimulation the very basis of how the brain generates states of mind would require us to completely rearrange its structure to match that of the subject who's experience we are trying to mirror essentially eliminating the individual trying to experience another's experience.
ok
source: made it up
The human brain can also not solve the halting problem.
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
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
the problem we're all ignoring here is that this is why error handlers exist.
from the start the setup was flawed. A and C would both get stuck because you fed them incorrect input; "expected integer, got boolean" type deal. ignoring the fact that A and C themselves should, logically, have error handlers themselves, i.e. "expected expression, got image" or vice versa, a hypothetical H would instead have three outputs; "true", "false", or "invalid".
with machine X, you feed it its own blueprint. P duplicates it and feeds their outputs into H, which would print with this new output "invalid"; blueprint is not a valid input parameter for argument two. N would also therefore be modified, likely providing an output similar to getting "stuck" as an input.
congratulations, we've just created "try/catch" etc. error handling. Python and many Java-like languages have these handlers. assume that the variables "a" and "b" are predefined, and function similarly to machine A in this case;
try:
x = a + b
except SyntaxError as e:
...
even things like Lua that don't have explicit try/catch statements have an equivalent; Lua itself has "pcall";
local success, output = pcall(function()
local x = a + b
end)
if not success then print output end
the entire theorem and setup for "the halting problem" is faulty from the start. computers will simply take what we give them and output accordingly, and as the people who created said computers, we know we're not perfect; so, we create these methods to continue as expected.
given the restrictions scenario in this video, yes, you're correct; H couldn't exist, because in any scenario where its input is incorrect, its output would be recursive and paradoxical. the restrictions, however, don't make sense in a real-world scenario.
"computers will simply take what we give them and output accordingly". Oh, really? Did you never had a program which gets stuck in a loop? Were you able to predict it would get in a loop?
Your comment changes nothing about what the video is about or what has been proven. It's like saying the proof 1+1=2 is wrong because what if 1 would be 5? What if the equal sign means something else? And we cannot use it in real world. You see all these remarks are frankly irrelevant and change nothing of what has been proven. The video proves that the Halting problem (dooes a machine halt on its input yes or no?) is not solveable. That's it. That's what the video has proven. What this means is that there are problems no computer can solve for you. Like the halting problem. You cannot build a machine or a program which can tell you if another machine halts on its input
The early examples in the video can lead people to thinking that this is about "errors", but this is much more fundamental than that. This is about infinite loops. When we say a machine is "stuck", what we mean is that it runs forever, and when we say "not stuck", we mean that the machine eventually stops (or "halts"). The error cases given are examples of why a practical machine might get stuck, but this is far more general than that.
You can't error handle your way out of infinite loops. There is no try/catch for that condition. Like, look at this code:
while (true) {
print("hello")
}
Where would you put the try/catch? Nothing throws an exception. It just runs forever. It's _stuck._
The point of this proof is to show that it's impossible to reliably detect whether a program will get stuck on a given input. You _can't_ have a reliable "infinite loop exception", because it's impossible for a machine to know whether or not an arbitrary piece of code is in an infinite loop.
The premise that when H receives X's blueprint, it can conclude is wrong. It can simply be stopped because it cannot be concluded.
Then H can’t exist. H’s definition is that it gives the right answer to the halting problem in every case. The halting problem always has a yes or no answer. If it’s impossible to build a machine that can give the correct answer in every case (which it is), then we say that the problem is “undecidable”.
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*
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 😂
I’m confused, what was the purpose of machine N as a negator. It sounded like the machine only contradicts itself because N was programmed to do the opposite of what it was told. H said it was Not Stuck so N said it was. H said it was Stuck so N did the opposite. How does forcing something to do the opposite of the input count as proof?
I figured it out. Basically the proof is that a machine can’t be perfect at solving everything, including contradictions. The negator is used to prove that you can make a “perfect machine” contradict itself. H is always supposed to be right and N makes it say something wrong. Now that I figured it out I honestly don’t feel like I’ve learned much. Yeah, things aren’t “perfect” because you can make them contradict itself.
@@codex2345 No, X is not contradicting itself or trying to predict anything. There is a standalone H, that tries to predict X's state. The purpose of N inside X is to make it so standalone H can never give a correct prediction, contradicting its own definition.
@@codex2345 The fact that you CAN make H contradict itself such that even an external H would be wrong, is interesting.
You can't do that for many machines.
Can we, for the 10th anniversary of this video, give C a modern gaming rig and pit it against the chess machine in the description?
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).
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
this is the very best illustration/explanation of this problem i came across
So in the beginning of the video, what does machine C do when given an input where the only possible move/moves is a losing outcome?
Machine C never loses if it makes all the moves. Of course, if it's for example at a place where it's in a losing position, it will still lose, it can't perform magic.
So machine C just gives you the best possible move.
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
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
@@jennyfisher3765 ♥
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
2:07 A: "ight imma head out"
This is so beautiful. Thank you so much!
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.