Lecture: Recognizability and Computable Reductions

We return again with more on Turing recognizability and introducing the tools we need for showing that languages are decidable, recognizable, or neither.

First off, we showed that there are some languages that aren’t decidable last time. We’ve argued before, informally, that there must be languages that can’t be described by Turing machines at all and thus aren’t even recognizable. Here we’ll give a nice concrete example that also will demonstrate that Turing machines aren’t closed under complement.

Recall the language $A_{TM} = \{(M,w) | M \text{ accepts the string } w\}$, now consider it’s complement $\overline{A_{TM}} = \{(M,w) | M \text{ rejects or loops on the string } w\}$. Intuitively, would we expect this to not be recognizable. Why? Because recognizing $A_{TM}$ amounts to just simulating the action of $M$ on $w$. That’s easy enough, because you can just sit and wait for an answer. If you get an accept eventually, then you can accept, but if the simulation loops well it’s okay to loop yourself because you can either fail or loop on a rejection. If you’re trying to simulate the complement, however, you hit an awkward problem: how do you sit around and wait forever on the loop and somehow still return an accept? You might object and say that there must be a more clever way to do this simulation and you’d be right, we didn’t write a proof we just made an appeal to intuition which is why we’ll do a formal proof that $\overline{A_{TM}}$ is unrecognizable after we introduce one more fact.

The lemma in question is the fact that if both a language and it’s complement are recognizable, then the language is actually decideable. Look at it this way, we have a language $L$ that is recognizable then that means there will be a machine that returns “accept” in finite time whenever a string $w$ is in $L$. The complement being recognizable means that there will be some machine that returns “accept” in finite time whenever a string $w$ is in $\overline{L}$. Now, we can make a new machine that combines these two recognizers in a multitape dual simulation, where it alternates taking a step in one machine with taking a step in the other. This way, no matter whether a string is or isn’t in the language, then we’ll get an “accept” back from one of the two machines in finite time. As long as we reject when the complement machine accepts, then we have a decider for the language.

This means, however, that if a language isn’t decidable but is recognizable, then it’s complement cannot be recognizable. Clearly, $A_{TM}$ is such a language and thus $\overline{A_{TM}}$ is not recognizable.

Great, now that we have concrete proven examples of both undecidable and unrecognizable languages now we can introduce the notion of a computable function whose definition we’re pretty much just going to steal wholesale from Sipser: a function $f : \Sigma^* \to \Sigma^*$ is computable if there exists some Turing machine $M$ such that on every input $w$, $M$ halts with just $f(w)$ on the tape. Now, now Turing machines are starting to resemble computation as we normally think of it, aren’t they? We’re introducing this construction, though, to define the notion of a mapping reduction from one language to another.

Given languages $A$ and $B$, $A$ is reducible to $B$, written as $A \le_m B$, if there is a computable function $f$ such that if a string $w \in A$ then $f(w) \in B$ and if $w \notin A$ then $f(w) \notin B$, in other words $f(w) \in B$ iff $w \in A$. What does this mean intuitively, though? It means that we can take the question “is $w$ in $A$ ” and turn it into the question “is $f(w)$ in $B$ “, because by the condition that $f(w) \in B$ iff $w \in A$ these questions are equivalent to each other. If you answer one, you’ve answered the other. Which means, in turn, that if we already know how to answer “is $s$ in $B$ ” then we automatically have a way to answer “is $w$ in $A$ ” without having to even build a machine for it, we only need the reduction.

We’ve seen this already, actually, because this is in essence what we did with the difference between $A_{DFA}$, $A_{NFA}$, and $A_{RegExp}$. Remember how, as we defined each of these machines in turn we just turned an NFA into a DFA or a RegExp into an NFA and then used the machine we defined previously. This is also how we defined $EQ_{DFA}$, by reducing the problem to $E_{DFA}$.

There’s a couple of really nice properties about reductions. First, that if $A \le_m B$ and $B$ is decidable then we know that $A$ is decidable. We know this because our decider for $A$ is just to compute the reduction to $B$ and then run the decider for $B$. This also means, however, that if $A \le_m B$ and $A$ is undecidable then $B$ must be undecidable as well or else we’d get a contradiction.

Similarly for recognizable languages, if $A \le_m B$ and $B$ is recognizable then so is $A$ and if $A$ is unrecognizable then so to must $B$.

I think I’ll leave things here for now and next post will be lots and lots of examples of reductions because it’s a cool technique that’s worth savoring.