# How does an enumerator for machines for languages work?

In Dexter C. Kozen - Theory of Computation (2006, Springer) page 319 exercise 127 he says :

"A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks."

How exactly do you do what he is talking about for any r.e. collection of functions/languages (or complexity class like P)--enumerate the machines that solve the languages in the collection? Normally, when speaking about an enumerator, you talk about enumerating the words of a language, not a collection of languages.

The enumerator goes over all pairs $$(T,p)$$, where $$T$$ is a Turing machine and $$p$$ is a polynomial. For each such pair, it creates a new machine $$M(T,p)$$ which simulates $$T$$ for $$p(n)$$ steps (where $$n$$ is the input length), and then halts. The machine $$M(T,p)$$ is guaranteed to run in polynomial time, and so whatever language it accepts is in P. Conversely, for any P-time machine $$T$$, there is a polynomial $$p$$ such that $$T$$ and $$M(T,p)$$ are equivalent, and so the enumerator goes over all languages in P.