Answer question 3

Let M be a TM. Call M a narcissistic TM if L(M) = {(M)}: in other words, the only string that M recognizes is its own description. We will assume, without proof, a theorem called the "recursion theorem" (see Sipser Chapter 6 if you're interested): any TM has the ability, as its first step, to get its own description as a string. (a) Show that a narcissistic TM exists. (b) Let L = {(M): M is a narcissistic TM}. Prove that L is not recognizable, and that L is not recognizable. I am concerned that my Python program is too complicated, and can be simplified without changing its behavior. It would be nice if I can check whether there is such a simpler program. We aren't concerned with what "simplified" means other than the size of the program. Let L = {{P): P is a Python program and there is no other Python program smaller in size than |(P)| with language L(P)}. Show that L is not recognizable