2
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

Kozen answers this in your quote: what you enumerate is Turing machines that accept all languages in P. This makes sense in many contexts, for example if you want to diagonalize against all languages in P.

It is not a priori clear how to enumerate P (as Turing machines). The problem is that given a Turing machine, it is (provably) impossible to tell whether it halts in polynomial time. The trick is to force the machine to halt in polynomial time.

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm not sure what you mean by "code". As for how Turing machines are expressed, be imaginative. Whatever you come up with is probably good enough. Essentially, you want a description which could be fed to a universal Turing machine. $\endgroup$ – Yuval Filmus Jun 1 at 20:17
  • 1
    $\begingroup$ This sounds like a completely different question. $\endgroup$ – Yuval Filmus Jun 1 at 20:20
  • 1
    $\begingroup$ In brief, you enumerate "timed Turing machines", which are Turing machines that stop after polynomially many steps. The enumerator goes over all pairs of Turing machines and polynomials, and converts each such pair to a timed Turing machine. $\endgroup$ – Yuval Filmus Jun 1 at 20:21
  • 1
    $\begingroup$ Updated my answer. $\endgroup$ – Yuval Filmus Jun 1 at 20:25
  • 1
    $\begingroup$ This statement is explained in the rest of the paragraph. If it bothers you, just ignore the paragraph. $\endgroup$ – Yuval Filmus Jun 1 at 20:30

Your Answer

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