Emptiness for Turing Machines is Undecidable

[@EasyTheory]

Thanks to my supporters Yuri, vinetor, Ali (KZbin) and Bruno, Timmy, Micah (Patreon) for making this video possible! If you want to contribute, links are in the video description.

[@dmitrikoltsov7155]

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.

[@nourankhaled3091]

+1

[@EasyTheory]

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.

[@taylankarakaya3856]

@@EasyTheory So can we say here is given M here is the A_TM ?

[@benjaminrichards303]

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

[@onepiecefan3969]

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.

[@brendawilliams8062]

Open CERN. Just kidding Thankyou for the vids. Much appreciated

[@lowerbound4803]

6:21 I don't understand (2) Run E on ? What is the input that we feed M'? When do we feed that?

[@alexm.2960]

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?"

[@I_hate_HANDLES]

@@alexm.2960 thank you！

[@axonis2306]

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 ?

[@pedrogouveia3111]

Great explanation

[@alicebob5439]

Thank you so much! this is very helpful to me!

[@KaniRaj0707]

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?

[@akramrasheed8666]

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

[@EasyTheory]

What specifically about them? And thanks!

[@samettermin3769]

To answer your final question: Emptiness for Turing Machine is co-turing recognizable

[@谷悦鸣]

thank u so much!!!!!

[@owensanzas9147]

哈哈

[@bartekf4]

fajnhy film

[@bartekf4]

tak!!!!!!!!!!!!

[@KhangNguyen-wj5jd]

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') = ∅.