3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – ThunderWiring Dec 17 '16 at 14:12
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 17 '16 at 14:50
  • $\begingroup$ 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? $\endgroup$ – ThunderWiring Dec 17 '16 at 15:21
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 17 '16 at 16:03
  • $\begingroup$ i don't understand what part of my last correct is incorrect? Also it is not clear to me how the fact that HP is RE-complete is related to deduce something about L? $\endgroup$ – ThunderWiring Dec 18 '16 at 12:10

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.