do part (a) only

PROBLEM 1: UNDECIDABILITY (a) Show that A = {(M) | M is a TM that halts on } is undecidable. Do not use Rice's Theorem (b) Is A Turing-recognizable? Prove your answer (c) Show that {(M) | L(M) = *) is undecidable. You may use Rice's Theorem if you wish (d) Which of the following languages are undecidable? Al = {(A) | M is a Turing Machine that has an even num ber of states } Ag = {(Mi, Ma) I M ,My are Turing Machines and L(M) UL(M) = *) Ag = {(M) | M is a Turing Machine and L(M) is finite } A4 = {(M) | M is an DFA L(M) is finite } As {(11) | M is a TM having a configuration sequence ending in qACCEPT}