Understanding the Halting Problem

The halting problem is an important problem in computer science that asks whether we can construct an algorithm to determine whether a computer program will run forever. It turns out that the halting problem can't be solved, and in this video, we look at the proof to understand why.

***

[fredoverflow]

I love how the green robot is still running when the video ends 😂

[Trank]

I wonder if it's your channel being recommended to people recently that inspired you to continue making more videos or something else. Either way I am glad that you do it, keep up the good work!

[samarthtandale]

You just gave me an intuitive understanding of a concept I struggled to understand since months lol! Thank you!

[GuitarSlayer]

Watching this dude's content I feel like he deserves a play button specifically for college professors and tech school instructors using the video without giving credit/compensation because it's better than anything they could do.

[Wonders_of_Reality]

Note: that we might make a program that can IN SOME CASES predict whether an algorithm stops or runs indefinitely. In all cases—no, it’s proven. But in some cases—possible.

[jaideepshekhar]

Glad to see you back dude! :)
It would be great if you went further into NP and NP hard problems, and their classes. Cheers! :)

[superspartanman]

So glad you are making more videos, I discussed this exact problem with my buddy over spring break

[lightning_]

It feels like we should still be able to make programs that solve the haunting problems in certain, restricted scenarios.

[emtacolor]

this video came at just the right time. my algorithm analysis final is in a week

[Dark_Slayer]

Luckily we can easily write a halting program for any specific program, just not for every program.

[arthursamenu]

I never understood these thing for many years ! this dude is a rockstar!

[asmaarefaatVO]

This channel is like water and air to the human being!

[GCKteamKrispy]

Brian, thank you so much for these and CS50w videos. Your explanations are amazing

[chuckgaydos]

Finally, a math problem that can be solved with a sledgehammer.

[debanwitahajra]

The best video on YouTube. I mean, yes.

[NEMountainG]

Great video!

I do have one question that seems to always enter my mind whenever watching these sorts of videos on The Halting Problem though:

As states at around 5:55, it’s not possible to construct a program that detects halts IN GENERAL. May I ask if there are some “practical constraints” that do allow us to construct such programs? What “meta constraints” must he met in order to choose some system of constraints? (i.e., (A and B or not C) or (not A and not B))

I never seem to find an answer to these questions and don’t really know where to look. I would appreciate any support!

[bcs_AyushkumarRai]

Simply amazing kindly upload more videos, and thank you.

[kvelez]

I've been watching your channel and it's been great.
Please do encryption algorithms, sorting algorithms, and history of computing.

[giveaway]

really really awesome easy wayto understand.

[bubblesort]

again one of those videos. Thank you sir for your efforts.