we will prove that the language ALLTM = {(M)| M is a TM such that L(M):...

Transcribed Image Text:

we will prove that the language ALLTM = {(M)| M is a TM such that L(M): Σ} for some alphabet Σ is not recognizable or co-Turing recognizable. We will use the language ATM = {(M,w)| M is a TM and M accepts w} for this purpose. a) (4 points) Give a mapping reducibility from ATM to ALLTM In other words, prove that ATM SM ALLTM- b) (2 points) Based on part a) explain why ALLTM is not co-Turing recognizable (i.e. ALLTM is not recognizable)? c) (3 points) Give a mapping reducibility from ATM to ALLTM. In other words, prove that ATM SM ALLTM- d) (1 point) Using your answers to parts a,b and c, explain why ALLTM is neither recogniz- able nor co-Turing recognizable. we will prove that the language ALLTM = {(M)| M is a TM such that L(M): Σ} for some alphabet Σ is not recognizable or co-Turing recognizable. We will use the language ATM = {(M,w)| M is a TM and M accepts w} for this purpose. a) (4 points) Give a mapping reducibility from ATM to ALLTM In other words, prove that ATM SM ALLTM- b) (2 points) Based on part a) explain why ALLTM is not co-Turing recognizable (i.e. ALLTM is not recognizable)? c) (3 points) Give a mapping reducibility from ATM to ALLTM. In other words, prove that ATM SM ALLTM- d) (1 point) Using your answers to parts a,b and c, explain why ALLTM is neither recogniz- able nor co-Turing recognizable.