Fix a standard effective listing $(\phi\_e)\_{e\in\omega}$ of the partial computable functions from $\omega$ to $\omega$. Let $\mathcal{C}$ be a class of computable total functions $\omega\rightarrow \omega$. Say that a set $X\subseteq\omega$ is a *representative* for $\mathcal{C}$ if $e\in X\implies \phi\_e\in\mathcal{C}$ and for all $f\in \mathcal{C}, \exists e\in X$ such that $\phi\_e=f$.


There is a very simple proof that there is no computable representative for $Tot=\lbrace \phi\_e: \phi\_e$ is total$\rbrace$. For suppose $X=\lbrace x\_0 < x\_1< . . . \rbrace$ were a computable representative. Then let $f\_X(i)=\phi\_{x\_i}(i)+1$. Since $X$ is computable, so is $f\_X$; since $X$ is a representative of $Tot$, $f\_X$ is total; but clearly $f\_X\not=\phi\_{x\_i}$ for any $i$, so we have a contradiction. 


However, this argument need not hold in general. Suppose $\mathcal{C}$ were a class of functions which converged sufficiently slowly. Then perhaps $f$ so defined would not converge quickly enough to be an element of $\mathcal{C}$, in which case no contradiction could be derived. For instance, suppose $\mathcal{C}$ consists of the total polynomial-time computable functions. Then if $X$ is a computable representative, the function $f\_X$ is not equal to any function in $\mathcal{C}$, but it appears that $f\_X$ would need more than polynomial time to be computed, so no immediate contradiction is reached. On the other hand, it still seems extremely unlikely that the set of total polynomial-time-computable functions should have a computable representative.


My questions are the following: Is there a known complexity class with a computable representative? Does the set of polynomial-time-computable total functions have a computable representative?



Diagonalization and classes of computable functions
The set of polytime computable functions does indeed have a computable representative. Note that for $f$ to be polytime computable means there exists $t$, and $n\_0$ such that for all $n\ge n\_0$ it takes only at most $n^t$ time steps to compute $f(n)$. Now dovetail over all indices $e\in\omega$ and all $t$ and $n\_0$; if $\phi\_e(n)$ has not halted by time $n^t$ just set the output to say $0$, to make a total function.


