We showed that $E_{TM}$ was undecidable by reducing $A_{TM}$ to it, but it turns out there is no mapping reduction that allows us to do so. If we recall what we did in the proof of that theorem, we constructed a machine $M_w$ and tested whether it was empty. The key point to notice is that our TM for $A_{TM}$ accepted whenever $E_{TM}$ rejected our machine. This means that what we actually showed was $A_{TM} \leq_m \overline{E_{TM}}$. This is fine, since this still implies that $E_{TM}$ is undecidable. Furthermore, it turns out there is no mapping reduction from $A_{TM}$ to $E_{TM}$.
Theorem. $A_{TM}$ is not mapping reducible to $E_{TM}$.
Proof. Suppose that we do have a reduction $f$ such that $A_{TM} \leq_m E_{TM}$. Then this means that by definition we have $\overline{A_{TM}} \leq_m \overline{E_{TM}}$ from the same reduction $f$. However, $\overline{E_{TM}}$ is recognizable but $\overline{A_{TM}}$ is unrecognizable. $$\tag*{$\Box$}$$
Now, we'll use mapping reducibility to show that there are languages that are not recognizable nor co-Turing-recognizable.
Theorem. $EQ_{TM}$ is neither Turing-recognizable nor co-Turing-recognizable.
Proof. First, we show that $EQ_{TM}$ is not Turing-recognizable via a reduction from $A_{TM}$ to $\overline{EQ_{TM}}$. Our reduction $f$ is computed by the following machine.
Here, we have $L(M_1) = \emptyset$ while $L(M_2) = \emptyset$ if $M$ doesn't accept $w$ and $L(M_2) = \Sigma^*$ if $M$ accepts $w$. Then $L(M_1) \neq L(M_2)$ if and only if $M$ accepts $w$ as required.
Now, we show $\overline{EQ_{TM}}$ is not Turing-recognizable by reducing $A_{TM}$ to $EQ_{TM}$. Then the reduction $g$ is computed by the following machine.
Here, we have that $L(M_1) = L(M_2)$ if and only if $M$ accepts $w$ as required. $$\tag*{$\Box$}$$
Theorem. $\leq_m$ is a transitive relation.
Proof. Suppose $A \leq_m B$ and $B \leq_m C$. Then there are computable functions $f$ and $g$ such that $x \in A \iff f(x) \in B$ and $y \in B \iff g(y) \in C$. Consider the function $h(x) = g(f(x))$.
We can build a TM that computes $h$ as follows:
The output of this machine is $h(x) = g(f(x))$ and thus $h$ is a computable function. Then $x \in A \iff h(x) \in C$ and $A \leq_m C$. $$\tag*{$\Box$}$$
Let $M$ be a Turing machine and $w$ and input string. An accepting configuration history for $M$ on $w$ is a sequence of configurations $C_1, \dots, C_\ell$, where $C_1$is the start configuration of $M$ on $w$ and $C_\ell$ is an accepting configuration of $M$ on $w$ and each $C_i$ follows directly from $C_{i-1}$ as defined by $M$. We define a rejecting computation history similarly.
A linear bounded automaton is a Turing machine with the restriction that the tape head is not permitted to move off the portion of the tape containing the input.
In an LBA, we are restricted in how much tape we can use. This means that the number of symbols in the tape alphabet directly affects how much we can store. This amount is linear in the size of the input. This gives us the following interesting property for LBAs.
Lemma. Let $M$ be an LBA with $q$ states and $g$ symbols in the tape alphabet. There are exactly $qng^n$ distinct configurations of $M$ for a tape length of $n$.
Proof. Recall that a configuration consists of the current state, the current position of the tape head, and the contents of the tape. Note that $M$ has $q$ states, the tape head can be in one of $n$ tape cells, and there are $g^n$ possible strings of tape symbols on the tape. This gives us a total of $qng^n$ possible configurations. $$\tag*{$\Box$}$$
However, even with this restriction, LBAs are powerful enough to decide some questions concerning DFAs and CFGs. We will show that the the membership problem for LBAs is decidable, defined by $$ A_{LBA} = \{\langle M,w \rangle \mid \text{$M$ is an LBA and $w \in L(M)$} \}.$$
Theorem. $A_{LBA}$ is decidable.
Proof. Let $n = |w|$. We construct the following Turing machine.
Recall from the above lemma that there are a finite number of configurations that an LBA can be in. We can take advantage of this limitation to detect whether or not the LBA has entered a loop. In a way, we run out the clock by waiting for the LBA to have gone through as many steps as is required to go through every single unique configuration. If it hasn't stopped by then, that means it must have repeated a configuration and must be in a loop. $$\tag*{$\Box$}$$