1)We know by rice's theorem that none of the following problems are decidable.However,are they recursively enumerable,or non-RE?
a) IS L(M) infinite?
2)If we can only show: if x belongs to A, then y does not belongs to B;explain the logic why it is not enough to show A reduction B.IN other words why the theory needs to prove"if and only if"?
3)Show that the halting problem,the set of (M,w) pairs such that M halts(with or without accepting) when given input w is RE but not recursive.