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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\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}$.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Dec 17, 2016 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
    Commented Dec 17, 2016 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
    Commented Dec 17, 2016 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
    Commented Dec 17, 2016 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
    Commented Dec 18, 2016 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.