Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
I am a bit confused at the end when you come to the conclusion that A/TM is undecidable. Because the steps are ran in a finite amount of time we assume that A/TM is decidable if E/TM, but because A/TM is undecidable there is no way E/TM can be decidable. How do you come to that conclusion for A/TM being undecidable, is it because when we run E on
We say that ATM is undecidable simply because it is a problem that has already been proven to be undecidable. This makes it a good baseline for testing decidability of other languages in relation to ATM. So, showing that a problem P being decidable allows ATM to be decidable (which we already know is not possible) helps us realize that P can't be decidable. It's kind of like if I wrote a book proving 1 + 1 = 0. Since you already know 1 + 1 can't equal 0, you can use that fact to prove that my proof is flawed.
It won't matter here, because all that we are doing is *constructing* the machine, not running it. A hypothetical decider must be able to deal with the fact that the input TM to it might run forever, if that decider ran the given TM.
E is a TM that takes in an encoded TM, say , and accepts if L(M) is empty. You do not feed an input to M because you are sending the machine itself to E, you are not running M on any particular input. The decision E makes depends on no particular input feeded to M, it is a general statement about all inputs of M. E asks "Is it true that there is no input this machine M accepts?"
Answering your final request (2 years later): You have constructed M′ in a way that "L(M′) = ∅ ⇔ M rejects w" and assuming that E is a decider for Empty/TM: Your machine accepts ⟨M,w⟩ ⇒ E rejects ⟨M′⟩ ⇒ L(M′) ≠ ∅ ⇒ M accepts w Your machine rejects ⟨M,w⟩ ⇒ E accepts ⟨M′⟩ ⇒ L(M′) = ∅ ⇒ M rejects w These mean Your machine is a decider for Accept/TM which is a contradiction. Therefore the assumption is false and therefore Empty/TM isn't decidable. Right ?
In case if Turing machine M accepts all binary strings can we prove by just changing the last two steps in the videos i.e, say if E accepts accepts , if E rejects rejects?
plz make a video a on recognizeable and unrecognizable languages, if u already made plz provide me the link.. thnk u ,, I'm ur new subscriber from this video
I have a simpler construction of M'. Just ignore the input x and simulate M on w. If M accepts w, then accept, otherwise reject. Now if M accepts w, M' will accept all strings otherwise L(M') = ∅.
Thanks to my supporters Yuri, vinetor, Ali (UA-cam) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.
I am a bit confused at the end when you come to the conclusion that A/TM is undecidable. Because the steps are ran in a finite amount of time we assume that A/TM is decidable if E/TM, but because A/TM is undecidable there is no way E/TM can be decidable. How do you come to that conclusion for A/TM being undecidable, is it because when we run E on
We say that ATM is undecidable simply because it is a problem that has already been proven to be undecidable. This makes it a good baseline for testing decidability of other languages in relation to ATM.
So, showing that a problem P being decidable allows ATM to be decidable (which we already know is not possible) helps us realize that P can't be decidable.
It's kind of like if I wrote a book proving 1 + 1 = 0. Since you already know 1 + 1 can't equal 0, you can use that fact to prove that my proof is flawed.
Open CERN. Just kidding Thankyou for the vids. Much appreciated
step (b). What if M loops on w? So it's looping and we don't know is it going to accept, reject or loop forever.
+1
It won't matter here, because all that we are doing is *constructing* the machine, not running it. A hypothetical decider must be able to deal with the fact that the input TM to it might run forever, if that decider ran the given TM.
@@EasyTheory So can we say here is given M here is the A_TM ?
6:21 I don't understand (2) Run E on ? What is the input that we feed M'? When do we feed that?
E is a TM that takes in an encoded TM, say , and accepts if L(M) is empty. You do not feed an input to M because you are sending the machine itself to E, you are not running M on any particular input.
The decision E makes depends on no particular input feeded to M, it is a general statement about all inputs of M. E asks "Is it true that there is no input this machine M accepts?"
@@alexm.2960 thank you！
Answering your final request (2 years later): You have constructed M′ in a way that "L(M′) = ∅ ⇔ M rejects w" and assuming that E is a decider for Empty/TM:
Your machine accepts ⟨M,w⟩ ⇒
E rejects ⟨M′⟩ ⇒
L(M′) ≠ ∅ ⇒
M accepts w
Your machine rejects ⟨M,w⟩ ⇒
E accepts ⟨M′⟩ ⇒
L(M′) = ∅ ⇒
M rejects w
These mean Your machine is a decider for Accept/TM which is a contradiction. Therefore the assumption is false and therefore Empty/TM isn't decidable.
Right ?
Thank you so much! this is very helpful to me!
Great explanation
In case if Turing machine M accepts all binary strings can we prove by just changing the last two steps in the videos i.e, say if E accepts accepts , if E rejects rejects?
plz make a video a on recognizeable and unrecognizable languages, if u already made plz provide me the link.. thnk u ,, I'm ur new subscriber from this video
What specifically about them? And thanks!
thank u so much!!!!!
哈哈
To answer your final question: Emptiness for Turing Machine is co-turing recognizable
fajnhy film
tak!!!!!!!!!!!!
I have a simpler construction of M'. Just ignore the input x and simulate M on w. If M accepts w, then accept, otherwise reject. Now if M accepts w, M' will accept all strings otherwise L(M') = ∅.