The Padding Lemma
StatementProp. Given a TM , exists an infinite computable subset so that In other words, for any TM we can computably find infinitely-many other turing machines that act the same. Since is finite and bounded below, this entails that in particular we can finite infinitely-large copies of , hence the name ‘padding lemma’. Note that this lemma rests relative to choice of indexing . In most cases this lemma will hold.
DiscussionThis theorem isn’t really that interesting. Given some we can compute these copies by adding extra states to which do nothing. Done. Note that this strategy again rests on choice of . If our indexing were injective1, for instance, then this would fail (and the padding lemma would also not hold).
Apparently there does exist an injective computable enumeration of TMs. See Richard M. Friedberg, Three Theorems on Recursive Enumeration, The Journal of Symbolic Logic, 23,3,1958 (doi.org/10.2307/2964290)