Reductions in computability theory

Question

Given $\ L= \{<M> \mid \forall w \in \Sigma^*, \text{ while } M \text{ runs on } w, \text{ it makes at least } |w|^5 \text{ steps right and then accepts.}\}$

Intuitively this language is similar to $\ L= \{ <M> \mid L(M)=\Sigma^*\}$ and therefore $L\notin RE$ and $L\notin coRE$, but how should I define the reduction formally to prove it?

Answer 1

Let $\overline{HP} = \{\langle A,x \rangle :$ A is a TM that does not halt on x $\}$

Loop = "On input (A, x)
$\qquad\qquad$1) M = "On input w
$\qquad\qquad\qquad\qquad$10) simulate A on x for |w| steps
$\qquad\qquad\qquad\qquad$20) if A halts on x in |w| steps
$\qquad\qquad\qquad\qquad$30)$\quad$ reject
$\qquad\qquad\qquad\qquad$40) else
$\qquad\qquad\qquad\qquad$50)$\quad$ move right for $|w|^5$ steps
$\qquad\qquad\qquad\qquad$60)$\quad$ accept

$\qquad\qquad$2) if R(M) accepts
$\qquad\qquad$3)$\quad$ accept
$\qquad\qquad$4) else
$\qquad\qquad$5)$\quad$ reject

A loops on x ⇐⇒ M accepts all strings after making at least $|w|^5$ steps right
If R recognizes L then Loop recognizes $\overline{HP}$
Since $\overline{HP}$ is not RE, L is not RE.

The complement of L is $\overline{L} = \{\langle M \rangle :$ there exists w that M accepts after less than |w|^5 steps $\}$

The reduction is similar to L but you remove line 50.

Answer 2

Define $ALL_{TM} = \{<M> : L(M) = \sum \ ^ * \}$ .

As you noted, $ALL_{TM} \in \overline{Re \cup CoRE}$, so it is enough to show that $ ALL_{TM} \le_p L$.

The reduction acts as follows:

Given $<M>$ the reduction outputs $<M'>$ . $M'$ , on input $x$ , simulates the run of $M$ on $x$ , if $M$ accepts $x$ , then $M'$ moves $|x| \ ^ 5$ cells to the right and accepts.

Show that $<M> \in ALL_{TM}$ iff $f(<M>) = <M'> \in L$ , and this completes the proof.