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:
if |y| = 4
write x on the tape
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:
- Given an instance $I=(\langle M\rangle, x)$ of HP, use $f$ to produce an instance $f(I)=\langle N\rangle$ of 4LENGTH.
- Run the decider $D_4$ on $f(I)$.
- 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.