The Halting Problem - An Impossible Problem to Solve

Alan Turing proved that the Halting Problem was impossible for Turing machines (computers) to solve. Come find out how.

This video was co-written by my super smart hubby Simon Mackenzie.

Hi! I'm Jade. Subscribe to Up and Atom for new physics, math and computer science videos every two weeks!

Visit the Up and Atom Store

*Follow me: @upndatom

Check out this PlayList for a taste of the channel:

A big thank you to my AMAZING PATRONS!
Paul Kendra, Harsh Tank, Alan McNea, Daniel Tan-Holmes, Simon Mackenzie, Yoseph, Andrew Pann, Dave, Anne Tan, Ayan Doss, Marc Watkins, Sung-Ho Lee, Todd Loreman, David, Susan Jones, M.H. Beals, Doug Cowles, Stephen Veitch, Renato Pereira, Simon Dargaville, Dean Madden, Noah McCann, Robert Frieske, Magesh.

If you'd like to consider supporting Up and Atom, head over to my Patreon page :)

For a one time donation, head over to my PayPal :)

Other videos you might like:

*Sources*

*Music*

[upandatom]

WHOOPS 1 isn't a prime. The computer would have stopped at (2+2), my bad! Thanks for pointing that out everyone :) I can be a bit ignorabimus sometimes.

[TierZoo]

Platypus wins, those venomous spines are no joke

[FGj-xjrd]

5:07 "Barrie can't both run forever and halt" Schrödinger's cat is calling fake news on this one.

[lostwizard]

Seems a few people are either trolling or missing a fundamental detail of the particular proof. Hal is assumed to be a *general purpose* program that can be run on *any* input program and it always provides the correct answer. Because Hal is defined to work on all programs, it must be able to work on itself since Hal is, itself, a program. The thing I think a lot of people are missing is that this is a proof that the halting problem cannot be solved in the *general* case. To prove that the general case cannot be solved, you just need to find *one* counterexample.

This says nothing about specific cases. There are plenty of specific cases where it is possible to identify if a program will halt. The existence of those cases does not invalidate the proof. The proof is simply telling us that there is no magic box that will work on every possible program. Basically, it means there isn't a magic shortcut for solving Goldbach and other problems.

[leonardoreyes]

These guys didnt even had computers when this was proposed, I love it. Alan Turing was a visionary.

[Hobbitstomper]

3:53 - I'm sorry, Dave, I'm afraid I can't do that.

[Melthornal]

I solved the halting problem by unplugging my computer and crying.

[prafulchauhan]

This is just more complicated version of "this sentence is false".

[robertbilling]

Studied this back in the 70s in Cambridge when the people who had known Turing were still lecturing. This video brought back some wonderful memories. Thanks.

BTW the entire university computing service ran on an IBM 370/165 with 3 megabytes of RAM back then.

[boghag]

Hilbert's Nemeses: Turing and Gödel :D

[DSMWannabeLinguist]

“Will I ever stop being a disappointment to my family?”
A’ight Jade, I’m gonna need you to stop recording me while I’m “working”, we’ve talked about this.

[KeystoneScience]

I just found your channel, your videos are great! Keep up the good educational videos! :)

[ingeborgsvensson]

What if we put the Barrie program on a quantum computer where it is potentially both running and halting simultaneously, in a state of superposition. I think I have solved it. ;-) Great videos, keep them coming.

[coffeeshangarworkshop]

Computer, which is better: Pirates or Ninjas? Star Wars or Star Trek? ... .... 42.

[Ownagelif]

You have one of the best animations for science videos, period.

[mkrichey]

Great video, wonder if in a quantum world it could run and halt at the same time :)

[raymitchell]

I remember in the good old days studying computer science and first hearing about "The halting problem" it seemed odd and trivial to me at first... that is because I didn't understand it, I mean... I didn't understand why it was such a big deal. The proof done by contradiction was brilliant ploy by Turing, I'll never forget how astonished that I actually got understood it on the first run-through (that rarely happens!)... but you made me feel sad for the way poor Hilbert was broken hearted in your animation... but, as you rightly pointed out, he does have his own space named after him, so there is that...

[electromorphous]

You literally have an infinity like-to-dislike ratio right now.

[RickSummon]

In fact, a Turing machine has been created with, I believe, 29 states that halts if and only if the Goldbach conjecture is false. The step function S is the maximum number of steps a Turing machine can run before it must either halt or run forever. So, if you ran the machine for S(29) steps and it didn't halt, you'd know the conjecture was true! Of course, the halting problem proves that S cannot be computed by a Turing machine, so we can't actually know what S(29) is. However, we do know that S(17) is greater than *Graham's number*, so the age of the universe isn't even pocket change compared to it.

[anujarora]

Do you write your jokes by yourself??if so then you're a good comedian as well