Let the following transformation f which maps each pair consisting of Turing machine M and input w to M to another Turing machine M ,w N? ?. TM M ,w N? ? when given input string x over its input alphabet Σ behaves as follows. M ,w N? ? simulates computation of M on w for |x| steps (where |x| is the length of x). If M doesn't accept within these steps, then M ,w N? ? accepts its own input x and halts. If M accepts during steps, then M ,w N? ? rejects its input x and halts.
1. Assume that M accepts w. What is L( M ,w N? ? )?
2. Assume that M doesn't accept w. What is L( M ,w N? ? )?
3. Use the transformation f to show that language { | N is Turing machine whose language L(N) is infinite } is not recursively enumerable.
4. If you perform reduction in proof of Rice's theorem for special case of property P: "infinite language", does this reduction also show that language P L = { | N is Turing machine whose language L(N) is infinite } is not recursively enumerable? Describe why it does or it doesn't.