# Enumerating the set of polynomial time Turing machines

I was checking this question and wondered how to apply it to the following language to prove it is in $RE$: $$L = \{ \langle M \rangle : \exists P \text{ such that } M \text{ halts on every input } w \text{ within } P(|w|) \text{ steps} \},$$

where $P(x)$ is a polynomial with coefficients $a_1,\ldots,a_n \in \mathbb{N}$.

Those are the two approaches I am thinking of so far, in order to build a Turing Machine $M_L$ which accepts $L$ above:

1. Let $d$ be the degree of the polynomial $P$. For each $d=1,2,3,\ldots$, iterate over all possible $d$ coefficients, and check whether the current $P$ satisfies $L$'s condition above. I think it might work because if there is no such $P$, then the Turing machine $M$ won't stop and this is OK.
2. Here I am taking $P$ to be a constant (i.e. $P(x)=k \in \mathbb{N}$), and then iterate over all $k$ and apply the Turing machine from the question I linked at the beginning, where the language at the question above is in $R$ then there is a Turing machine $M_k$ which decides it, thus, while we get Rejection from $M_k$ for the $k$ values we're iterating on, $M_L$ does not stop.

I am not sure even where I made a mistake above, since the concept of iterating over all $k \in \mathbb{N}$ does not seems robust.

Does the approach of building a Turing machine work? Since I could not get to a reduction which proves that $L \in RE$.

The halting problem reduces to $\overline{L}$: given a machine $T$, create a new machine that on input $n$ simulates $T$ for $n$ steps, and if $T$ halts then it enters an infinite loop. (I leave you the details.)
Since the halting problem is complete for $\mathsf{RE}$, it cannot be the case that $\overline{L} \in \mathsf{coRE}$, and so it cannot be the case that $L \in \mathsf{RE}$.
• I might be wrong, but the way I understand 'complete for $RE$' is that $L \in RE$ then , any $L' \in RE$ yields $L' \leq L$, so i don't see how $\overline{L} \leq L$ and then $L$ cannot be in $RE$ (because $\overline{L} \notin coRE \rightarrow \overline{L} \in RE$)? could you please clarify that point a bit more? Dec 17 '16 at 14:12
• I showed a reduction from the halting problem to $\overline{L}$. This shows that every problem in $\mathsf{RE}$ can be reduced to $\overline{L}$. If $\overline{L}$ were in $\mathsf{coRE}$, then it follows that $\mathsf{RE} \subseteq \mathsf{coRE}$, which we know to be false. Dec 17 '16 at 14:50
• to make sure I understood, basically we have this scenario: $HP \leq \overline{L} \rightarrow HP \notin coRE \text{ implies } \overline{L} \notin coRE \rightarrow L \notin RE$ where I used the reduction rule. correct? Dec 17 '16 at 15:21
• No. The point isn't that the halting problem is not in coRE. It's that the halting problem is RE-complete, and that RE$\neq$coRE. Dec 17 '16 at 16:03