Reducibility

The primary method of proving problems are computationally unsolvable is called reducibility

See Decidability.md for more context

As the name suggestions, if $A$ reduces to $B$ then $B$ can be used to solve $A$. If $A_{\text{TM}}$ reduces to a problem, that problem is undecidable.

Theorem: $HAL{T}_{\text{TM}}=\{⟨M,W⟩\mid M\text{ is a TM and }M\text{ halts on input }w\}$ is undecidable

This is a famously known as the halting problem. If we had a solution to $HAL{T}_{\text{TM}}$, we could easily make a universal decider, so $HAL{T}_{\text{TM}}$ must be undecidable. We can also prove this directly with diagonalization, but reducibility given $A_{\text{TM}}$ is simpler.

Theorem: $E_{\text{TM}}$ is undecidable

We can construct $M_1$ to simulate $M$ on input $w$ and reject all others. Then running $E_{\text{TM}}$ on $M_1$ tells us whether $M_1$ and therefore $M$ accepts $w$. Hence, $E_{\text{TM}}$ provides a solution to $A_{\text{TM}}$ and is therefore undecidable.

Theorem: $REGULA{R}_{\text{TM}}=\{⟨M⟩\mid M\text{ is a TM and }L(M)\text{ is a regular language}\}$ is undecidable

This is not as immediately intuitive. The idea is we run a decider on $M_2=$ “On input $x$: Accept if $x$ has the form $0^n{1}^n$, otherwise run $M$ on input $w$ and accept if $M$ accepts $w$”. $M_2$ is only regular if $M$ accepts $w$…

Theorem: More generally, determining any property of the languages recognized by Turing machines is undecidable

Theorem: $E{Q}_{\text{TM}}$ is undecidable

We can use other results to make our proofs simpler. $E_{\text{TM}}$ reduces to $E{Q}_{\text{TM}}$ where one of the machines always rejects. Thus, $E{Q}_{\text{TM}}$ is undecidable.

Computation Histories

Definition: An accepting computation history for $M$ on $w$ is a legal sequence of configurations $C_1,C_2,\dots ,C_l$ that results in an accept state, while a rejecting computation history results in a reject state

If $M$ doesn’t halt on $w$, no accepting or rejecting state exists for $M$ on $w$

Nondeterministic machines may have many computation histories, but we don’t focus on this (and they are equivalent computationally)

Definition: A linear bounded automaton is a restricted Turing machine wherein the tape head cannot move off the portion of the tape containing the input

The memory of an LBA is linear in $n$, as a factor of the size of the input alphabet

Despite limited memory, these are actually quite powerful. Conceptually, you should already understand that many problems can be solved in linear memory (using standard algorithmic terms). This includes $A_{\text{DFA}},A_{\text{CFG}},E_{\text{DFA}},E_{\text{CFG}}$.

Theorem: $A_{\text{LBA}}=\{⟨M,w⟩\mid M\text{ is an LBA that accepts string }w\}$ is decidable

Since there are a finite number of configurations, we run $M$ for $qn{g}^n$ steps and reject if it has not halted

Theorem: $E_{\text{LBA}}$ is undecidable

At first glance, this is surprising. We can’t come up with an algorithm that decides this in limited memory?

Observe that we can make an LBA $B$ that verifies an accepting computation history for $M$, allowing us to reduce from $A_{\text{TM}}$

Theorem: $AL{L}_{\text{CFG}}=\{⟨G⟩\mid G\text{ is a CFG and }L(G)={\Sigma }^{\ast }\}$ is undecidable

The key idea is that we can actually design a CFG that generates all strings that are not valid computation histories for a given $w$. This is pretty easy to do with an equivalent PDA, using 3 branches,

1. Check the history doesn’t begin with $C_1$
2. Check the history doesn’t end with an accept configuration
3. Verify that it isn’t the case that each configuration leads to the next

A small technical note is that we alternate the configuration history writing configurations forward and then backward. This is necessary for our stack comparison to check the transition function.

My two takeaways are,

• CFGs can handle certain problems that clearly take unlimited memory
• The TM transition function has finite size

These are both trivial but important to internalize

Normal Problems

Turns out there are undecidable problems that aren’t about contrived computation models! Good to know if you want to convince anyone you’re learning something useful

Definition: The Post Correspondence Problem takes a collection of dominos $P=\left\{[\frac{t_1}{b_1}],[\frac{t_2}{b_2}],\dots ,[\frac{t_k}{b_k}]\right\}$ and a match is a sequence $i_1,i_2,\dots ,i_l$ where $t_{i_1}{t}_{i_2}\dots t_{i_l}=b_{i_1}{b}_{i_2}\dots b_{i_l}$. The problem is finding whether $P$ has a match. Note that our sequence need not be a permutation (we can repeat or omit as much as we want).

$PCP=\{⟨P⟩\mid P\text{ is an instance of the Post Correspondence Problem with a match}\}$

Theorem: $PCP$ is undecidable

The proof idea is designing a set of dominos that can only generate accepting configuration histories of a given $M$

The idea is best demonstrated in MPCP (Modified PCP) where we force the sequence to begin with $\left[\frac{\text{\#}}{\#q_0{w}_1{w}_2\dots w_n}\right]$ (I’m not going to include the proof, but you can look it up or think about it)

Then we modify the set of dominoes to look like $\{[\frac{\ast t_1}{\ast b_1\ast }],[\frac{\ast t_1}{b_1\ast }],\dots ,[\frac{\ast t_k}{b_k\ast }],[\frac{\ast \diamond }{\diamond }]\}$ to enforce the start and end domino

Mapping Reducibility

Reducibility is very important in the theory of computation, so we formalize it

Definition: A function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$ is a computable function if some Turing machine $M$, on every input $w$, halts with just $f(w)$ on its tape

Definition: Language $A$ is mapping reducible to language $B$, written $A{\le }_{m}B$, if there is a computable reduction function $f:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$, where for every $w$, $w\in A⟺f(w)\in B$

If one problem is mapping reducible to a second, previously solved problem, we have a solution to our original problem

Theorem: If $A{\le }_{m}B$ and $B$ is decidable, then $A$ is decidable
Vice versa, if $B$ is undecidable, then $A$ is undecidable

Example:
Show $A_{\text{TM}}{\le }_{m}HAL{T}_{\text{TM}}$
We need a function $f(⟨M,w⟩)=⟨M^{\prime },w^{\prime }⟩$ such that $⟨M,w⟩\in A_{\text{TM}}⟺⟨M^{\prime },w^{\prime }⟩\in HAL{T}_{\text{TM}}$

The following machine computes the reduction $f$,
$F=$ “On input $⟨M,w⟩$”:

1. Construct $M^{\prime }=$ “On input $x$: Run $M$ on $x$, accept if $M$ accepts, otherwise loop”
2. Output $⟨M^{\prime },w⟩$

Our proof for the undecidability of PCP shows that $A_{\text{TM}}{\le }_{m}MPCP$ and that $MPCP{\le }_{m}PCP$

As our intuition implies, reducibility is a transitive property

Importantly, mapping reduction is not exactly equivalent to the informal notion of reducibility that we’ve used earlier. For example, look back at how we proved $E_{\text{TM}}$ is undecidable. This proof showed $A_{\text{TM}}{\le }_m\overline{E_{\text{TM}}}$ (not $E_{\text{TM}}$)

In fact, there is no mapping for $A_{\text{TM}}{\le }_m{E}_{\text{TM}}$! $A_{\text{TM}}{\le }_m{E}_{\text{TM}}⟺\overline{A_{\text{TM}}}{\le }_m\overline{E_{\text{TM}}}⟺\overline{E_{\text{TM}}}$ is not Turing-recognizable (see Theorem right below). However, we can see clearly that $\overline{E_{\text{TM}}}$ is Turing-recognizable.

Theorem: If $A{\le }_{m}B$ and $B$ is Turing-recognizable, then $A$ is Turing-recognizable
Vice versa, if $B$ is not Turing-recognizable, then $A$ is not Turing-recognizable

We typically apply this by showing that $A_{\text{TM}}{\le }_m\overline{B}⟺\overline{A_{\text{TM}}}{\le }_{m}B$

Theorem: $E{Q}_{\text{TM}}$ is neither Turing-recognizable nor co-Turing-recognizable

$E{Q}_{\text{TM}}$ is not Turing-recognizable because $A_{\text{TM}}{\le }_m\overline{E{Q}_{\text{TM}}}$, $f(⟨M,w⟩)=⟨$“On any input reject”, “On any input forward the result of $M$ on $w$”$⟩$

$\overline{E{Q}_{\text{TM}}}$ is not Turing-recognizable because $A_{\text{TM}}{\le }_{m}E{Q}_{\text{TM}}$, $f(⟨M,w⟩)=⟨$“On any input accept”, “On any input forward the result of $M$ on $w$“$⟩$

Turing Reducibility

Our intuition says that $A_{\text{TM}}$ and $\overline{A_{\text{TM}}}$ should be reducible to each other, but this is not the case for mapping reducibility

We introduce another way to think of reducibility

Definition: An oracle for a language $B$ is an external device that is capable of reporting whether any string $w$ is a member of $B$

An oracle Turing machine is a modified Turing machine with the capability of querying an oracle for a language $B$, denoted $M^B$

We say that a language $A$ is decidable relative to $B$ if $T^B$ can decide $A$

Definition: Language $A$ is Turing reducible to language $B$, written $A{\le }_{T}B$, if $A$ is decidable relative to $B$

This is a generalization of mapping reducibility

Interestingly, we can construct undecidable languages for any given oracle machine