Tuesday, November 12, 2013

The structural theory of computability

The structural theory of computability continued, and how all the different levels of undecidability fit together (it's not just an infinite ladder, it's infinitely many infinite ladders).

Hand-written notes available on the instructor's website

1Reductions continued¶

1.1Mapping reductions¶

aka many-to-one reductions, but "mapping" is a better name

$A \leq_m B$ means that there exists a function $f: \Sigma^* \to \Sigma^*$ (a string transformation) such that $f$ is total computable (so there is an algorithm, guaranteed to terminate, that can compute $f$) and $w \in A$ $\Leftrightarrow$ $f(w) \in B$.

Note that this is a directional concept - the function goes from $A$ to $B$, not $B$ to $A$.

If $A \leq_m B$, then $\overline{A} \leq_m \overline{B}$ also holds.

This concept will be useful when exploring the hierarchy of undecidability and for making finer distinctions than just decidable vs. undecidable.

1.1.1Some theorems¶

If $A \leq_m B$ and $A$ is not RE, then $B$ cannot be RE.

If $A \leq_m B$ and $A$ is undecidable, then so is $B$.

Proofs omitted since they are obvious.

1.1.2Relation to previous reductions¶

Recall the language $A_{TM} = \{\langle M, w \rangle \mid w \in L(m) \}$. We know that this is RE but not decidable. Also, $E_{TM} = \{\langle M \rangle \mid L(M) = \varnothing \}$. Recall our reduction for $A_{TM} \leq E_{TM}$. We started with $\langle M, w \rangle$ and we constructed a machine $M'$ such that $M$ accepts $w$ $\Leftrightarrow$ $L(M') \neq \varnothing$. This is clearly total and computable. However, it's not a mapping reduction from $A_{TM}$ to $E_{TM}$ - rather, it's a mapping reduction for $A_{TM} \leq_m \overline{E_{TM}}$.

In fact, there is no mapping reduction from $A_{TM}$ to $E_{TM}$. The proof runs as follows: Suppose there is a function $f$ such that $x \in A_{TM} \Leftrightarrow f(x) \in E_{TM}$. In other words, $x \notin A_{TM} \Leftrightarrow f(x) \notin E_{TM}$, $\therefore$ $x \in \overline{A_{TM}} \Leftrightarrow f(x) \in \overline{E_{TM}}$.

Now, $\overline{E_{TM}}$ is RE - given some machine $M$, we can just try it on every possible word by dovetailing, and if there is a word that $M$ accepts, we will find it eventually. However, we know that $\overline{A_{TM}}$ is not RE. By the first theorem above, it must be that no such $f$ exists. $\blacksquare$

(Remember that if a language and its complement are both RE, then the language is decidable. But $A_{TM}$ is RE and not decidable. So $\overline{A_{TM}}$ can't be RE.)

1.1.3Reductions for $EQ_{TM}$¶

Consider $EQ_{TM} = \{\langle M_1, M_2 \rangle \mid L(M_1) = L(M_2)\}$. This language happens to be neither RE nor co-RE. To prove this, we'd have to show that $A_{TM} \leq_m EQ_{TM}$ and that $\overline{A_{TM}} \leq_m EQ_{TM}$.

Proof: Let $R$ be a decider for $EQ_{TM}$. Let $M_1$ be a TM accepting NOTHING, ABSOLUTELY NOTHING AT ALL. Given a TM $M$, let $S$ be a TM that simulates $R$ on input $<M_1, M>$, and accepts if and only if $R$ accepts. But then $S$ decides $E_{TM}$, which is a gigantic contradiction to everything we've been raised to believe.

1.2Rice's theorem¶

1.2.1Functional equivalence¶

Let $P$ be a program in some Turing-complete language. Every program has an associated RE set $⟦P⟧ = \{(x, y) \mid P(x) = y \}$, which is just the table of input/output correspondences.

We say that two programs are functionally equivalent by some equivalence relation $\sim$ if they have the same spec, i.e., the same input/output table. So $P_1 \sim P_2 \Leftrightarrow ⟦P_1⟧ = ⟦P_2⟧$.

1.2.2Extensional properties¶

An extensional property of programs is a map

$$Q: \text{Program} \to \{\text{T}, \text{F}\} \tag{T = true, F = false}$$

such that if $P_1 \sim P_2$, then $Q(P_1) = Q(P_2)$.

Thus, if any two languages are functionally equivalent, any extensional property that holds for one must also hold for the other. We can think of these properties as properties of RE sets.

Some extensional properties are trivial - for example, the property "F". No program can change "F" into "T". Clearly this property is unsatisfiable, and so the set of programs satisfying this property is empty. On the other hand, the property "T" is satisfied by all programs.

1.2.3Statement of the theorem¶

Every non-trivial extensional property is undecidable¹.

Proof: let $Q$ be a nontrivial extensional property of RE sets. We will show that $Q$ is undecidable via a mapping reduction to $A_{TM}$. Assume that if $L(M) = \varnothing$, then $Q(M)$ is not true³. Since $Q$ is non-trivial, there must be at least one program that satisfies it, which we'll call $M_0$. So $Q(M_0) = \text{T}$.

Let's now define the following set: $L_Q = \{\langle M \rangle \mid Q(M) \text{ holds}\}$. We want to show that $A_{TM} \leq_m L_Q$. Given $\langle M, w\rangle$, we construct a new Turing machine $M'$. On input $x$, $M'$ simulates $M$ on $w$. If $M$ accepts $w$, $M'$ will simulate $M_0$ on $x$, and the result will be either accepting, rejecting, or an infinite loop. If $M$ does not accept $w$, then $M'$ just rejects $w$.

Now we claim that $\langle M, w \rangle \in A_{TM}$ holds if and only if $Q(M')$ holds. Proof of this: if $M$ accepts $w$, then $M'$ will just run $M_0$. So $L(M') = L(M_0)$. Thus $Q(M_0)$ holds if and only if $Q(M_0) \Leftrightarrow Q(M')$. If $M$ does NOT accept $w$, however, then $L(M') = \varnothing$, so $Q(M')$ does not hold. Thus the mapping reduction is complete. $\blacksquare$

2Degrees of undecidability¶

$A_{TM}$ happens to be the most undecidable RE set you can find. We can call it RE-complete - every other RE set can be reduced to it. So if $B$ is RE, then we can say that $B \leq_m A_{TM}$. (The parallels with NP-completeness are pretty striking. Indeed, the notions of NP-completeness came about as a conscious imitation of the concepts here.)

There are also undecidable problems that are NOT RE-complete. In fact, there are many different degrees of undecidability! We'll talk about these more complex problems now.

Stephen Kleene proved that there exists a total computable function $T$ which takes as input $(k, m, n)$ and reports whether or not the $k$^th Turing machine (assuming some effective enumeration of Turing machines, which is possible since there are countably many) with input $m$ halts within $n$ steps. We assume that $m \in \mathbb N$ since it's convenient to work with integers, but it would work just as well with strings.

We define the following set:

$$H_{TM} = \{(k, m) \mid \exists m \text{ such that } T(k, m, n)\}$$

This set essentially existentially qualifies the halting problem (think of it as the set of machine-word pairs for which the machine will halt on that word). This set is undecidable but RE.

Now consider $\neg H_{TM} = \{(k, m) \mid \forall n \neg T(k, m, n) \}$ (so the $k$^th Turing machine does not ever halt on input $m$). This is co-RE.

Now consider the following set:

$$\{ k \mid \forall m \forall n \neg T(k, m, n)\}$$

i.e., the set of Turing machines that never halt for any input. This is equivalent to $E_{TM}$, which is co-RE.

So there's something more subtle involved than merely counting quantifiers if we want to determine the degree of complexity of a problem. Indeed, it has to do with the number of alternations of quantifiers. Consider the following set:

$$TOTAL_{TM} = \{k \mid \forall m \exists n T(k, m, n) \}$$

i.e., the set of machines that eventually halt for every input. Both $H_{TM}$ and $\overline{H_{TM}}$ can be reduced to this set (which is neither RE nor co-RE); these reductions are left as an exercise for the reader.

Here's another set to think about:

$$FIN_{TM} = \{k \mid \exists m \text{ such that }\forall x, n, \text{ if } x > m, \text{ then } \neg T(k, x, n) \}$$

So if $M \in FIN_{TM}$ then $L(M)$ is finite. It so happens that $FIN_{TM}$ is neither RE nor co-RE but also not equivalent to $TOTAL_{TM}$.

2.1Naming the hierarchy¶

$$\Sigma_n^0$$

The $\Sigma$ refers to sets that can be defined by formulas that start with the $\exists$ quantifier; the 0 refers to sets that contain only first-order quantifiers²; and the $n$ indicates that there are $n-1$ alternations.

$$\Pi_n^0$$

The $\Pi$ refers to sets that can be defined by formulas that start with the $\forall$ quantifier; the $n$ and 0 mean the same as before.

$$\Delta_n^0$$

The $\Delta$ refers to sets that can be defined by both formulas that start with $\forall$ and formulas that start with $\exists$; the $n$ and the $0$ mean the same as before.

Here's a diagram for this infinite hierarchy (with the 0 superscript, this is called the arithmetic hierarchy):

Some properties:

• $\forall n: \Sigma_n^0 \subset \Sigma_{n+1}^0$
• $\forall n: \Pi_n^0 \subset \Pi_{n+1}^0$
• $\forall n: \Delta_n^0 \subset \Pi_n^0$ and $\Delta_n^0 \subset \Sigma_n^0$
• $\forall n, i: \Sigma_n^i \subset \Pi_{n+1}^0$
• $\forall n, i: \Pi_n^i \subset \Sigma_{n+1}^0$

At every level of this hierarchy, there are ?-complete problems.

Note that $\Sigma_n^1$, $\Pi_n^1$ allow quantification over numerical functions. This results in another infinite hierarchy, which is called the analytical hierarchy. Higher-order unification is one example of a problem that falls within the analytical hierarchy. Problems like deadlock detection are even more undecidable.

2.1.1Relation to the computational complexity¶

Incidentally, if you limit it so that the quantification is only over finite structures, you get the complexity theory hierarchy (with $P$ and $NP$ and all that), except that we don't know if containment is strict or not.