3
$\begingroup$

Given some complexity class $\mathsf{C}$, I want to know if there exists a function (Turing machine) $F:\mathbb{N} \to \mathsf{C}$ such that, if $S$ is any set for which the problem $x \mapsto x \in S$ is in $\mathsf{C}$, then $F(n)$ is a Turing machine which (partially, if $\mathsf C = \mathsf{RE}$) decides $x \in S$ for some $n$.

Note that if $g$ and $h$ are two Turing machines that decide $x \in S$, then $F$ only needs to enumerate one of them (hopefully this makes the problem easier). Thus the title is a bit wrong, but kept as it is for lack of a better one.

Trivially, if $\mathsf{C}$ equals something in the Chomsky hierarchy, such machine $F$ exists (enumerating all grammars of the required type). I'm interested in the less obvious classes.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I have doubts about validity of my notation (I'm implicitly converting functions to Turing machines to integers, it seems) and clarity of my statements (first paragraph is all one sentence). I'd appreciate suggestions on how to improve either of these. $\endgroup$ – Karolis Juodelė Jan 4 '13 at 18:11
  • 1
    $\begingroup$ It feels like you should be slightly doubtful about that validity - in particular, your $S$ and $F$ feel a bit underspecified. If $F:\mathbb{N}\to C$, then $F(n)$ is a set $S$, not a turing machine; it sounds like what you want is a function $F:\mathbb{N}\times C\to \mathbb{N}$, where $F(n,S)$ is the code for a machine deciding $n\in S$, but such a function runs into issues with its domain, particularly the specification of $S$/$C$... $\endgroup$ – Steven Stadnicki Jan 4 '13 at 18:35
  • $\begingroup$ @StevenStadnicki, I assumed a complexity class to be a set of Turing machines. If it is in fact a set of sets, I don't see why it would be a problem. In that case $F_C$ is a function such that if $S \in C$ then $F_C(n)$ decides $S$ for some $n$. $\endgroup$ – Karolis Juodelė Jan 4 '13 at 18:42
  • $\begingroup$ Ahhh, I think I see what you mean more clearly now; that makes quite a bit of sense. I thought it was trying to decide a question of membership, not enumerating. Will chew on this a bit... $\endgroup$ – Steven Stadnicki Jan 4 '13 at 19:08
5
$\begingroup$

Time-bounded classes can be enumerated. Suppose we want to enumerate all languages in P. Every language in P is accepted by some Turing machine $T$ running in time $f(n)$ for some polynomial $f$. We can construct a Turing machine $T'$ that emulates $T$ but also keeps track of the time, and stops after $f(n)$ steps. Every Turing machine of the form $T'$ accepts a language in P, and vice versa, for every language in P, we can construct such a machine $T'$. The machines $T'$ themselves can be enumerated by enumerating the simulated machines $T$ and the "timers" $f(n)$.

For a space-bounded class, you do something similar, keeping track of the space usage of the Turing machine. You also need to prevent infinite loops somehow, either using a timer or by keeping track of all positions encountered so far during the simulation.

Non-deterministic and randomized versions can also be handled this way, so for example, PH can be enumerated.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Well, that turned out to be oddly trivial. In that case, could you also throw in a word about the case when $F$ has to enumerate all machines that decide any set? $\endgroup$ – Karolis Juodelė Jan 4 '13 at 19:10
  • $\begingroup$ The set of all Turing machines that stop on all inputs is not recursively enumerable, so that's impossible. $\endgroup$ – Yuval Filmus Jan 4 '13 at 19:57
  • $\begingroup$ Could you explain what it means formally to enumerate all languages in P? $\endgroup$ – usul Jan 4 '13 at 20:59
  • $\begingroup$ @YuvalFilmus, I felt that would be the problem, but I don't think this argument works. I only want a small subset of all Turing machines that stop on all inputs. $\endgroup$ – Karolis Juodelė Jan 4 '13 at 21:01
  • $\begingroup$ @Karolis You can probably show that the set of all Turing machines that stop on all inputs and output either $0$ or $1$ is also $\Pi_2$-complete. $\endgroup$ – Yuval Filmus Jan 4 '13 at 21:18
2
$\begingroup$

The codomain of $F$ should be Turing machines (or machines in some other particular model of computation) not the complexity class itself. You can't identify the machines that decide sets in a complexity class with the sets in the complexity class because it is not a one-one correspondence. Moreover a complexity class has various representations, you have to fix the representations of the sets in the complexity class (by fixing a model of computation) before discussing how to enumerate them.

Let $\tilde{C}$ be a representation of sets in the complexity class $C$, i.e. the sets decided by machines in $\tilde{C}$ belong to $C$ ($\tilde{C}$ doesn't need to be an r.e. set, e.g. $C = \mathsf{BPP}$ which we don't know any r.e. representation for, but it should be enumerable so we can consider it as a subset of $\mathbb{N}$). You want a function $F:\mathbb{N}\to \mathbb{N}$ s.t.

  • for all $n\in\mathbb{N}$, $F(n) \in \tilde{C}$,
  • for all $A \in C$, there is $n\in\mathbb{N}$ s.t. $L(F(n)) = A$,
  • $F$ is computable.

So we have at least one representative for each set in $C$ and we can computably enumerate these representatives.

This is related to the question of being a syntactic complexity class. Most famous complexity classes turn out to be syntactic as is implied by Yuval's answer (it is open for other famous complexity classes like $\mathsf{BPP}$). If we have an efficient universal simulator for the complexity class then the class is syntactic. It is important to remember that we want machines that decide sets in the complexity class to decide them with reasonable resources.

ps: this is also known in literature as recursive representability, also sometimes referred to as recursive indexing of the complexity class (look also for computable in place of recursive).

|cite|improve this answer
$\endgroup$

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.