3
$\begingroup$

I was going through some Halting Problem reduction and I found the following problem:

Given a semi-decider TM $M$, does the language $L(M)$ contain all strings of exactly length $4$?

The question later asks to prove whether this is recursive or r.e. Going through some practicing, I came to the conclusion that this is must be r.e., since otherwise such problem would solve the Halting Problem.

So, I attempted this question by showing that $$HP < 4LENGTH$$

My approach is to show that $4LENGTH$ is recursive and then showing the contraddiction, that $HP$ is not recursive, so is $4LENGTH$.

However I can't understand how to construct such machine. Moreover, by looking at some similar proof I see that they suggest to build a machine $M'$ that erases the tape, writes $I$ (input) on the tape and simulate $M$. However, I can't follow such proof.

Can someone describe how to solve such problem or give any direction?

$\endgroup$
  • $\begingroup$ So? Everybody makes mistakes. Anyway, I think I figured out the correct parenthesisation (I think). Note that "this is must be r.e., since otherwise such problem would solve the Halting Problem" is not a meaningful statement; every recursive language is also recursively enumerable. $\endgroup$ – Raphael Apr 28 '15 at 9:23
  • $\begingroup$ Thanks for your feedback. So please tell me if I am wrong, but by saying that I thought I meant that we can accept, but never reject. $\endgroup$ – revisingcomplexity Apr 28 '15 at 9:30
  • $\begingroup$ That's too strong; even for a language $L$ in RE - R (the languages that are rec. enumerable but not recursive), there may be a TM that can reject infinitely many strings from $\overline{L}$ -- just not all. $\endgroup$ – Raphael Apr 28 '15 at 9:34
5
$\begingroup$

This might help you understand a standard proof technique for such problems. An instance of HP is a pair, $(\langle M\rangle, x)$ where $\langle M\rangle$ is a description of a TM $M$ and $x$ is a string. To reduce HP to 4LENGTH we require a function $f$ that maps instances of HP to instances of 4LENGTH such that $(\langle M\rangle, x)\in HP\Longleftrightarrow f((\langle M\rangle, x))\in 4LENGTH$. In other words, an instance $I = (\langle M\rangle, x)$ will have a "yes" answer ($M$ halts on $x$) if and only if the transformed instance will have a "yes" answer ($f(I)$ accepts all strings of length 4).

Given $(\langle M\rangle, x)$, we'll define a TM $M'$, using $M$ and $x$, that acts as follows:

M'(y) =
   if |y| = 4
      erase y
      write x on the tape
      simulate M
      return accept

Now if $(\langle M\rangle, x)\in HP$, then $M$ will halt on $x$ and so $M'$ will accept any string of length 4, so $M'\in 4LENGTH$.

On the other hand, if $(\langle M\rangle, x)\notin HP$, then $M$ will never halt on $x$ and so $M'$ will never get to the return accept statement and so will accept nothing. Hence if $(\langle M\rangle, x)\notin HP$, then $M'\notin4LENGTH$.

To summarize, we have established a faithful mapping from instances of HP to instances of 4LENGTH.


Now to show that 4LENGTH is not recursive, we argue by contradiction. Suppose that 4LENGTH were recursive. Then there would be a decider, $D_4$, for 4LENGTH namely, given any TM description $\langle N \rangle$, $D_4$ would take that description as input and halt and either return "yes" if $\langle N \rangle\in 4LENGTH$ and "no" if $\langle N \rangle\notin 4LENGTH$.

We can then use $f$ and $D_4$ to build a decider for HP. It would work like this:

  1. Given an instance $I=(\langle M\rangle, x)$ of HP, use $f$ to produce an instance $f(I)=\langle N\rangle$ of 4LENGTH.
  2. Run the decider $D_4$ on $f(I)$.
  3. If $D_4$ answers "yes" to $f(I)$, then by the construction of $f$, $I$ must have been in HP. Similarly, if $D_4$ answers "no", $I$ must not have been in HP. In short, we've built a decider for HP, contradicting the fact that HP is not recursive.
$\endgroup$
  • $\begingroup$ I can't understand why we erase y, can you tell more about that? $\endgroup$ – revisingcomplexity Apr 27 '15 at 21:39
  • $\begingroup$ @revisingcomplexity. Just so that you can clear the deck for the simulation of $M$ on $x$. It's not that important of a point. $\endgroup$ – Rick Decker Apr 28 '15 at 0:36
  • $\begingroup$ Why do we use the HP as decider for 4Length? Should it not be the other way around since HP < 4LENGTH ? (I might have understood it wrongly!) $\endgroup$ – revisingcomplexity Apr 28 '15 at 9:28
  • $\begingroup$ @revisingcomplexity. We're using a decider for 4LENGTH to construct a decider for HP. See if my revised description is any clearer. This construction is, as I said, common, but you're in the same boat as many of my students: the first time you see it, it can be hard to grasp. Keep at it--eventually it will make sense. $\endgroup$ – Rick Decker Apr 28 '15 at 14:06

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.