Now we'll formalize the notion of reducibility and reduction. First, we'll need to revisit the notion of Turing machines and functions.
While our basic definition of a Turing machine is a language recognition device, we can modify it so that it becomes a computing device, which seems very relevant and practical. Instead of having accept and reject states, we define our machine to have a single halting state. Then we have the following notion.
A function $f: \Sigma^* \to \Sigma^*$ is a computable function if some Turing machine $M$, on every input $w$, halts with only $f(w)$ left on its tape.
As usual, there are multiple equivalent definitions for the specifics here. For instance, the choice of input alphabet is up to us, so if we want to compute, say, integer functions, then we can take our input and output to be unary or binary or something else. This means that a machine computing the function $f(n) = 2n$ can be implemented as a machine that takes $1^n$ as input and computes $1^{2n}$ in unary, or it could be something that does it in binary, like $(n)_2 \mapsto (n)_2 0 = (2n)_2$.
This notion is useful for a few things. First, it gives a very obvious way for us to connect Turing machines with the concept of recursive functions. Secondly, it gives us a way to think about data transformation. Thirdly, we'll be using it in the formal definition of reducibility, and it shows up again for various definitions in complexity theory.
But is this machine equivalent to our basic model? Sure, it's not hard to see that we can designate something like an output tape for our output to appear on and then we just hit the accept state once we're done computing our function. Similarly, we can always "simulate" the notion of accept and reject states; after all, languages are just decision problems, which are just functions from $\Sigma^*$ to $\{0,1\}$, so we output a 1 for accept and output a 0 for reject.
For our current purposes, we are more interested in transforming various kinds of input strings into other input strings. For instance, we can take as input some description of a Turing machine $\langle M \rangle$ and transform it into some other machine $\langle M' \rangle$. This is something that we've been implicitly doing when we assume that various machines can be constructed.
A language $A$ is reducible to a language $B$, denoted $A \leq B$, if there is a computable function $f:\Sigma^* \to \Sigma^*$, where for every $w$, $$ w \in A \iff f(w) \in B.$$ The function $f$ is called the reduction from $A$ to $B$. The reduction is a formal way of specifying a transformation of an input string for a particular problem to an input string for some other problem.
Then we get the following.
Let $A$ and $B$ be languages.
We'll only give the proof for (1). Let $M$ be a TM that decides $B$ and let $f$ be a reduction from $A$ to $B$. Then we can construct a TM that decides $A$ as follows:
From this we can see that $w \in A$ obviously implies $f(w) \in B$.
It's important to note that this is not a bijection. To see this, look at any of the undecidability proofs we've done so far.
Let's consider the proof that $HALT_{TM}$ is undecidable. To show an explicit reduction, we need to show that there exists a computable function $f$ that transforms strings $\langle M,w \rangle$ into strings $\langle M',w' \rangle$ where $$ \langle M,w \rangle \in A_{TM} \iff \langle M',w' \rangle \in HALT_{TM}.$$ To do this, we simply show that there is a TM that computes an appropriate function $f$:
Something that you may notice in the above theorem is that this gives us a way to show that a language is unrecognizable. We already showed, via diagonalization, that there have to be unrecognizable languages out there. By showing that we have an undecidable language and using reductions, we can show that specific languages are unrecognizable.
We say that a language is co-recognizable if it is the complement of a recognizable language.
A language is decidable if and only if it is recognizable and co-recognizable.
If $A$ is decidable, then $A$ and $\overline A$ are recognizable, since a decidable language and its complement are recognizable.
If $A$ and $\overline A$ are recognizable, then there exist Turing machines $M_1$ and $M_2$ that recognize $A$ and $\overline A$, respectively. Then we can construct a Turing machine $M_3$ that on input $w$ operates as follows:
Since $A \cup \overline A = \Sigma^*$, we have that either of $M_1$ or $M_2$ must accept, which means that $M_3$ is guaranteed to halt. This means that $A$ is decidable.
Note that the TM $M_3$ that we constructed is a deterministic machine. If we used a nondeterministic machine, the construction would be even easier: just run the two machines in parallel until one accepts.
This result gives us a clear example of an unrecognizable language.
$\overline{A_{TM}}$ is not recognizable.
If $\overline{A_{TM}}$ were recognizable, then $A_{TM}$ would be decidable.
This might seem obvious, but these results lead to something that may not be entirely obvious until we work through the details. We showed before that $E_{TM}$ was undecidable by "reducing" $A_{TM}$ to it, but this is technically incorrect. 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 \overline{E_{TM}}$. This is fine, since this still implies that $E_{TM}$ is undecidable. But what happens if we try to find a reduction from $A_{TM}$ to $E_{TM}$? The answer is: we can't.
$A_{TM}$ is not reducible to $E_{TM}$.
Suppose that we do have a reduction $f$ such that $A_{TM} \leq E_{TM}$. Then this means that by definition we have $\overline{A_{TM}} \leq \overline{E_{TM}}$ from the same reduction $f$. However, $\overline{E_{TM}}$ is recognizable but $\overline{A_{TM}}$ is unrecognizable.
Now, note that this says nothing about whether or not $E_{TM}$ or $\overline{E_{TM}}$ are recognizable or unrecognizable. It could be that one of them are recognizable (which means the other isn't) or both could be unrecognizable. The answer turns out to be the first.
$\overline{E_TM}$ is recognizable.
Recall that $\overline{E_{TM}}$ is the language of Turing machines that accept at least one word. Therefore, all we need to do is enumerate every word and check if $M$ accepts it. There is a slight problem with this: what if we encounter a word that makes $M$ run forever? Then we can never move on to the next word. So we need to be a bit more clever.
We define a Turing machine that does the following:
If no word is accepted by $M$, this machine will run forever. If there is a word $w \in L(M)$, then $w$ must be of finite length $n$ and is accepted within a finite number of steps $t$. This means that the machine will detect that $w$ is accepted when $i = t$.
An alternative proof uses nondeterministic Turing machines: the NTM nondeterministically guesses a string $w$ and simulates $M$ on it. If $w$ is accepted, then this means at least one branch of computation on the NTM is an accepting branch and the word is accepted. Otherwise, none of the branches are accepting branches.
This clearly gives us the following.
$E_{TM}$ is unrecognizable.