Undecidability of the Halting Problem 

But, its because of our program c na? Didn't we write so? Why are we saying it is contradiction at last instead of the time we write it initially as C.

@@Thahira-yc2ys yeah. exactly my doubt too

Thank you for the explaination! I was getting pretty confused until you explained it further

It is funny that some people think Quantum computer can solve the halting problem

@@akankshasharma7498 I find it possible by quantum computer because the property of Q-bits, you tell me why do you find this funny ?

@@niteshswarnakar my bad, missed a "comma" 😩. I meant the conversation between Turing and schrodinger, you wrote about, is 2× funny acknowledging some people think that Quantum computers can solve the haunting problem

@@niteshswarnakar if I may ask, why do you think that Quantum Computer can solve the haunting problem? I don't have an opinion on that btw, in the morning I think they can, by the night I think they can't 🤣🤣🤣🤣🤣. It is "undecidable" for me 🤣🤣🤣

@@akankshasharma7498 well your undecidable thought is actually funny for me. Thank you for the response :)

what if i write in if return and in else loop forever?? i think i didn't understand this can u help?

@@AmitSingh-1916 But we have to show it is wrong so by that particular thing we showed H is wrong now in general we cannot say H exist for such question

If you suppose H exists, then you create C and C(C) is absurd, so H shouldn't exist

i might be 1 year late but i'll still try, pretty sure it is because a program that does not halt is impossible just like we saw in the video (i guess it's because it has to run infinitely to give a conclusion that it doesn't halt cuz that's the meaning of not halting)

This is all based on contradiction. If we pass C itself theres twos options, either halting or not halting. If it halts it will loop forever and if it's not halting it will halt. In my head it makes sense

It is an independent statement. example: for(int i=5; i>=0; i++);

@@LasradoRohan no but why we need to write this loop only can't we write some loop which will terminate please can you explain I would be glad to know the answer

@@sadhnasharma1000 because we want to show that there is a contradiction, and the only way to do that is if there is a loop (i.e. does not halt) for when H(X,X) says the program will halt. So it has to be opposite to the result of H(X,X).

If you find a single counterexample or contradiction to a given property, then that property is false. In this case, we have the counterexample in the video already, there's no need to consider the case where the branches are switched. If you consider the case where you do switch the branches, no, there isn't a contradiction, but that still doesn't tell us anything about the nature of H.

@@mohitshresthanep Okay.But if u consider the situation logically if(H(x,x)==halt) ,then it should return not loop forever

@@adityaraj5678 If H exists, it should be able to work for all kinds of inputs. One of the inputs is the program C where it fails. Hence, H cannot exist. We are creating a paradox here.

@@mohitshresthanep thank you so much for explaining!

You just need one example to prove contradiction here

Practically, this sort of problem can occur in a way that’s not as blatant as this. The contradiction could be hidden, and regardless of what the program is, a program that detects whether it should halt should simply detect everything and figure it out. But it can’t figure it out because it will always be wrong. The contradictions are only so explicit because Sir is trying to explain them. In reality, it could be much more complex than that.

There is nothing wrong in this video he has actually proved it if you can't understand it then watch it twice or thrice... Don't be disrespectful he is providing free education, show some respect...

@@Rahulsingh-bu6jh He's just making fun of the concept not the person who made the video. It's actually funny; no disrespect.

@@coop4476 naah I don't think so he is making fun of the person

Good question - I believe the answer is no for a variety of reasons. I think the simplest one is that to return a value of undecidable, the program would have to halt to do so. If we think about how a Turing machine is defined, it has set of states. Two special states are { q_acc, q_rej }. Any other state "q_i" is a state that continues the computation. To reach a conclusion, the program has to halt. Therefore, for the program to terminate on the state that means "undecidable", it would have to halt to do so. Another way to approach this would be to think about what the machine you're proposing would imply. If we could build a machine that says "H(P, I) == undecidable", then "not H(P, i) == decidable", thus implying that negating the program proposed would mean that we have built a machine that can determine decidability. I know youtube can be full of mean spirited comments, but I sincerely intend this comment in good faith. Happy computing!

I too felt the same way but the textbook I use says such assumptions are alright.

the theory says that every program(P) is a string ( a combination of characters). therefore, it can be passed as a string( I ) . Think about a program that you write in C or Java. It's a string

I think you and me are studying in the same university.

Really? Where are you studying?

she said "same university" : |

You're passing the result of a function (H) to a function (C) which is different than passing the definition of a function to a function (that check whether the passes definition can/will always halt)

@@LasradoRohan Ummm The definition of a funtion to another function, I think you need to give more background explaination than that??

@@yunfeichen9255 This might sound a bit weird, but bear with me... Imagine a datatype "function". A variable (object) of this datatype has the ability to store the exact steps to be followed and value to be computed and returned when that object is "called". Say, a function is defined as int f(int a, int b) {return a+b;} So when I pass 'f' to another function say 'g', by doing g(f), I'm giving it the "definition" of that function. But, when I pass f(1,2) to 'g', by doing g(f(1,2)), I'm giving it the value/output (1+2=3) of 'f' evaluated on inputs 1 and 2. Here, they define 'H' as: H(function f, string s){ if("f halts") return 'Halts' else return 'Doesn't Halt' } and define 'C' as: C(function f){ if(H(f, 'some string') == 'Halts'){ //start running an infinite loop } else{ //do something non infinite } } Therefore, calling C(C): For the if-condition it needs to evaluate the value of H(C, 'some string') But, we don't know the value after evaluation. Case 1: Say 'H' somehow determines that 'C' always halts. But this leads to an infinite loop being started, So we know 'H' was actually wrong. Case 2: Say 'H' somehow determines that 'C' will never halt. But this leads to a direct return statement, immediately halting C, So we know 'H' was actually wrong again. Therefore the function 'H' can't 'Decide' if 'C' halts or not. Therefore, the problem is proven undecidable, as there exists no function 'H' that can (algorithmically) solve the halting problem.

@@LasradoRohan "So when I pass 'f' to another function say 'g', by doing g(f), I'm giving it the "definition" of that function." How can you pass a function that has two parameters with none?? The compiler will say undefined function??

​@@yunfeichen9255 The thing is, H and C aren't defined as directly compilable code. They are actually a high-level encapsulation of some algorithm. So when we say, "we can define 'H'", it means some algorithm can possibly be written that will go through the given definition of a function and determine if it halts. Also, note that here we write the definition as an algorithm, which is not code (like in some programming language). So the parts of the algorithm may sometime become "high-level" thus ignoring some implementation details. You might be wondering, how is it ever possible to pass the definition of a function. One way to imagine would be, passing the exact code as a string. Now, there will be some "mini-compiler" inside function receiving the string which will help it to "understand" what the code from the string means, just like any compiler that you might be using. So when we say, the halting problem is decidable, we mean that the "assumed-to-be-existing-and-working-correctly" function 'H', has the ability to look at the definition (possibly as above) and use what it understands to "decide" between 'Halts' and 'Doesn't' halt. A side fun fact: it is actually possible to pass functions as I said, in some languages like C++, python (basically languages that treat functions as objects or allow objects to behave like functions). But, it is not the same as "passing code in a string" method I explained above. This is because these passed "function-objects" usually encapsulate and hide the code they run within themselves. Here's where, "passing code in a string" is more understandable.

BRUHHHHHHHHHH XD

kaka please explain loop forever part. why is it there?

@@kowshicroy1418 He used loop to prove that the program does not halt forever!!

@@arvind7966 guru thank you. but got S in the subject 😇😇😇

@@kowshicroy1418 I have to write exam today!!!

@@arvind7966 best of luck kaka!!!

exactly....Da fuk?? What is going on in this lecture???

Siddharth Singh Theoretical CS is one of the most beautiful areas in the entirety of Computer Science, this property is one of the most central and classical properties of computer science that has large implications on the art of problem solving and computation in general.

the whole thing is like trolling, we make the whole new TM C(ontradictor) that combine the halting machine H (that accept machine and input to simulate whether that machine will halt or loop with the input) to function that do the opposite result of H afterward, so when you feed input C into C machine for H, no matter the result H have reached, C will always gives the opposite result

Exactly what i was going to comment

Same

It absolutely doesn't

You're wrong, don't confuse people. If so, where is the contradiction?