Tuesday, November 5, 2013

The halting problem and undecidability

The halting problem. Undecidability and RE sets. Notes on the course website

1The halting problem¶

The proof of the undecidability of the halting problem was first proven by Alonzo Church, using his system of lambda calculus. It was later proven independently by Turing, as no one understood Church's proof until much later.

The proof we will cover in this lecture is much simpler than either of the above, simply because we are familiar with the concept of software.

1.1Definitions¶

If $P$ is a program, then $\langle P \rangle$ is its text.

$P(x)$ means to run program $P$ on input $x$.

$P(x) \downarrow$ means that $P$ terminates (halts) at some point, when given input $x$.

$P(x) \uparrow$ means that $P$ diverges on input $x$ (so it never halts).

1.2Statement of the problem¶

There does not exist a procedure $H(\langle P \rangle, x)$ which can accurately determine whether $P(x) \downarrow$ or $P(x)\uparrow$ for all $P$, where $H$ itself always halts.

(Note that $H$ is, by convention, a boolean-valued function that returns true if the input program halts and false if it does not.)

1.3Proof by contradiction¶

Suppose that $H$ does exist. Consider the following procedure $S$, which takes as input $x$ (representing the text for some program), and is defined as follows: if $H(x, x)$ then loop; else, halt.

Now consider $S(\langle S \rangle)$. Does this halt or not?

Well, if it does halt, then $H(\langle S \rangle, \langle S\rangle)$ must return true, because that's what $H$ is supposed to be able to determine. But, by the way $S$ is defined, $S$ must then loop. Conversely, if it does not halt, then $H(\langle S \rangle, \langle S\rangle)$ must be true, in order for the program to have reached the "else" branch of execution. But then that means that $S$ must halt on input $\langle S \rangle$. Contradiction. $\blacksquare$

2Sidebar on partial functions¶

Section omitted, see notes on the course website if you really want to know.

3Decidability¶

3.1A note on terminology¶

The terminology in this field has undergone quite a bit of change. The word "recursive" used to mean "computable"; now, of course, recursive means something quite different and we just use the word "computable". In this course, however, we will be using "recursive" in the old sense: i.e., computable.

3.2Definitions¶

A set $X \subseteq \mathbb N$ is said to be decidable if there is an algorithm $A$ such that for every $x \in \mathbb N$, $A(x)$ terminates and answers the question "is $x \in X$". This can also be called a recursive set. Similarly, $L \subseteq \Sigma^*$ is Turing-decidable if there is an algorithm (or Turing machine) that can decide if $x \in L$ for any $x \in \Sigma^*$.

A language is said to be recursively enumerable (RE) if there exists an algorithm $A$ such that for any $x \in L$, $A(x)$ terminates and "yes". For $x \notin L$, $A$ must either return "no" or never halt. This concept is closely related to the idea of a semi-decision procedure. (An example of such a procedure for the halting problem would be to just run the program.)

Note that all of these definitions can be made for subsets of $\mathbb N$ or of $\Sigma^*$; they are fundamentally equivalent.

3.3Decidability and functions¶

Proposition: Let $X \subseteq \mathbb N$, where $X$ is infinite. $X$ is decidable $\iff$ $X$ is the range of a total, computable¹, non-decreasing function $f: \mathbb N \to \mathbb N$.

Proof: ($\Leftarrow$) Assume that we have such an $f$. Let $A$ be the algorithm that implements $f$. Given $x \in \mathbb N$, carry out the decision procedure. Run $A$ on $0, 1, 2, 3, \ldots$ and observe the output. (Note that $A$ is guaranteed to halt on any input since $f$ is total.) This gives us $x_0, x_1, x_2, x_3, \ldots$. If any one of these is $x$, then $x \in X$. On the other hand, if, for some $n$, $x_n > x$, then $x \notin X$, since $f$ is non-decreasing. This algorithm must halt because the $x \in \mathbb N$ that we are given is a finite number, and it's not possible for the range of $f$ to plateau indefinitely, since $x$ is an infinite set.

($\Rightarrow$) Suppose $X \subseteq \mathbb N$ is an infinite decidable set. Since it's decidable, there is an algorithm $A$ that is guaranteed to terminate for any $n \in \mathbb N$ such that $A(n)$ return true $\iff$ $n \in X$. Let's use this algorithm to construct a function. Run $A$ on $0, 1, 2, 3, \ldots$ and call the first number that $A$ finds to be in $X$ $x_0$, the next $x_1$, etc. Now define $f(n) = x_n$. $\blacksquare$

3.4Recursively enumerable sets¶

A set is recursively enumerable (RE) if there is an algorithm (which may run forever) that eventually produces all members. The elements don't need to emerge in any systematic order - if this were true, you could get a decision procedure out of it, but that's not possible for all RE sets.

We define the following set (important!):

$$A_{TM} = \{\langle A, w \rangle \mid A,\text{ when run on } w,\text{ halts and accepts} \}$$

where $\langle A, w\rangle$ is the encoding of the algorithm $A$ with input $w \in \Sigma^*$.

Clearly this set is not decidable due to the halting problem. But it's the next best thing - it's an RE set.

Let's sketch out a proof for that. Here's a procedure capable of producing all members of $A_{TM}$ (eventually), which uses dovetailing. First, we list all pairs of Turing machines and words in a table:

• $\langle A_1, w_1 \rangle$, $\langle A_1, w_2 \rangle$, $\ldots$ in the first row
• $\langle A_2, w_1 \rangle$, $\langle A_2, w_2 \rangle$, $\ldots$ in the second etc
• etc

Next, we find a way to traverse the structure. The simplest is probably the way used in the standard proof for showing that $\mathbb N \times \mathbb N$ is countable - start at the top-left corner, then move one column over and go diagonally down and left, and repeat after each diagonal. Suppose we have a simulator that can run an algorithm on some input. First, we run $A_1$ on $w_1$ for one step and stop. If it accepts immediately, great; otherwise, we'll come back to it later. Then, run $A_1$ on $w_2$ for two steps. Then run $A_1$ on $w_1$ for one more step. Then $A_2$ on $w_1$ for three steps, $A_1$ on $w_2$ for one more step, and $A_1$ on $w_1$ for one more step. Continuing in this fashion, we see that we manage to run every word on every machine for $n$ steps for all $n$, avoiding infinite branching in the process. (There are a number of ways of specifying the number of steps of the algorithm to run at each step; see the notes for a different one.)

3.4.1Some properties¶

• The union of any finite number of RE sets is RE
• The intersection of any finite number of RE sets is RE

Proofs: run the enumerators in parallel.

• Any decidable set is RE.
• If $X$ is RE and $\overline{X}$ is RE, then $X$ is recursive.
• If a set is decidable, so is its complement.

All of these are fairly straightforward to prove.

3.4.2Post's theorem¶

We'll now look at pairs of numbers: $[n, m] \in \mathbb N \times \mathbb N$. Now, we can talk about the decidability of sets of pairs of numbers just as easily as we could of sets of numbers. Suppose we have two functions $\Pi_1$ and $\Pi_2$ such that $\Pi_1([n, m]) = n$ and $\Pi_2([n, m]) = m$. Post's theorem is as follows:

A set $X \subseteq \mathbb N$ is RE $\Leftrightarrow$ (there exists a decidable set $Y \subseteq \mathbb N \times \mathbb N$ such that $x \in X \Leftrightarrow \exists y \in N$ with $[x, y] \in Y$).

Proof: ($\Leftarrow$) If $Y$ is decidable, we just iterate through all pairs (diagonally), and at each stage we check if the pair is in $Y$ or not. If so, we project the first element, which is in $X$. This is a semi-decision procedure for $X$.

($\Rightarrow$) Since $X$ is RE, there is an algorithm $A$ for enumerating it. We define $Y = \{[x, n] \mid A \text{ enumerates } x \text{ in } n \text{ steps.}\}$. $\blacksquare$