A class of languages $C$ is recursively presentable if there is an effective enumeration of Turing machines $\mathcal{M}_1,\mathcal{M}_2,\ldots$ such that $C=\{L(\mathcal{M}_i)\mid i=1,2,\ldots\}$. Uwe Schöning considers this notion in his elegant generalisation of Ladner's theorem ("A Uniform Approach to Obtain Diagonal Sets in Complexity Classes", Theor. Comp. Sci. 18, 1982).
In a previous answer on this site, Ryan Williams argues that the set of all P-hard languages can be recursively presented "similar to how Schoening does it for the NP-hard sets". I would like to know how this works, since I cannot find this in the paper. Schöning works with Turing reductions and shows that the NP-complete sets are recursively presentable. We can adapt his argument to NP-complete sets under polynomial many-one reductions as follows:
- Take an enumeration $(\mathcal{M}_i,\mathcal{R}_i)_{i\geq 1}$ of pairs of polynomially time-bounded non-deterministic Turing machines $\mathcal{M}_i$ and polynomial reductions $\mathcal{R}_i$ (we can enumerate polytime machines and reductions by enumerating all machines and polynomials, and augmenting them with a polytime "stop clock" that enforces timely halting).
- For each pair of a machine $\mathcal{M}_i$ and reduction $\mathcal{R}_i$, the let $\mathcal{M}'_i$ denote a machine that does the following on input word $w$:
- For all input words $v$ with $|v|<|w|$, test whether $\mathrm{SAT}(v)=\mathcal{M}_i(\mathcal{R}_i(v))$, i.e., whether $\mathcal{R}_i$ reduces $\mathrm{SAT}$ to $L(\mathcal{M}_i)$ on these instances.
- If yes, accept iff $\mathcal{M}_i$ accepts $w$
- If no, accept iff $w\in\mathrm{SAT}$
The required enumeration is $\mathcal{M}'_1,\mathcal{M}'_2,\ldots$, since each of those either decides $\mathrm{SAT}$ (up to finitely many cases) or some other language in NP to which $\mathrm{SAT}$ can truly be reduced.
I do not see how to apply this idea to recursively present all P-hard languages. One could readily recursively present, e.g., all P-hard languages in ExpTime (which would suffice as an answer in the other thread), but I don't see why the P-hard languages in general (including undecidable ones) should even be countable.