效绵 Non-RE Languages Lemma:the set of all TMs is countable. Proof: the set of all strings >is countable,for a finite alphabet >With only finitely many strings of each length,we may form a list of >by writing down all strings of length 0,all strings of length 1,all strings of length 2,etc. each TM M can be described by a finite-length string s <M> Generate a list of strings and remove any strings that do not represent a TM to get a list of TMsNon-RE Languages ◼ Lemma: the set of all TMs is countable. ◼ Proof:  the set of all strings * is countable, for a finite alphabet . With only finitely many strings of each length, we may form a list of * by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc.  each TM M can be described by a finite-length string s <M>  Generate a list of strings and remove any strings that do not represent a TM to get a list of TMs