In this book ‘Theory of computation’ By Dexter Kozen on page 313,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 do you do what he is talking about for any collection of languages that is r.e.? How do you represent an r.e. complexity class with a list of TMs? What is an example of an enumerator that does this for any r.e. class C?


1 Answer 1


Its easy to iterate through all turing machines - simply iterate through all strings, and pick the ones that actually represent a TM.

I think its possible to iterate through all $P$ by iterating through all turing machines, and for each one to add a "clock" that counts the number of steps and halts after some polynomial time.

  • $\begingroup$ Can you run these turing machines that you have enumerated? what are you enumerating exactly, a description of them? Can you show me how to do this for P for example? Thanks! $\endgroup$
    – DeeDee
    May 30, 2020 at 20:11
  • $\begingroup$ yes, we are enumerating on their descriptions. to run them, simply use the UTM (universal turing machine). $\endgroup$
    – nir shahar
    May 30, 2020 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.