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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered May 30, 2020 at 20:04
-
$\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$– DeeDeeMay 30, 2020 at 20:11
-
$\begingroup$ yes, we are enumerating on their descriptions. to run them, simply use the UTM (universal turing machine). $\endgroup$ May 30, 2020 at 20:20