Proof language classification using reduction mapping

Question

I am required to determine whether the following language is in $R$/$RE$-$R$/$coRE$-$RE$ or neither.

$$L = \{\langle M \rangle |\ M\ \text{is a}\ TM\ \text{and}\ \exists x\ \text{s.t.}\ |x|<5\ \text{and}\ M\ \text{rejects}\ x\}$$

This is my thought of doing: Building a reduction mapping $F$: $A_{TM}\rightarrow L$

$F$ = "On input $\langle M,w \rangle$:

• Generate $M'$ = 'On input $x$:
  • Simulate $M$ on $w$:
    • If it accepts $\Rightarrow$ if $|x| < 5$ reject. Else $\Rightarrow$ accept.
    • Otherwise $\Rightarrow$ accept.'
  • Return $\langle M’\rangle$"

Correctness: $$\langle M,w\rangle \in A_{TM} \iff M\ \text{accepts}\ w \iff \text{all}\ |x| < 5\ \text{rejected} \iff \langle M’\rangle \in L$$ $$\langle M,w\rangle \notin A_{TM} \iff M\ \text{doesn’t accept}\ w \iff \text{No}\ x\ \text{is rejected} \iff \langle M’\rangle \notin L$$

I'm not quite sure if I've used the mapping reduction correctly.

Answer 1

The proof of correctness contains a couple of errors. The condition that all $x: |x| < 5$ are rejected does not imply that $M$ accepts $w$. The reason is that $M$ may reject $w$ by hanging. For the same reason the fact that $M$ does not accept $w$ does not imply that $M'$ accepts every string.

Here is a working reduction from $A_{TM}$ to $L$.

$F$ = "On input $\langle M,w\rangle$:

1. Construct the following machine $M'$.

   $M'$ = "On input $x$:

   1. If $|x| \ge 5$, accept.
   2. Otherwise, run $M$ on $w$. If it accepts, accept; if it rejects, reject."
2. Output $\langle M'\rangle$"

It is not difficult to see that $\langle M,w\rangle \in A_{TM}$ if and only if $\langle M'\rangle \in L$.