Equivalence for Turing Machines is neither Recognizable nor co-Recognizable

[@EasyTheory]

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

[@camrws]

good video, just when i needed it

[@philippegauthier5922]

How come when building our mapping reduction we can simply say ''run M on w, accepts if M accepts'' (6.25) when this statement could just loop and never halt?

[@Adam-wt2ws]

If I understand correctly, it's because A_TM is a recognizable language and we're making a mapping for EQ_TM's recognizability

[@ngxtmvre.9261]

we only construct the machine M2 and later return its encoded specification in , the machine itself is never actually run, we are just mapping strings here to demonstrate a reduction

[@nothingatall6882]

but if Atm is recongizable, and Atm < Etm, doesn't that mean Etm is recognizable...

[@nytelin274]

exactly what i need at the moment

[@1HARVEN1]

Thanks for this.

[@imfailing3134]

jesus christ why can't eberly teach us like this

[@HoltWendy-n1i]

Crist Row

[@omerbayramdemir846]

Isn't Atm recognizable by a Turing Machine ?

[@lionelmayhem]

Correct, but since Atm' isn't (else Atm would be decidable), we can say that EQtm also isn't recognizable.

[@nothingatall6882]

but if Atm is recongizable, and Atm < Etm, doesn't that mean Etm is recognizable...

[@nothingatall6882]

@@lionelmayhem but if Atm is recongizable, and Atm < Etm, doesn't that mean Etm is recognizable...