retagged by
695 views
0 votes
0 votes

In the "Halting Problem" lecture, the prof. introduced a magic trick to use the fact that there exists no TM that accepts all other TM that accept themselves to prove that the halting problem is undecidable. There he asked to change the algorithm to alternate the answer i.e if the answer is yes change it to no and vice versa. Then he proved that the halting problem is undecidable. I kind of didn't get his magic trick for the proof. It would be great if somebody can shed some light on it. Thanks!

https://www.youtube.com/watch?v=e9zzY7uqT8g

retagged by

Please log in or register to answer this question.

Related questions

5 votes
5 votes
0 answers
2
Mk Utkarsh asked Jan 8, 2018
1,051 views
How many n length base 10 numbers are there with at least 3 zeros?
1 votes
1 votes
1 answer
3
GautamDas asked Apr 4, 2017
552 views
What if we use queue data structure instead of stack data structure in Push Down Automata? How can we simulate queue data structure in PDA?
0 votes
0 votes
1 answer
4
Anand Vijayan asked Dec 12, 2016
1,334 views
In Shai Simonsons video lecture series , the last few videos are titled as follows : Complexity Theory, Quantified Boolean Formula,Savitchs Theorem, Space hierarchy ,Deci...