Non-RE Languages Lemma the set of all tms is countable Proof o the set of all strings 2* is countable for a finite alphabet 2. With only finitely many strings of each length, we may form a list of 2* by writing down all strings of length 0, all strings of length 1, all strings of length 2, etc o each tM M can be described by a finite-length string s <M> o 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