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.

[@TypicWhisper]

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

[@roxferesr]

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

[@offeibekoe452]

The explanation is wrong though

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

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

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

[@shadmantabib5014]

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

[@HiJackLeeLee]

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

[@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?

[@MATHONG]

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

[@dsareis9134]

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

[@dsareis9134]

I enjoyed all the videos I watched on your channels

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

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

[@illyushen9856]

Why did ye stop making videos

[@breathemath4757]

This deserves one million more views. Thank you.

[@azzarox6661]

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.

[@miguelsr4272]

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

[@reemaj2482]

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 ❤

[@offeibekoe452]

This explanation is wrong 🙏😭

[@reemaj2482]

@offeibekoe452 which part is incorrect? 😭🙏

[@reemaj2482]

@@offeibekoe452 please explain🙏🙏🙏

[@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")

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

[@omegahaileyesus]

Easily the best explanation I’ve seen

[@amritborah2773]

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

[@tejas.873]

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

[@breezyx976]

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

[@aavashkuikel1341]

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

[@kid_kulafu_1727]

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

[@sahaneakanayaka3394]

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

[@Ms_Ink]

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

[@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 😇

[@_yomiadebowale]

This person has to be the best teacher ever!

[@noname60605]

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

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

[@Ananyalatchupatula]

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

[@thecsmedic]

3 years later and this is making things soo understandable

[@mastadodo]

Simple and intuitive explanation, thank you very much!

[@AbdoulieTamba]

Easiest explanation I've seen so far.

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

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

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

[@paulblart7378]

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.

[@Anders01]

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

[@paulblart7378]

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

[@Anders01]

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

[@paulblart7378]

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

[@saichaithrik7134]

One of the greatest explanations ever thanks for the video

[@vijaykumar-cz7ot]

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

[@AkikoHaruki-i5o]

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

[@paulblart7378]

I don't like any of these visual proofs on youtube. I think the formal mathematical proof is much easier to understand.

[@offeibekoe452]

Because this is wrong

[@paulblart7378]

@@offeibekoe452 It's not wrong. Just confusing

[@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?

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

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

[@mshahidur]

Proof of "everything can be explained". Awesome!

[@Spacexioms]

Best explanation ever, thank you.

[@JessicaReginadosSantos]

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

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

[@dishendra.]

short, precise, easy to understand !

[@UTubeLion]

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

[@NeerajSingh-or9hd]

Crystal clear explanation.

[@byzantinegold]

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

[@MuhammadAbdullah-qi1of]

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

[@TheoriaPraxisPoiesis]

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

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

[@shogunrua1040]

Thank you! I finally understood what it means.

[@saakshimalhotra3926]

Best explanation of this problem

[@tunaylmaz7405]

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

[@raphulali8937]

why you so less suscriber 😐she deserves more

[@shaikingtroy]

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

[@neerajshah7781]

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

[@dmfh5646]

Amazing explanation. Thank you!

[@rajkamalingle9144]

Best Explanation hands down!!

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

[@BoazNahumPlus]

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

[@rishipoonia7374]

Great explanation, good job!

[@meganbytes7650]

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

[@Sydrooo]

Fantastic video and amazing visuals!!! :D

[@diegomeza6160]

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

[@sahilghuge5302]

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

[@dumitruluca3571]

great explanation

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

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

[@dariy1999]

Really good explanation

[@-ChiragP]

Finally understood this thank you so much

[@offeibekoe452]

But D is using H's output as input? So D is running an altered version of the program H read.

[@jorandebraekeleer7557]

Very nice explanation & animation!

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

[@Kraboobee]

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

[@shivanggarg2270]

this was awesome genuinely

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

[@Fury_42]

beautifully explained, thank you!

[@saikoushik4064]

Easiest and Cute explanation

[@zexceed65]

great audio and video representation

[@muhammedgold3]

this is an awesome explanation, thanks :)

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

[@Jose-yt3qz]

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

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

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

[@jeevansch.5599]

This is so good Best content in my opinion

[@sahilghuge5302]

OMG loved your video!! thanks a lot

[@adenm8963]

Basically the classic "This statement is false" paradox

[@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 (:

[@콘충이]

Thanks!

[@masterprattu]

Great video!

[@snipebuddy]

very underrated

[@therightfulobstacle8297]

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