2
$\begingroup$

I am trying to prove that the language

$$ L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\} $$

belongs to Co-RE but not R.

Showing $\overline{L}\in$ RE is pretty much straightforward, but I also want to show that $L\notin$ R.

My idea was a reduction $\overline{H_{\text{TM}}}\le_mL$ but I struggle to figure out how to do it.

Any help/guidance will be much appreciated.

$\endgroup$
  • $\begingroup$ Can you edit the question to add a reference to the original problem? $\endgroup$ – Apass.Jack Jun 26 at 16:36
  • $\begingroup$ @Apass.Jack the question is from past exams in my university, it asks us to show a reduction to prove this language is in Co-RE but not in R $\endgroup$ – Limitless Jun 28 at 8:09
0
$\begingroup$

Preparation

Since we are talking about the exact number of steps run by a Turing machine (TM), a fixed formal definition of TM is in order. This answer assumes the popular definition of a one-tape Turing machine as in Hopcroft and Ullman (1979, p. 148).

Let $N(w) \downarrow$ denote $N$ on $w$ halts eventually. Let $N(w) \uparrow$ denote $N$ on $w$ never halts.

You have done the initial analysis correctly, pointing out a reasonable solution could be constructing a reduction $\overline{H_{\text{TM}}}\le_mL$. That is, for a TM $N$ and a word $w$, we should construct a Turing machine $M_{N,w}$ such that $$N(w) \uparrow\ \Leftrightarrow\ \langle M_{N,w}\rangle\in L.$$

For simpler notation, we will write $M$ to mean $M_{N,w}$.

Outline of the construction

Basically, we will let $M$ on input $x$ simulate $N$ on $w$ for $|x|$ steps. In case when $N$ on $w$ halts eventually, we will let $M$ run forever when the input is long enough.

Detailed explanation

The basic intuition is that $M$ will have to simulate $N$ on $w$ in some way since the only way to find whether $N$ on $w$ halts eventually is to run $N$ on $w$.

  1. The first problem is the input to $M$ can be any word, which has probably nothing to do with $w$. On the other hand, how long $M$ may run depends on the length of the input.

    Here is a simple approach. We will let $M$ compute how long the input is but ignore the actual content of the input otherwise. Moreover, $w$ will be encoded in the specification of $M$ so that $M$ will be able to put $w$ on the tape, which can be treated as the input to the simulated $N$.

  2. The next problem is how to ensure $\langle M\rangle\in L$ if $N(w) \uparrow$. Assume $N(w)\uparrow$.

    1. For short input, $M$ cannot be running too long for $\langle M\rangle$ to be in $L$.

      The idea to prevent $M$ from running too long is simple. $M$ will halt once it has done reading the input if the input is not long. More specifically, let $M$ have state $s_0$, $s_1$, $\cdots$, $s_{t}$ for some $t$ where $s_0$ is the start state. When $M$ in state $s_i$ reads a cell, it halts if the cell means the end of input. Otherwise it advances to the next cell, updating its state to $s_{i+1}$. So, on every input $x$ of length at most $t$, $M$ will halt in $|x|+1$ steps, which is less than $4|x|^2$ steps.

      Note that we can set $t$ to an arbitrary positive integer.

      Also note that the action above will be performed regardless of whether the input is short or not, since $M$ doesn't know whether the input length is less than or equal to $t$ beforehand.

    2. The next problem is how to prepare $M$ for simulating $N$ on $w$ once it has reached state $s_t$, which will happen if $|x|>t$.

      $M$ should store the length of input while erasing the input. Here are the details.

      1. First it goes back to the start of the input. We will refer this cell as $S$.
      2. Write 0 to the left of $S$.
      3. Switch direction to erase the first symbol of the input.
      4. Switch direction to change 0 to 1.
      5. Switch direction to erase the first symbol of the remaining input.
      6. Switch direction to change 1 to 10, which is 2 in binary representation.
      7. Switch direction to erase the first symbol of the remaining input.
      8. Switch direction to change 10 to 11, which is 3 in binary representation.
      9. And so on until $M$ passes the end of the input, at which time the non-blank symbols to the left of $S$ is the length of the original input in binary representation.
      10. $M$ goes back to $S$. Switch direction to write $w$ on the tape. Switch direction to go to $S$.

      All 10 items above can be done by $M$ in $c(x)<|x|^2+O(|x|)$ steps for input $x$. We can set $t$ to be large enough so that $c(x)+|x|+1<\frac32|x|^2$ for all input $x$ with $|x|\gt t$. The "$|x|+1$" at the left hand side of the inequality comes from the previous item.

    3. How should $M$ simulate $N$ on $w$ as well as maintain the number to the left of $w$ on the tape so that $M$ will not be running too many steps?

      Thanks to the number $|x|$ to the left of $w$ on the tape, we can let $M$ simulate $N$ on $u$ for $|u|$ steps and then halt. Note that at the end of item 2.2.10, $M$ should be in a state that corresponds to the start state of $N$. The head of $M$ is on the top of $S$, which is the first of the cells whose content is $w$. Now we let $M$ loop the following.

      1. Read the current symbol.
      2. If the current symbol is the last binary digit of that number, it means the simulated $N$ is supposed to read a blank symbol. So, let $M$ move all symbols to its right one cell to the right as well as setting $S$ to the blank symbol at last. Now $M$ should be on top of $S$, a blank symbol. Let $M$ read $S$, the (new) current symbol.
      3. Simulate $N$ on the current symbol. Mark the (new) current symbol.
      4. Move to the left of S. Decrease the number by 1.
      5. If the number is 0, break the loop. Otherwise, go back to the marked symbol and start a new round of the loop.

      This stage, stage 3 can be done in at most $\frac52|x|^2$ steps.

    In summary, $M$ will run at most $4|x|^2$ steps regardless whether $|x|\le t$ or $|x|\gt t$, as long as $N(w)\uparrow$.

  3. The last problem is how to ensure $\langle M\rangle\notin L$ if $N(w) \downarrow$.

    $M$ must always be run as specified in item 2 above since $M$ does not know whether $N$ on $w$ will halt eventually or not beforehand. However, what $M$ should do is not specified at the moment when the simulated $N$ on $w$ halts. That will happen when the length of the input to $M$ is larger than the number of steps $N$ will have run before halting. Well, in that case, we will let $M$ just loop forever, which ensures that $\langle M\rangle\notin L$.

Exercises

Exercise 1. Explain that the reduction above can be algorithmic. In particular, the value of $t$ in item 2.2 can be determined algorithmically.

Exercise 2. Explain why $L_{2019}=\{M\mid M$ $\text{is a TM and for all}$ $x\in \Sigma^*$, $M\text{ on }x$ $\text{runs at most}$ $\max(2019,\dfrac{|x|^2}{2019})$ $\text{ steps}\}$ is also undecidable.

Exercise 3. Show that $\{\langle M\rangle\mid M$ $\text{is a TM that halts in }$ $O(n^2+1)\text{ steps where}$ $n$ $\text{ is the length}$ $\text{ of the input}\}$ is undecidable.

$\endgroup$
  • $\begingroup$ Thank you so much! $\endgroup$ – Limitless Jul 6 at 15:01
  • $\begingroup$ Welcome! To clarify exercise 3, the language should have been "$\{\langle M\rangle\mid M$ $\text{is a TM that always halt.}$ $\text{Moreover, M halts in } O(n^2)$ $\text{ steps where}$ $n$ $\text{is the length}$ $\text{of the input}\}$. $\endgroup$ – Apass.Jack Jul 6 at 21:52

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.