Proof That Computers Can't Do Everything (The Halting Problem)

Later in 3019... Robot: Let's assume that humans are useful

H: I'm always right. N : I'm gonna destroy his whole career.

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.

"H was wrong again but H is supposed to always be right" that just hits me in the heart, so emotional..

H doesn't exist? So it's The Alting Problem

"H was wrong again but H is supposed to always be right" Never have I ever been so emotionally attached to a theoretical machine

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

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.

the smugness in her voice when she said "logically impossible" is so powerful

i like how a and c turn into washing machines when they're given the wrong problems

basically the halting problem in a machine that negates itself is the same as "This sentence isn't true", thats so cool and interesting

Expectation: "It will always print the correct answer." Reality: INSTALLED INK CARTRIDGE CANNOT BE RECOGNIZED

Who else felt satisfied when all the machines connected perfectly

"Oh dear", says H, "I hadn't thought of that", and promptly vanishes in a puff of logic.

it’s crazy how 9 year olds think they’ve solved a problem that’s been studied by experts for years

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.

"What won't be your next sentence?" the engineer asked the all-powerful computer.

Note that this doesn't mean we can't build a version of H that solves the Halting Problem really well but not perfectly.

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.

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.