[Solved]: Is deciding whether the language of a TM contains all strings of length 4 computable?

Problem Detail: 

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?

Asked By : revisingcomplexity

Answered By : Rick Decker

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41885

3.2K people like this

 Download Related Notes/Documents