# Diagonalization and classes of computable functions

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?

-

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.
Hadn't thought of that but that makes sense too... because the "right" $\phi_{e_0}$ is visited polynomially (quadratically) often even if you don't know which $e=e_0$... – Bjørn Kjos-Hanssen May 5 '12 at 7:51