L15: Proof by Diagonalization that ATM (Halting Problem) is Not Decidable

Proof, by diagonalization, that ATM, the Halting Problem, is not decidable.

[@bazzler13]

Excellent explanation! This is such a life-saver and much better than the rushed, heavily hand-waved explanation I got from my lecturer. Thank you!

[@mattiaricci1524]

Really enlighten, finally I've got the feeling to grasp diagonalization proof. I just hope it won't vanish too fast

[@jackphel]

I appreciate that you posted this lecture. I had misunderstood the lecture at my own school, and watching this lecture I came to understand my error.

[@SemicolonExpected]

I came across this while studying for my finals and this took me back to my undergrad theory class. Much nostalgia for my favorite class. Thanks

[@johnhills8922]

This is a great explanation of diagonalization proof for the halting problem. Great stuff!

[@peteolcott7822]

The video is very similar to the Sipser version. As soon as I saw UC Davis I knew it must be good, because my favorite author is from UC Davis: Peter Linz. I had always mistaken the halting problem diagonalization proof for the same thing as the diagonal lemma so I always ignored it. When I needed to learn it, careful notes of this video was all that was required to gain a complete understanding.

[@constantmarks3187]

Thanks, that was a very good description of the argument.

[@leo2002b]

Great explanation! This helped me finally get a good understanding of this material.

[@musterstudent6746]

very good explanation, thank you. but I think this is the membership problem, not the halting problem. it would be the halting problem if the second table would accept on accept or reject from the first table and only reject if the first table doesnt halt.

[@Gnichs]

Thanks, this video dissolved my confusion over this problem.

[@depresso18163]

FINALLY!!!! Thank you! An explanation I understand.

[@warnford]

Many thanks - I love his lectures on diagonalisation

[@ytpah9823]

Using the diagonalization argument requires endless input, which of course would not be computable. Try it with finite length sets (which in turn would only be relevant for very limited limits of 'finite').

[@jakethomas6123]

It's interesting to compare the two arguments. In the other proof, it is critical to realize that we can pass a program in by reference, otherwise the value we'd be passing into the subroutine would be infinitely long, rendering the proof invalid (would not be able to set up the contradiction because we would never be able to get to it). Also in the other proof, note that the subroutine is "hard-coded" (not passed into the program), but we were free to imagine it as anything. But above, we have a critical difference: the programs may receive input. So, we instead pass a finite description of D into a finite description of D. That does not blow up into infinity if we choose to pass by value: Here, when D is passed into itself, the "inner D" still has variables for what it passes into H. So that keeps an infinite loop from happening in anything we've defined. Conveniently, we don't define H; we assume it to exist for sake of contradiction. So now you know the (or "a") point of having this proof by diagonalization: it shows that you can prove the point without "pass-by-reference", instead strictly adhering to "pass-by-value".

[@Tony-bn7jj]

Great video, very helpful. thanks for sharing!

[@morenon07133T]

Very good explanation, thanks a lot.

[@StepwaveMusic]

I still don't get it, sadly. If D gets input D, which we'll call D1 and D2 respectively, then If D2 accepts, D1 accepts as well because D1 decides whether it's input (D2) is accepted or not If D2 rejects, D1 rejects as well because D1 decides whether it's input (D2) is accepted or not So it behaves just like you want it? I don't understand why the solution would be reject when the input accepts or otherwise.

[@rashmidhant3364]

what are even on about ? D1 for you is a turing Machine and D2 is an input . So "if D2 accepts" is in itself a wrong statement. How can a input accept anything ? And if thats not what you mean, then to what machine is D2 getting accepted to?

[@ZeroG]

But prima facie D is insane because it claims that a boolean output (true/false) could be identical to a non-boolean output (true/false/doesn't halt). So this proof is no good. For the proof to be any good, D must be capable of producing the same type of output as the first table (true/false/doesn't halt). As it stands D could never match the first table for any M so this proof fails. I think this is a misreading of Turing.

[@rashmidhant3364]

Sir said that the first Table is, the Behaviour of all possible Turing machines. The second Table is a table that is the deciding turning machine for the original table. Basically, it tells whether a particular tuple is accepted or rejected in the original table. How? Simple, if by the original table the particular pair would have halted and accept, then the H would give the answer as accepted. If it halts and rejects, then H has answer reject. If it by chance doesn't halt, then basically the Turing Machine was not made for that language and thus its end product should have been halt and reject but rather got stuck in an endless loop due to incomplete halt and reject cases. So H gives the answer as reject. Thus H is a boolean table only and D simply being the reverse of the diagonal of H, is also a boolean table.

[@Fahodinho]

why all these videos are too old

[@learnwithsid2044]

our awesome teacher . i like your video .i need your help .i am stuck can you please help me in this question : Distinguish each of the following axioms as either Peano arithmetic or Presburger arithmetic with proper reason. 1. a×b (a + b) = (a×b) 2. a+ 1 = b + 1 → a = b please if its possible answer me within in one hour . kindly i am waiting for reply

[@trawencz]

I don't think he's going to make it in time