I am so jealous of people that get to learn from profs like this. Sipser just cleared up an error in my understanding of decidability that 40 hours of studying my professors slides and lectures couldn't.
Mister Sipser, after almost watching half of your lectures on theory of computation I have to say that you are the GOAT lectrurer of this course. Thank you!
At 1:01:55 on checkin 9.5, I'd like to give you guys a intuition on why it is true. It's true because if you look at the definition of a T - recognizer, it says -: 1. Halts and accepts 2. Halts and rejects 3. Loops and rejects Now, Let A be T - recognizable and O be it's recognizer. Suppose w is a string not in A. Now, when you look Ā and it's recognizer Ō( Ō is implemented using O, it does opposite of what O does) and pass w through it, it should accept w, but since you're implementing Ō with the help of O, it loops on w and rejects it. Therefore it's not always possible for Ā to be recognizable if A is. Infact it's possible on a special condition, which is A must be a decidable language.
I think, in general if A reduces to B by general reduction, then B is recognizable => A is recognizable iff B is decidable. I'm not sure about this one though, one can argue.
A general intuition without involving compliments and stuff would be. General reducibility reduces the given problem into some form of a know problem whereas mapping reducibility reduces not only the problem, but also the input (sample space of strings) into equivalent inputs. So, if B is recognizable and A is mapping reducible to B, then we just convert A's inputs to B's input, hence A becomes recognizable. But if it's general reducible then, B is recognizable doesn't imply A is recognizable because there might be some strings in A which would get rejected by looping.
The best explanation I found to understand it, is in the book, in example 5.27: there is noted, that when using general recursion you are often using the complement of the problem, and not exactly the problem as "B". The theorem 5.2 in the book is proved like that, the output of the E_TM is inverted. This inversion makes the general reducibility to fail in proving recognizability. If you make no inversion, then you can also use general reduction to prove recognizability. It is just tricky and error prone.
I don't understand why at 1:07:16 we are keeping the same TM Mw. If we want in Atm complement, don't we want to accept when x != w, else run M on w, and accept when M rejects? Don't we want when M does not halt on w (the complement of Atm)?
Recall that A M does not accept w (i.e., M rejects or runs forever on w). f() in E_TM ==> f() outputs an encoding of a TM M_w where L(M_w) = {} (i.e., f() = ). So, f must have input and output where L(M_w) = {} if and only if M does not accept w. Note that the converse must be true as well: L(M_w) =/= {} if and only if M accepts w. If we look at the implementation of M_w, we see that if M accepts w, then L(M_w) = {w}. Otherwise, if M does not accept w, then L(M_w) = {}. If we output TM M_w, we have the function f that satisfies Complement(A_TM) or some other letter.
The main difference is that in general reducibility you simulate B, in mapping reducibility you don’t have to simulate B you just change the input. For decidable is the same, but when it’s recognizable and it can loop it makes a huge difference. Hope it helps 🙌🏾
Based on the lecture, I feel it might be instructive if one can use mapping reduction method (instead of general reduce method) to reduce A_{TM} to HALT_{TM}. That is exactly what textbook Example 5.24 does. And it also confirm my suspicion that it is easier to prove (at least more consistent).
When showing EQ_tm is unrecognizable, we create T_w. If T_w is a machine that does not halt, can we say that it is the same as a machine that always rejects? In other words, can we consider a machine that always loops and a machine that always halts and rejects to be the same?
In the proof for "E_TM is undecidable" in the construction of M_w you don't even need to Check, whether x != w. You can Just Run M on w for all x. Then the language of M_w is either Sigma* or empty.
I am so jealous of people that get to learn from profs like this. Sipser just cleared up an error in my understanding of decidability that 40 hours of studying my professors slides and lectures couldn't.
Mister Sipser, after almost watching half of your lectures on theory of computation I have to say that you are the GOAT lectrurer of this course. Thank you!
Studying for midterm for CS class and Prof. Sipser's videos are absolutely GOLD
At 1:01:55 on checkin 9.5, I'd like to give you guys a intuition on why it is true.
It's true because if you look at the definition of a T - recognizer, it says -:
1. Halts and accepts
2. Halts and rejects
3. Loops and rejects
Now,
Let A be T - recognizable and O be it's recognizer.
Suppose w is a string not in A.
Now, when you look Ā and it's recognizer Ō( Ō is implemented using O, it does opposite of what O does) and pass w through it, it should accept w, but since you're implementing Ō with the help of O, it loops on w and rejects it.
Therefore it's not always possible for Ā to be recognizable if A is. Infact it's possible on a special condition, which is A must be a decidable language.
I think, in general if A reduces to B by general reduction, then
B is recognizable => A is recognizable iff B is decidable.
I'm not sure about this one though, one can argue.
A general intuition without involving compliments and stuff would be.
General reducibility reduces the given problem into some form of a know problem whereas mapping reducibility reduces not only the problem, but also the input (sample space of strings) into equivalent inputs.
So, if B is recognizable and A is mapping reducible to B, then we just convert A's inputs to B's input, hence A becomes recognizable.
But if it's general reducible then, B is recognizable doesn't imply A is recognizable because there might be some strings in A which would get rejected by looping.
The best explanation I found to understand it, is in the book, in example 5.27: there is noted, that when using general recursion you are often using the complement of the problem, and not exactly the problem as "B". The theorem 5.2 in the book is proved like that, the output of the E_TM is inverted. This inversion makes the general reducibility to fail in proving recognizability. If you make no inversion, then you can also use general reduction to prove recognizability. It is just tricky and error prone.
58:37
- "The right answe is winning, but not by much.. I suppose I shouldn't be laughing about it" 😂
Sipser is an amazing professor, helping clear up all issues in understanding from my university's course. Thank you!
I don't understand why at 1:07:16 we are keeping the same TM Mw. If we want in Atm complement, don't we want to accept when x != w, else run M on w, and accept when M rejects? Don't we want when M does not halt on w (the complement of Atm)?
Recall that A M does not accept w (i.e., M rejects or runs forever on w).
f() in E_TM ==> f() outputs an encoding of a TM M_w where L(M_w) = {} (i.e., f() = ).
So, f must have input and output where L(M_w) = {} if and only if M does not accept w. Note that the converse must be true as well: L(M_w) =/= {} if and only if M accepts w.
If we look at the implementation of M_w, we see that if M accepts w, then L(M_w) = {w}. Otherwise, if M does not accept w, then L(M_w) = {}. If we output TM M_w, we have the function f that satisfies Complement(A_TM) or some other letter.
The main difference is that in general reducibility you simulate B, in mapping reducibility you don’t have to simulate B you just change the input.
For decidable is the same, but when it’s recognizable and it can loop it makes a huge difference.
Hope it helps 🙌🏾
34:45 - Mapping reducability
Based on the lecture, I feel it might be instructive if one can use mapping reduction method (instead of general reduce method) to reduce A_{TM} to HALT_{TM}. That is exactly what textbook Example 5.24 does. And it also confirm my suspicion that it is easier to prove (at least more consistent).
When showing EQ_tm is unrecognizable, we create T_w.
If T_w is a machine that does not halt, can we say that it is the same as a machine that always rejects?
In other words, can we consider a machine that always loops and a machine that always halts and rejects to be the same?
How are we using reducibility to solve undecidable problems if we are using proof of contradiction?
51:37 wrong explanation? (it is surjective but not bijective?)
No it is not surjective. since the rule is (w in A) iff (f(w) in B). Therefore the Range of f is not necessarily equal to the co-domain
This guy is an excellent.
A is reducible to co-A implies that Atm is reducible (general) to co-Atm. Is this really the case?
Is reducibility symmetric? Thanks for the great video.
No. It may be for some pairs of problems. But not necessarily.
21:36
so good
In the proof for "E_TM is undecidable" in the construction of M_w you don't even need to Check, whether x != w. You can Just Run M on w for all x. Then the language of M_w is either Sigma* or empty.
You are right but I thing the way he show it is more didáctica. Uwu
1:02:26
You are best
The break isn't a break lol