8. Undecidability

MIT 18.404J Theory of Computation, Fall 2020
Instructor: Michael Sipser

Quickly reviewed last lecture. Showed that natural numbers and real numbers are not the same size to introduce the diagonalization method and used it to prove acceptance problem for TMs is undecidable. Introduced the reducibility method to show that HALT for TMs is undecidable.

License: Creative Commons BY-NC-SA

[chimetone]

Thank you Michael for actually explaining concepts like an actual person not a huge terminology word dump like my teachers do

[stvqbhxjnmmqbw]

Professor laughed 2 times. First time when a student said Cantor went crazy and second time when a student wrote cannabalism for feeding TM into TM

[mr_vazovski]

1:02:16 you indeed made me feel bad for choosing (c). This by far the most humiliating check-in yet.

[SuperMusikstar]

Mister Sipser, I'm honoured to have the opportunity to watch your lectures.

[williammoyle]

Wish my professor taught like this I'm cramming for my final and this lecture series is saving my life haha

[karankumarmageswaran]

"Somebody got it. It's i^ith power. let's not get hung up on that please."
literally half a second later:
"i^ith oddly enough can be seen as a real number if you define the imaginary exponentiation, which is weird."

[ethernet]

All this theory hurts my head 😂

So if I understand correctly:
1. By definition A(TM) is recognizable, since TM recognizes A
2. We proved that A(TM) is undecidable, using the diagonalization method
3. We proved that if A(TM) and co-A(TM) are recognizable, then A(TM) is decidable
4. But since we already proved that A(TM) is undecidable, via #2, therefore co-A(TM) cannot possibly be recognizable, therefore, co-A(TM) is unrecognizable

[AntoniousAutodidacticasaurus]

Check-in 8.1> b! Even the logic we use is arbitrary but math is just deduction from arbitrary axioms. The only way you could decide this question is to make it empirical. That is to say, whatever logic and whatever set of axioms we use should be the one that is most predictive of observed experience!

[SunShine-xcdh]

Is you infinite mapping function decideable? Or do you just assume it's truth?

[dtung]

For some reason I think the proof that A_{TM} is undecidable has nothing to do with countable and uncountable. Don't know why it needs to argue that the number of all language is uncountable and the number of all Turing machine is countable. The diagonalization method also is quite different from Cantor's.

[himeyprogramming]

I requested this video and I am the first person to comment

[gloverelaxis]

absolutely loved this lecture. so many elegant ideas! witnessing ⟨D⟩ being fed into D felt as mindblowing as learning the Y-combinator