@@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.
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.
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!
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
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!!
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!
I have watched many videos (many halting machines) around UA-cam.. But your cute machine's just made me understood the problem.. Thanks a ton... I really appreciate... Oh God thanks 😇
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
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!
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.
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.
@@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. """
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.
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❤.......
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.
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!
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.
There is something wrong no isn't it ? lets call x the program that is passed to H (the sheet that appears at 2:05). I don't understand what x is because D needs some input to be runnable. D is a funciton of some data isn't it ? So to be able to call that a x "program" that can either run indefinitely or stop, x has to be D(d1) even if the data d1 is empty. (I can construct easily a program which has different behaviors based on the data passed to it, so H cannot be a program that takes a function as an argument, it has to be a deterministic runnable with no parameters) at 2:20, there is no contradicion then, H said that x ( i.e. D(d1) halts) and by construction we see that D(x) = D(D(d1)) does not halt. This would only be a contradiction if D(d1) = d1 which remains to be proven there is no reason why D(D(d1)) and D(d1) should behave in the same way. I don't get it nothing makes sense here, this is a hoax please help. Edit : I found an actual math video that explains the real proof which does involve the data of D not some simplified version that does not work. I'm considering reporting this under the "misinformation" category
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.
This explanation is AMAZING! Most other videos feel like the author doesn't really know they problem themselves. Thanks I finally got it
This is the best explanation of the halting problem on UA-cam by far
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
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 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
This is one of the best intuitive channels for one to learn basics of fundamental computer science problems
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 UA-cam.
Appreciate.
It's so brilliantly explained, it really makes you think-why didn’t I get this sooner?
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.
Simple and intuitive explanation, thank you very much!
The most easiest explanation on YT.❤️❤️
I subscribed.
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
Why did ye stop making videos
Easily the best explanation I’ve seen
Wow this was the simplest yet most interesting and helpful video explanation!!
Brilliant animation and vocal skills. Much Thanks & Love :)
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
Short and precise, whilst still being engaging with amazing animations! A well deserved like :D
This person has to be the best teacher ever!
you definitely needs more subscriber. simple explanation. I easily got it. thank you! can you explain Turing complete and state machines?
Easiest explanation I've seen so far.
Awesome explanation. Short and concise! Love from Louisiana, USA.
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...
One of the greatest explanations ever thanks for the video
Thank you so much!! I’ve watched quite a few videos about this but this one really made sense!
thank you so much i did not understand this halting problem in other programs but now it is pretty clear.
3 years later and this is making things soo understandable
Finally understood after watching tons of videos.... Thank you very much 🙏🙏
Finally understand this! Thanks for the video, shame the channel is dead because the voice and animation are both awesome.
Best explanation ever, thank you.
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.
short, precise, easy to understand !
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")
I have watched many videos (many halting machines) around UA-cam..
But your cute machine's just made me understood the problem..
Thanks a ton...
I really appreciate...
Oh God thanks 😇
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
Crystal clear explanation.
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...
This is the best explanation. Now I understood the concept clearly.Thanks a lot❤❤
Proof of "everything can be explained". Awesome!
Best explanation of this problem
Thank you for this, excellent explanation, I actually understand the issue now!
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!
Best Explanation hands down!!
Amazing explanation. Thank you!
Thank you! I finally understood what it means.
Awesome video. This should be used in lessons.
Love it!
Wow. This a such a good video, and I’m only half way through.
First video that explained it so I can understand it! :)
How is this still free ?
Damn this is some high quality educational playlist
Great explanation, good job!
Is basically the pinochio paradox, its the exact same thing, but with computers
BEST FREAKIN' EXPLENATION IN THE WORLD, THANK YOU SO SO SO MUCH
Finally understood this thank you so 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?
Very nice explanation & animation!
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.
"""
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.
beautifully explained, thank you!
Beautiful!! Keep making videos!! Mabe one explaining the Entscheidungsproblem or Type theory would be great!
Really good explanation
great explanation
Fantastic video and amazing visuals!!! :D
this was awesome genuinely
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❤.......
Tomorrow is my semester examination
Thank you to your whole team 😭❤️
great audio and video representation
this is an awesome explanation, thanks :)
very underrated
i am watching this like 30 minutes before my quiz and what was i doing love it so much easier
It's like, "I am Lying... Is this statement a truth or a lie?"
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.
Thanks for the help. It's really help me to understand more. Very good animation, I really like this.🤖
Easiest and Cute explanation
This is so good
Best content in my opinion
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.
I feel so bad for the sad H :( thanks for the great explanations!
why you so less suscriber 😐she deserves more
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.
Basically the classic "This statement is false" paradox
Omg this video is best! Love the way u explained! ❤❤😊
Great video!
Thank you lydia!
OMG loved your video!! thanks a lot
Thank you
Really cool problem!
Best explanation
Please make a video on solvable and unsolvable problems..
Nooo poor H , you are right don't listen to other people(2.:24 to 2:29 💔)
Very cute channel btw.
I've been studying AI for almost two years and will definitely recommend your channel to all new cs students (:
But if D follows what H says, instead of doing the opposite, will it solve the problem?
What? It dosen't solve anything, the problem is that H isn't right in the situation that it is in. Of course H is usualy right, but not always.
THANKS
I love you! thank you so much!
There is something wrong no isn't it ?
lets call x the program that is passed to H (the sheet that appears at 2:05). I don't understand what x is because D needs some input to be runnable. D is a funciton of some data isn't it ? So to be able to call that a x "program" that can either run indefinitely or stop, x has to be D(d1) even if the data d1 is empty. (I can construct easily a program which has different behaviors based on the data passed to it, so H cannot be a program that takes a function as an argument, it has to be a deterministic runnable with no parameters)
at 2:20, there is no contradicion then, H said that x ( i.e. D(d1) halts) and by construction we see that D(x) = D(D(d1)) does not halt. This would only be a contradiction if D(d1) = d1 which remains to be proven there is no reason why D(D(d1)) and D(d1) should behave in the same way.
I don't get it nothing makes sense here, this is a hoax please help.
Edit :
I found an actual math video that explains the real proof which does involve the data of D not some simplified version that does not work. I'm considering reporting this under the "misinformation" category
nice explain