Turing Machine lecture content stan..

Question

A = { <M,w> | M is a TM that accepts W}

what is A’( A complement)?

 

Pls guide :  M is a Tm doesn,t  accept w,

 Unable to approach further

 

 

Source:https://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/20/Small20.pdf

Comments

M is a TM that accepts W

then in TM yes ans is possible

So, language is RE

Complement of it may or maynot RE 

Answer 1

A' may or may not form a TM , it depends which type of lanague is accepted by TM ( if recursive then A'  will form a TM but as here  no reference is provided - we assume the languge is REL hence A'  may or may not be REL as REL are not closed on complement )

Comments

"   A' may or may not form a TM  " may you please elaborate further

---

@Learner_jai A" ( complement of A) may or may not for tm