CSC 341: April 6, 2007

From CSWiki

1 Instructor's notes for the class session
2 Study questions
- 2.1 Proposed Solutions

Instructor's notes for the class session

Reduction via computation history

Section 5.1 discusses one major variation on the theme of reduction: reduction via computation history. In reducing problem $B$ , which takes the encoding for an automaton $M$ as (part or all of) its input, to problem $A$ , which takes the encoding for a related automaton $M'$ as (part or all of) its input, the preprocessor that inputs $\langle M\rangle$ and outputs $\langle M'\rangle$ may arrange for $M'$ to do more than just reflect the structure of $M$ or simulate its operation; it may arrange for $M'$ to construct and process computation histories, that is, executation traces, sequences of configurations that $M$ goes through as it processes certain inputs. A proof by reduction via computation history still conforms to the overall design pattern for reduction proofs -- the goal is still to make the answer that the decider for $A$ gives for its input equivalent in every case to the answer that the decider for $B$ should give -- but the conceptual distance between the two equivalent answers is perhaps a little greater.

[edit]

The Post correspondence problem

Stated abstractly, the Post correspondence problem is to determine whether, given a finite set $\{(t_1, b_1), \ldots, (t_k, b_k)\}$ of pairs of strings on some alphabet, there is a finite sequence $i_1, \ldots, i_l$ of pair numbers such that $t_{i_1} \cdots t_{i_l} = b_{i_1} \cdots b_{i_l}$ . In the textbook's presentation, the two strings in a pair are thought of as occupying the top and bottom halves of a domino, and the problem is whether there is any way to line up dominoes from the given set in a finite, non-empty sequence, using any or all of the dominoes as many times as you like, in such a way that concatenating the tops of the dominoes in the sequence yields the same string as concatenating the bottoms.

The textbook gives two instances of the Post correspondence problem on page 199; in one case, the answer to the question is "yes" and in the other it is "no." Here's another instance (adapted from John C. Martin, Introduction to languages and the theory of computation, second edition [New York: The McGraw-Hill Companies, Inc., 1997], p. 349): Suppose that our set of pairs is $\{(\texttt{ba}, \texttt{abb}), (\texttt{b}, \texttt{ab}), (\texttt{abb}, \texttt{b}), (\texttt{ab}, \texttt{aba}), (\texttt{a}, \texttt{bab})\}$ . Can we line up the dominoes made from this set so that the same string appears above and below?

If any solution is possible, it must begin with the fourth pair, since in each of the other pairs the strings begin with different symbols. So we place the initial domino and get ab above and aba below. This means that the next domino's top component must begin with an a, so the next domino must be the third, fourth, or fifth in the set. Choosing the fourth would give us abab above and abaaba below, which rules it out; however, we might choose either the third or the fifth without creating a visible inconsistency. Suppose we choose the third; that gives us ababb above and abab below. Then the next domino's bottom component must begin with a b---it might be either the third again or the fifth. Suppose we again choose the third; that gives us ababbabb above and ababb below. Now we might consistently choose either the first or the second to continue; suppose we choose the first, and get ababbabbba above and ababbabb below. And so on.

If one of our choices doesn't work out, we may have to backtrack and follow the other alternative. Worse yet, perhaps we'll find ourselves extending the row of dominoes indefinitely, never encountering a visible contradiction but also never getting the right end to match up.

(Incidentally, there are solutions for the given set of pairs; one is to take the fourth, fifth, first, second, third, third, second, and third pairs, in that order. The common concatenation is then ababababbabbbabb.)

The significance and interest of this somewhat fanciful problem is that it can be used as a model of computation, and any questions about languages and their properties and relationships can be reduced to or simulated by Post correspondence systems. One can, for instance, model the process of generating a string in a context-free grammar, with the help of dominoes in which the top contains the variable on the left-hand side of a rule and the bottom contains the right-hand side of that rule.

[edit]

Undecidability

Although for particular Post correspondence systems it is sometimes possible either to demonstrate a solution or to prove that no solution is possible, there is no general algorithm that takes as its input a description of a Post correspondence system and determines whether or not there is a solution. If there were, we could use this algorithm to solve the acceptance problem for Turing machines, or any of a number of other problems that are known to be unsolvable. (Actually, the undecidability of the Post correspondence problem was first proved by reducing the the word problem for semi-Thue processes to it.)

To use the reduction design pattern for the proof, we have to supply an algorithm that converts any instance $\langle M, w\rangle$ of the acceptance problem for Turing machines into an equivalent instance of the Post correspondence problem. All of the detail work in Sipser's proof involves getting this preprocessing step exactly right, so that the particular instance of the Post correspondence problem that we construct really does have a solution if, and only if, $M$ accepts $w$ . (Here we'll walk through those details carefully.)

[edit]

Study questions

Solve the instance $\{(\texttt{a}, \texttt{aa}), (\texttt{bb}, \texttt{b}), (\texttt{a}, \texttt{bb})\}$ of the Post correspondence problem.
Determine whether the instance $\{(\texttt{ab}, \texttt{aba}), (\texttt{baa}, \texttt{ab}), (\texttt{ab}, \texttt{b})\}$ of the Post correspondence problem has a solution.
Determine whether the instance $\{(\texttt{a}, \texttt{aaa}), (\texttt{abaaa}, \texttt{ab}), (\texttt{ab}, \texttt{a})\}$ of the Post correspondence problem has a solution.
Why can't we simply program a brute-force solution-finder for arbitrary Post correspondence problems, one that would first check each domino to see whether its top and bottom match, then (if necessary) examine each possible pair of dominoes to see whether their concatenated tops and bottoms match, then (if necessary) each possible triple of dominoes, then each possible quadruple, and so on? Isn't such a solution-finder guaranteed to find a solution eventually, if there is one?
Determine whether PCP is Turing-recognizable.

[edit]

Proposed Solutions

a | a | bb| bb aa| bb| b | b
ab | ab aba| b
If there is a solution, it begins with ({abaaa}, {ab}), because starting with ({a}, {aaa}) would require a domino that had a bottom beginning with two as, and starting with ({ab}, {a}) would require a domino that had a top beginning with b, and there are no such dominos in this set.