The Halting Problem: The Unsolvable Problem
HTML-код
- Опубликовано: 7 фев 2025
- One of the most influential problems and proofs in computer science, first introduced and proved impossible to solve by Alan Turing. The video provides the idea of this incredibly clever proof. I highly recommend anyone who is comfortable with mathematical proofs to read the formal proof to the problem (look at additional resources below for information).
Also, the video does not cover this, but the significance of this unsolvable problem cannot be understated. By logically proving that the Halting Problem is impossible to solve, this means that there is an entire class of problems that can never be solved through computing (i.e. undecidable problems). For example, the Halting Problem tells us that it is impossible to come up with a general algorithm/program/machine that tells us if another algorithm/program/machine will ever halt. This means it would be impossible to come up with an algorithm that does something as simple as determine if a program only prints "A". This is because we can reduce the problem of determining whether a program halts to the problem of determining whether a program prints “A”: Take the description of the original program and change every exit/return statement to a “print A” statement. The new program prints “A” precisely if the original program halts, and being able to determine if the program prints "A" would mean we can determine if the program halts and, therefore, solving the Halting Problem. However, as Turing had proved, the Halting Problem is unsolvable, an algorithm that determines if another algorithm halts cannot exist; what more determine if a program prints something?
___________________________________________________________
Additional resources to understand this INCREDIBLE PROOF:
Turing, A.M. (1937), On Computable Numbers, with an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, s2-42: 230-265. doi:doi.org/10.111...
Alan Turing's original paper and proof to the Halting Problem. This is also the paper where he first introduced the idea of Turing Machines. It might be interesting to note he did not call it the Halting Problem in this paper. In fact, it wasn't until a later paper that the term 'halting problem' was introduced.
Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
The main source of my Theory of Computation knowledge (a textbook). Read Chapter 4.2: Undecidability to learn about the diagonalization technique used in this proof, and to see a more formal proof.
Hodges, Andrew, "Alan Turing", The Stanford Encyclopedia of Philosophy (Winter 2019 Edition), Edward N. Zalta (ed.), plato.stanford....
To read more about Alan Turing and his ideas!
___________________________________________________________
And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.
Easiest explanation I have ever seen... really awesome!
because its wrong luls
@@flo0778 wdym
@@iamamaze8790 D is a computable function it takes an input x and then you can compute D(x) (potentially for ever).
H can say if a computation will run forever.
At 2:11. H decides if D weather D will halt or continue forever. But this makes no sense because D is a function. It needs an argument to be a program. It makes no sense to say "it holds" or "it continues forever" for a function : it could depend on the argument.
This proof just proves that there is no algorithm that can say if a function D will stop or halt for all arguments. Which was trivial to prove : such a H cannot work for a function that stops or doesn't stop depending on the argument (example f(x : boolean) = while(x) {}).
The real proof actually proves that there is no computable function H that can say if a program will halt; it uses a clever trick with the arguments of function D and function H. check any other video.
@flo0778
It only omitted that D is both the input function and argument to H, as in:
D(f) = Opposite(H(f,f))
where H(f,g) determines if f halts given g.
when applied:
D(D) = Opposite(H(D,D))
Whether D(D) halts or not creates a contradiction as H states the opposite.
This explanation is AMAZING! Most other videos feel like the author doesn't really know they problem themselves. Thanks I finally got it
The explanation is wrong though
This is the best explanation of the halting problem on RUclips by far
Thank you so much for the clear explanation 🙏 I've watched countless clips about the halting problems, but never got to wrap my head around it. You did an awesome job at explaining in four minutes 👍 Please make more videos about computing, not the coding but the math behind it.
Kn
I feel as though this video filled the gaps in my misunderstanding. So clear! Thank you so much
Ive literally watched 10 other vids on the halting problem, and this is the only one that made sense. TY
This is one of the best intuitive channels for one to learn basics of fundamental computer science problems
I am preparing for my Automata exam. I've been struggling understanding the Halting problem this whole time. Your video was so precise and easy to understand. Keep up the good work!
aur kitna aaya apko?
@@supriyamanna715 92
Can you please tell me from where and how to study on this topic!! I'm literally crying
Digital structures are the most beautiful and most terrifying thing at the same time man
WOW!!! I just got ton of conceptual knowledge of TOC in detail with all the kind of theories involved inside it. Bunch of thanks to you Lydia Cheah!!!
Your explanation and animation help me to understand the Halting Problem! Thank you so much for such great video and please keep up the good work!
I believe this is the most easy-to-understand explanation and cutest animation about Halting Promble that I can find on RUclips.
Appreciate.
It's so brilliantly explained, it really makes you think-why didn’t I get this sooner?
Been a long time since I studied this, it's so useful. For those who need this too:
The Halting Problem also disproves the Eintscheidungsproblem.
The Eintscheidungsproblem asks for a program that can answer True or False when given a logical statement.
Say our logical statement is whether a program will halt (aka the Halting Problem)
so we have two instances of D, D1 and D2, with an instance of H each, H1 and H2
pass D2 into D1. If H1 determines D2 halts, then D1 will continue forever. If H1 determines D2 runs forever, then D1 will halt.
This is a contradiction, thus H can't exist.
This also means that if we fed this into the Eintscheidungsproblem it wouldn't be able to answer it, thus E (the algorithm to solve the Eintscheidungsproblem) also can't exist.
Your explanation were quite clear, understandable and enjoyable, thank you
I enjoyed all the videos I watched on your channels
I'm Korean. It's informative, cute, and informative. Thanks to you, I understood it first. This was the most important task.
This deserves one million more views. Thank you.
Thank you very much for this video. It's the first video I've seen that explain the problem with such simplicity
GIRL THANK YOU! I‘m writing my final exam this friday and I‘ve been struggling with this topic for tooooo looooong! You really helped me here. Wish you an amazing year! THANKS again ❤
This explanation is wrong 🙏😭
@offeibekoe452 which part is incorrect? 😭🙏
@@offeibekoe452 please explain🙏🙏🙏
The most easiest explanation on YT.❤️❤️
I subscribed.
Needed to quickly get a grasp on this for my dissertation. Definitely would've taken a long time if researched elsewhere. Thanks for the quick explanation
Easily the best explanation I’ve seen
you definitely needs more subscriber. simple explanation. I easily got it. thank you! can you explain Turing complete and state machines?
Brilliant animation and vocal skills. Much Thanks & Love :)
Wow this was the simplest yet most interesting and helpful video explanation!!
Thank you so much!! I’ve watched quite a few videos about this but this one really made sense!
This person has to be the best teacher ever!
Awesome explanation. Short and concise! Love from Louisiana, USA.
thank you so much i did not understand this halting problem in other programs but now it is pretty clear.
Why did ye stop making videos
job interviews be like:
Hmmm, it seems you dont understand the hard problems. Lets go with something easier. Write an algorithm that solves the halting problem in O(1) time!
Probably missed your joke, but that's really easy. Here's the program:
print("It's not possible")
really really amazing explanation , i had problem understanding this topic but now it is clear ! i am gonna recommend this channel to my friends . Keep posting more :D
This video is really awesome , it gave me the clarity of the proof of this halting problem, I really appreciate the work, thank you so much bro...
Finally understand this! Thanks for the video, shame the channel is dead because the voice and animation are both awesome.
I wondered if was dumb after watching the other videos and going “huh??” each time. I think I’m grasping it a bit better with yours. Thank you so much!!
I don't like any of these visual proofs on youtube. I think the formal mathematical proof is much easier to understand.
Because this is wrong
@@offeibekoe452 It's not wrong. Just confusing
I have watched many videos (many halting machines) around RUclips..
But your cute machine's just made me understood the problem..
Thanks a ton...
I really appreciate...
Oh God thanks 😇
Finally understood after watching tons of videos.... Thank you very much 🙏🙏
this is a kind of explanation for those people who are curious and want to learn for their own knowledge; this is not for those people who are studying the night before exam.
Do you study university exams on youtube?
One of the greatest explanations ever thanks for the video
3 years later and this is making things soo understandable
This is the best explanation. Now I understood the concept clearly.Thanks a lot❤❤
Easiest explanation I've seen so far.
Simple and intuitive explanation, thank you very much!
I somehow misread the title as "The Hailing Problem" and therefore thought the guy on the thumbnail was Hitler.... I was mildly confused.
Henceforth I'll be referring to him as "Adam" Turing.
The author likes to repeat that H is always right so...
Best explanation ever, thank you.
BEST FREAKIN' EXPLENATION IN THE WORLD, THANK YOU SO SO SO MUCH
How is this still free ?
Damn this is some high quality educational playlist
Thank you for this, excellent explanation, I actually understand the issue now!
I like❤this halting problem ,thanks🌹🙏❤ for creating this video 🎥 I enjoyed😊😂and cartoons are so cute I like it ❤. And getting halting problem knowledge📚 very easily.
Thank you❤.......
Proof of "everything can be explained". Awesome!
thank you for this, I dont know why i needed to or wanted to learn this, but Now I somewhat understand it. However everything else involved in this I dont understand.
short, precise, easy to understand !
Awesome video. This should be used in lessons.
Love it!
Tomorrow is my semester examination
Thank you to your whole team 😭❤️
Wow. This a such a good video, and I’m only half way through.
Crystal clear explanation.
First video that explained it so I can understand it! :)
i am watching this like 30 minutes before my quiz and what was i doing love it so much easier
Thank you! I finally understood what it means.
Beautiful!! Keep making videos!! Mabe one explaining the Entscheidungsproblem or Type theory would be great!
why you so less suscriber 😐she deserves more
Best explanation of this problem
Thank you for your explanation, it was really easy to catch on, the best I saw. I have one question for you though, it is probably stupid because I have no programming knowledge, why is the program D programmed to do the opposite of what H says?
I think the purpose of creating the program D that does the opposite of H is to make this proof, i.e. to show that the program H cannot exist. Using this program D doesn't affect the initial assumption because you should be able to design this program D since it is possible, and D can be used as input into itself since D itself is also a program.
we've deliberately designed D *just* for the purpose of using it to prove something about how H works. I'm not sure how Alan Turing figured out (or guessed) that this particular behaviour (negating H) would be useful for proving H can't exist - that kind of creativity is the hard part of coming up with formal proofs, after all!
Great explanation, good job!
Best Explanation hands down!!
Amazing explanation. Thank you!
The function H, as per your description, is meant to take in two arguments: a program (or function) P and an input i for that program. It doesn't assume that P has no arguments. The function H(P, i) would then return true if P(i) halts (returns a result after a finite number of steps) and false if P(i) loops indefinitely.
Here's a more precise sketch of the halting problem:
"""
def H(P, i):
"""
H is a hypothetical function that determines whether program P halts on input i.
Returns True if P halts on i, and False if P runs forever on i.
"""
raise NotImplementedError
def D(P):
if H(P, P):
while True:
pass # Loop indefinitely.
else:
return # Halt.
# Now consider D(D). There are two cases:
#case1:
# If H(D, D)==False then, by definition of D, D(D) must halt.
# But if H(D, D)==False then, by definition of H, D(D) must never halt.
#case2:
# H(D,D)==True , then by the definition of D, D(D) must never halt.
# But if H(D, D)==True, then, by definition of H, D(D) must halt.
# In either case, we have a contradiction.
"""
This is a contradiction, which means our initial assumption that function H can exist must be wrong. Therefore, no such function H can exist that accurately determines whether arbitrary programs halt on all inputs. This is the essence of the Halting Problem, and it also implies that there's no algorithm that can determine whether any arbitrary first-order logic formula is satisfiable.
you just rewrote what she said
@@grevel1376
"""
def A(x):
#A is a hypotetical function that returns its argument called with itself as its argument.
return not x(x)
#from definition of A: A(A)==not A(A)
#it is a contadiction.
#Therefore function that determines what does its argument return, if called with itself as its argument, does not exist.
print(A(A))#never returns.
"""
Omg this video is best! Love the way u explained! ❤❤😊
Thanks for the help. It's really help me to understand more. Very good animation, I really like this.🤖
great explanation
I feel so bad for the sad H :( thanks for the great explanations!
Very nice explanation & animation!
Finally understood this thank you so much
Great explanation. My only problem is why does this problem exist? Like wouldn’t a machine be able to return a third option, such as a 0, saying that the algorithm is itself? It would be a simple check, assuming the whole concept of seeing if an algorithm will halt or not is not too complicated. Idk this seems dumb
But what if a H* program is defined with the additional constraint that it only works as a standalone program? H* determines whether a program halts or not and when feeding H* to itself it says that it halts.
That makes no difference. It doesn't matter where H is called from, its output for a certain input is always the same. This is why I don't like these visual explanations, they make things like this confusing. The formal mathematical proof is the simplest way to understand it, in my opinion.
@@paulblart7378 Then what if H(P, I) is modified with the additional constraint if(P == I) return undefined? Maybe that's cheating haha, because H is then no longer universal and can in its modified form return truth, false and undefined, but anyway.
@@Anders01 A program cannot halt "undefined". It would either halt or not. There is no other option. If H makes it so that a program must halt "undefined" for H to always be right, then there's a paradox, therefore H cannot exist. The main issue is that H must be right about EVERY possible program, which includes programs composed of H.
@@paulblart7378 Yes, the addition of if(P == I) return undefined relaxes the universal requirement. But I think of as similar to the Regularity Axiom in set theory. It removes self-reference.
@@Anders01 True... I guess you could make an H that works for all programs that don't consist of H. Not sure if that's necessarily proven though.
this was awesome genuinely
Fantastic video and amazing visuals!!! :D
Great Explanation ✨
It really isn't... look how many people in the comments are confused. The formal mathematical proof is simpler to understand than any of these weird visual explanations.
Easiest and Cute explanation
Really good explanation
beautifully explained, thank you!
Very cute channel btw.
I've been studying AI for almost two years and will definitely recommend your channel to all new cs students (:
H needs 2 inputs (since whether a program halts is dependent on the input). Since H needs 2 inputs, D needs 2 inputs as well (to accurately simulate H). Simply giving D D as input is invalid. running D(D, D) implies simulating D(D, )(invalid input).
Also treating running forever and halting as booleans that can contradict is an arbitrary choice.
I'll admit that this video's explanation could have been a lot better but the proof is still there.
great audio and video representation
OMG loved your video!! thanks a lot
its like asking a liar if he is telling the truth, but instead asking a liar if another liar is lying. it will never work, and you can use this rethorical juggle to disprove anything. thats precisely the difference between sophism philosophy and science.
This is so good
Best content in my opinion
this is an awesome explanation, thanks :)
The halting problem becomes apparent when you hear the word 'forever'.
The program would run forever and never get a 'not stuck'.
Thanks!
Great video!
Thank you lydia!
This is the solution to the confusion (Read this word by word you can then sleep peacefully):
1) We know that from h we can derive h+
2) If h+ exists then h exists
3) And h+ returns opposite of whatever it is supposed to tell about an input
4) We make it to contradict by inputting itself into it, now even though it’s saying the opposite of it’s input but even doing the correct thing it’s contradicting with itself!
5) Now if h+ contradicts itself, it can’t exist and so h can’t exist!
this has to be the easiest explanation on the entire internet to the Halting Problem.
It only got it wrong because D does the opposite of what H says after H says it, and H wasn't programmed to be able to adjust for that. If H was programmed to able to randomly pick if D should halt or not, then signal to D the opposite of what it chose in response to that program and then display its prediction for humans to see separately, practically, it would always be right.
Yeah this explanation os wrong
But D is using H's output as input? So D is running an altered version of the program H read.
Thank you
Is basically the pinochio paradox, its the exact same thing, but with computers
Best explanation
easiest explanation❤
Also the worst. It's way too simplified
can u suggest some really good books to get notes on this topic?
very underrated