The Halting Problem: The Unsolvable Problem

[@NeerajSharma-rf2ev]

Easiest explanation I have ever seen... really awesome!

[@flo0778]

because its wrong luls

[@iamamaze8790]

@@flo0778 wdym

[@flo0778]

@@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.

[@roxferesr]

This explanation is AMAZING! Most other videos feel like the author doesn't really know they problem themselves. Thanks I finally got it

[@johndebord7802]

This is the best explanation of the halting problem on KZbin by far

[@pslaw]

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.

[@anubmusing9749]

Kn

[@L99BAN]

I feel as though this video filled the gaps in my misunderstanding. So clear! Thank you so much

[@shadmantabib5014]

This is one of the best intuitive channels for one to learn basics of fundamental computer science problems

[@jordanjohn01]

Ive literally watched 10 other vids on the halting problem, and this is the only one that made sense. TY

[@bisheshshrestha2740]

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!

[@supriyamanna715]

aur kitna aaya apko?

[@bisheshshrestha2740]

@@supriyamanna715 92

[@kangkshitaroydeshmukh9173]

Can you please tell me from where and how to study on this topic!! I'm literally crying

[@thewatcher9480]

Digital structures are the most beautiful and most terrifying thing at the same time man

[@HiJackLeeLee]

I believe this is the most easy-to-understand explanation and cutest animation about Halting Promble that I can find on KZbin. Appreciate.

[@MATHONG]

I'm Korean. It's informative, cute, and informative. Thanks to you, I understood it first. This was the most important task.

[@nuton9706]

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!

[@karanmunjani3256]

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!!!

[@kopanhagen668]

It's so brilliantly explained, it really makes you think-why didn’t I get this sooner?

[@Nitin-_-_-_-_-_-_-00971]

The most easiest explanation on YT.❤️❤️ I subscribed.

[@breathemath4757]

This deserves one million more views. Thank you.

[@olgermannik1830]

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]

you just rewrote what she said

[@olgermannik1830]

@@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. """

[@dsareis9134]

Your explanation were quite clear, understandable and enjoyable, thank you

[@dsareis9134]

I enjoyed all the videos I watched on your channels

[@tejas.873]

Wow this was the simplest yet most interesting and helpful video explanation!!

[@_yomiadebowale]

This person has to be the best teacher ever!

[@illyushen9856]

Why did ye stop making videos

[@omegahaileyesus]

Easily the best explanation I’ve seen

[@mastadodo]

Simple and intuitive explanation, thank you very much!

[@AbdoulieTamba]

Easiest explanation I've seen so far.

[@miguelsr4272]

Thank you very much for this video. It's the first video I've seen that explain the problem with such simplicity

[@aavashkuikel1341]

Awesome explanation. Short and concise! Love from Louisiana, USA.

[@amritborah2773]

Brilliant animation and vocal skills. Much Thanks & Love :)

[@breezyx976]

Finally understand this! Thanks for the video, shame the channel is dead because the voice and animation are both awesome.

[@justtom7860]

Short and precise, whilst still being engaging with amazing animations! A well deserved like :D

[@BenM2291]

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

[@sahaneakanayaka3394]

Finally understood after watching tons of videos.... Thank you very much 🙏🙏

[@shadmimhasansifat187]

I have watched many videos (many halting machines) around KZbin.. But your cute machine's just made me understood the problem.. Thanks a ton... I really appreciate... Oh God thanks 😇

[@HGGdragon]

I somehow misread the title as "The Hailing Problem" and therefore thought the guy on the thumbnail was Hitler.... I was mildly confused.

[@BeautyMarkRush]

Henceforth I'll be referring to him as "Adam" Turing.

[@billyberrington]

The author likes to repeat that H is always right so...

[@maxpoweroverdrive]

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.

[@thepiratepeter4630]

Do you study university exams on youtube?

[@desert-storm7]

Proof of "everything can be explained". Awesome!

[@thecsmedic]

3 years later and this is making things soo understandable

[@noname60605]

This is the best explanation. Now I understood the concept clearly.Thanks a lot❤❤

[@saichaithrik7134]

One of the greatest explanations ever thanks for the video

[@bertansadiki6794]

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!

[@paulblart7378]

Probably missed your joke, but that's really easy. Here's the program: print("It's not possible")

[@kid_kulafu_1727]

you definitely needs more subscriber. simple explanation. I easily got it. thank you! can you explain Turing complete and state machines?

[@vijaykumar-cz7ot]

How is this still free ? Damn this is some high quality educational playlist

[@Ananyalatchupatula]

thank you so much i did not understand this halting problem in other programs but now it is pretty clear.

[@unnatip2302]

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

[@dishendra.]

short, precise, easy to understand !

[@mrityunjoynath7673]

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!

[@inziify]

this has to be the easiest explanation on the entire internet to the Halting Problem.

[@Ms_Ink]

Thank you so much!! I’ve watched quite a few videos about this but this one really made sense!

[@JessicaReginadosSantos]

BEST FREAKIN' EXPLENATION IN THE WORLD, THANK YOU SO SO SO MUCH

[@kumardevada8567]

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...

[@NeerajSingh-or9hd]

Crystal clear explanation.

[@MuhammadAbdullah-qi1of]

Tomorrow is my semester examination Thank you to your whole team 😭❤️

[@Spacexioms]

Best explanation ever, thank you.

[@saakshimalhotra3926]

Best explanation of this problem

[@adrianbermudez7005]

Is basically the pinochio paradox, its the exact same thing, but with computers

[@rajkamalingle9144]

Best Explanation hands down!!

[@UTubeLion]

First video that explained it so I can understand it! :)

[@dunjasavic7583]

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?

[@nicogovindsamy9022]

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.

[@gloverelaxis]

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!

[@raphulali8937]

why you so less suscriber 😐she deserves more

[@tunaylmaz7405]

i am watching this like 30 minutes before my quiz and what was i doing love it so much easier

[@Anders01]

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.

[@adenm8963]

Basically the classic "This statement is false" paradox

[@Fine-py3tc]

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.

[@paulblart7378]

I'll admit that this video's explanation could have been a lot better but the proof is still there.

[@BoazNahumPlus]

Awesome video. This should be used in lessons. Love it!

[@Kraboobee]

I feel so bad for the sad H :( thanks for the great explanations!

[@shogunrua1040]

Thank you! I finally understood what it means.

[@therightfulobstacle8297]

It's like, "I am Lying... Is this statement a truth or a lie?"

[@arthursouza420]

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.

[@matthewhanson5634]

Thank you for this, excellent explanation, I actually understand the issue now!

[@darshanpoudel3125]

Great Explanation ✨

[@paulblart7378]

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.

[@saikoushik4064]

Easiest and Cute explanation

[@shivanggarg2270]

this was awesome genuinely

[@zexceed65]

great audio and video representation

[@sahilghuge5302]

can u suggest some really good books to get notes on this topic?

[@Noobnuker1]

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.

[@snipebuddy]

very underrated

[@byzantinegold]

Wow. This a such a good video, and I’m only half way through.

[@ShaheenSultana-p9p]

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❤.......

[@diegomeza6160]

Beautiful!! Keep making videos!! Mabe one explaining the Entscheidungsproblem or Type theory would be great!

[@dariy1999]

Really good explanation

[@rishipoonia7374]

Great explanation, good job!

[@dmfh5646]

Amazing explanation. Thank you!

[@jorandebraekeleer7557]

Very nice explanation & animation!

[@daleraz3506]

Very cute channel btw. I've been studying AI for almost two years and will definitely recommend your channel to all new cs students (:

[@Jose-yt3qz]

The halting problem becomes apparent when you hear the word 'forever'. The program would run forever and never get a 'not stuck'.

[@user-nb2yk9kf9k]

But if D follows what H says, instead of doing the opposite, will it solve the problem?

[@vhmix379]

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.

[@nickr753]

This only seems to prove that the halting problem is incoherent, because the behavior of a program is dependent not just upon the program’s logic, but also upon its inputs. Was there ever shown to be a proof that it is impossible for a program to statically analyze whether a program, given a set of inputs, will terminate or not?

[@paulblart7378]

Not that I know of, though I'm not sure what you mean by that. The halting problem only proves that it's impossible to write a program that can correctly determine if another program halts or not on some input, given ANY program.

[@-ChiragP]

Finally understood this thank you so much

[@Sydrooo]

Fantastic video and amazing visuals!!! :D

[@meganbytes7650]

Thanks for the help. It's really help me to understand more. Very good animation, I really like this.🤖

[@redice8928]

In fact, the halt 'D' depends on which program 'H' will take. If first program halts then inner 'D' will never stop, then 'H' tells it and last 'D' will halt. I don't see any contradictions

[@paulblart7378]

The contradiction is that H is never right about D halting or not. If H predicts that D halts, it doesn't, and if it predicts that D doesn't halt, it does. D is a counterexample to H, proving that it can't exist.

[@neerajshah7781]

Omg this video is best! Love the way u explained! ❤❤😊

[@protonproductions]

I jave a question, why are we putting that programme D that negates whatever H says in the first place?

[@ericzheng4815]

D can take any program. We are inputting D into D just for the contradiction.

[@可惜前]

Thank you lydia!

[@photoshoppe5223]

Here is why I think Turing was wrong. The D machine returns the opposite of the output of the H machine; if H decides the sequence halts, it prints ‘yes’, which D opposes by looping forever. If H decides ‘no’, D halts. Now, the output from D is fed into itself, and it contradicts itself. So far so good. But we quickly see that this is the case with any value we might want to input, and any such machine. Say we take the colors purple and orange; if the color-machine (call it C, the equivalent of H) decides the color is purple it prints purple, if it is orange it prints orange. Now the opposition machine (call it O, working just like D) opposes that output by printing the opposite. Now if we feed the result into that joined machine (with C being inside O), what we get is a contradiction. And yet it is perfectly possible to create a color-deciding machine. So this way of thinking does not prove anything. And this is why I think Turing was wrong.

[@_okedata]

You don't get a contradiction. In your case if i give O and orange object it prints purple, and if i give it a purple object it prints orange. nothing wrong with that. assume that we can give any object, including programs a color. if O is orange then when i give O itself it prints purple, if O is purple it prints orange. both scenarios are possible and do not cause any contradictions so C could correctly determine color(i.e we haven't proven it does, but we haven't proven it doesn't either). In turings case, the property we are reasonig about is the computation that we are doing which is where the contradiction comes from, D will either halt or loop, and in both scenarios H is wrong, the contradiction is we said H is always right but it was wrong. we said H is always right, we did logically valid things and concluded H was wrong since making D is a vlid thing to do H always being right cant be true.

[@ashishgoswami6303]

My god, kids these days probably 2 years into their Engineering deciding whether Alan Turing was wrong. Study TOX

[@jeevansch.5599]

This is so good Best content in my opinion

[@Fury_42]

beautifully explained, thank you!

[@klazouski]

Alan Turing: it's impossible to create a program that would determine whether another program halts Me: okay. That interviewer at FAANG: write a program that would determine whether another program halts, otherwise we won't hire you

[@paulblart7378]

This is probably a joke, but that's definitely a valid interview question. This proof only says that a universal H can't exist. There are more specific algorithms and computational models where it is indeed possible to determine if they halt or not

[@masterprattu]

Great video!

[@sahilghuge5302]

OMG loved your video!! thanks a lot

[@flo0778]

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

[@prasannasagarregmi1720]

Then for the contradiction, the Machine D doesn't have to take D's program as thr input , does it ? As it is doing basically the opposite of what H says , it still contradicts .. Help me guys

[@Zeddy27182]

"D does the opposite of what H says" is not a contradiction at all if that was the purpose of D. Think of the example that convert 0 to 1 and 1 to 0. BUT, if you assume that you can make a TM H that gives you always a RIGHT ANSWER that whether other programs halt or not, then it gives you a contradiction.🙂 I hope this helps.

[@muhammedgold3]

this is an awesome explanation, thanks :)