Now we're going to see more undecidable problems. We begin with Rice's theorem
which tells us that almost every question we can ask about the recursively
enumerable language is undecidable, and we then introduce a problem called post
correspondence problem, which we also show as undecidable. Post's problem does not
appear to have anything to do with Turing machines, so the fact that we can show it
is undecidable is a valuable step on our road to showing real problem's
undecidable. However, Post's problem is still just a game. But we can use Post's
problem to show some real problems, for example questions about grammars, to be
undecidable. Well, first, see Rice's theorem. That theorem involves what are
called properties of languages. Formally, a property of languages is any set of
languages; the languages that we say have this property. For example, the property
of being infinite is the set of infinite languages. The property of being empty is
the set containing only the empty language. Well properties like being
infinite apply to any language, even not recursively enumerable ones. We need to
represent languages, and the touring machine is the most powerful tool we have
for representing languages. So we'll talk about properties of recursively enumerable
languages only. Solution. Consider a property to be a problem about touring
machines. Given a code for touring machine, does it define a language with
that property? So for any property P we can define a language L sub P, the set of
binary strings that represent a Turing machine whose language has the property P.
So for example, L sub infinite. So for example, L sub infinite. Is the set of
codes of term machines that define an infinite language. There are two
properties we call trivial, for reasons that will be obvious. For these two
properties, P, L sub is decidable. One of these trivial properties is the always
false property that contains no recursively enumerable languages. We can
think of this property as, is not a recursively enumerable language. This
property is actually true of some languages, but those are outside the
recursively enumerable class, obviously. And we're talking about properties only as
applied to recursively enumerable languages. How do we decide this property?
Given an input W, ignore it, and say no. Notice that even if W represents an
invalid Turing Machine code, we have agreed to take all those strings as
representing a Turing Machine that accepts the empty language. But the empty language
is a recursively enumerable language. So we are correct in saying that W's Turing
Machine does not have this property. The second trivial property is the always true
property. We can express the property as is a recursively enumerable language. The
algorithm for this property is to ignore the input and say yes. And Rice's theorem
says, for every property P except the two trivial ones, L sub P is undecidable. An
important part of the proof of Rice's theorem, which we'll be working on for a
while, is the idea of a reduction. There are actually several different notions of
reduction. We'll come back to that point later. But the simplest one, and the one
we need for Rice's theorem, is an algorithm that takes an input string W for
one language, or a problem L, and converts it to another string X that is an input to
another language or problem, L Prime. With the property that X is in L Prime, if and
only if W is in L. The value of having such a reduction is that it tells us L is
no harder than L prime, at least as far as decidability is concerned. If I know L
prime is recursively enumerable, than I also have a touring machine program for L.
If I know L prime is recursive, then I also have and algorithm for L. In either
case the solution for L is to take the input W convert it to X see what the
Turing Machine for L prime does, and take its output to be that answer for W. The
thing that turns a sting W into X is called a transducer. So far we have only
talked about a Turing Machine whose only output is the yes or no that is implied by
accepting or halting without accepting respectfully. But we can get other kinds
of output from a multi tape track machine if it doesn't make one of its tapes to be
the output tape and we got what is written there when the machine halts is its
output. We could, for example imagine such a [inaudible] it takes W on its input tape
and writes X on its output tape and then halts. So if we reduce language L to L
prime using such a transducer and L prime is decidable, that is, there is an
algorithm to test membership in L prime, then there is also an algorithm for L.
That is, we start by applying the transducer to input W, and producing
output X. We apply the algorithm for L Prime to input X, and decide whether or
not X is in L Prime. Either way, the algorithm rendered, renders a decision,
either yes or no. And these two steps for an algorithm for L. The whole thing takes
input W, and tells us whether or not W is in L. We sometimes see a reduction use the
discover and algorithm for L, but the more important use of the idea is the
contrapositive. If we already know that there is no algorithm for L, then there
cannot be any algorithm for L prime. That's how we're going to use reductions.
We'll take one problem that we may not be interested in but that we know is
undecidable and reduce it to another problem that we are really interested in
but whose status we don't yet know, and then we will conclude that the second
problem is also undecidable. Moreover, when we get to intractability, or the
theory of NP-completeness, we'll be using reductions there fast, to argue that a
problem like L prime can't be solved faster than the problem L. There are more
powerful forms of reduction that let us reach the same conclusion. That is if
there is an algorithm for L prime then there is an algorithm for L. We actually
saw one example of a more complex reduction where we started by assuming
that there was an algorithm for L sub U, the universal language. And showed how we
could then construct an algorithm for LD which we know does not exist. However, the
hypothetical algorithm we constructed for L's of D involved more than just turning
one string into another. We first, have to check whether the input w is a well-formed
code for turning machine and if not we answer the question directly. More after,
moreover. After doing a transduction where we turned input W into W111W, we had to
compliment the answer that we got from the hypothetical algorithm for L sub U. That
is we turned a yes answer into no and vice versa. In the simple version of reduction,
we are not allowed to modify answers in this way; we have to take whatever answer
we get. We'll revisit this issue of more general kinds of reductions when we talk
about [inaudible] completeness. There, the simple reduction is called the Carp
Reduction and more general kinds of reductions are called Cook Reductions.
Steve Cook and Richard Carp by the way were the people who made the earliest
contributions to NP Completeness Theory. We're now ready to prove [inaudible]
theorem. The idea is that we can reduce l, sub u to l sub b for any none [inaudible]
property b. Then since we know l sub u is undecidable, it follows that l sub b is
undecidable. Here's how we reduce value to l p. The input to l u is touring machine m
and an input w for m. The output will be the code for touring machine in prime.
That is at least the right form, since LP is a set of Turing Machine codes. Those
for which the language of the machine has property P. Of course, for the
transduction from M and W to M Prime to work, we must arrange that M Prime has
property P, if and only if M accepts W. That is, M Prime is an L sub P, if and
only if M and W is an L sub U. We'll design M prime to be a 2-tape machine. On
the first tape, M prime simulates another particular Turing machine, which we'll
call M sub L, on its own input, say X. On the second tape, M prime simulates M on W.
It is important to understand the M prime has only its own input x which the
transducer does not deal with or see. The transducer knows about the M's of L, it is
build into the design of the transducer. The transducer gets to see the code for M
and the string W, that is on its own input. Thus the transducer can build both
the moves of M and the input W into the transition function of the machine M
prime, that is its own output. None of M, M sub L, or W is input to M prime. We're
going to assume that the empty line does not have property P. If that is not the
case, then consider the complimented piece AQ. Surely we loved your language than his
property Q. But if we could prove that Q around this of [inaudible] then P also
must be on this side of [inaudible]. That is well P were in cursive language, then
still it be a Q is [inaudible] class of cursive language is disclosed in the
complementation. So let L be any language with property P. We know L exists because
P is not trivial. Also, let M sub L be the turning machine that accepts L. Here's how
M prime behaves. To begin, M prime writes W on its second take. It can do that
because the transducer seeing W generates a sequence of states that write W one bit
at a time. M Prime, from its start state, enters each of these states in turn. Then
M Prime moves the tape head for tape two to the left end. Goes to the start state
of M, and simulates W on input W. Again, M Prime can do that, because the transducer
sees both M and W, and makes the transition function of M part of the
transition function of M Prime. Suppose, during the simulation of M on W, M enters
an accepting state. Then M Prime goes to the start state of M sub L, and simulates
M sub L on the input X to M Prime, which has been just sitting there on tape one
being ignored so far. Where does M prime get the transition function for M sub L? M
sub L is a particular Turing Machine, one that accepts a language L with property P.
Plus the transducer itself can be designed so that it writes the transitions of M sub
L out as part of the transition function of M Prime. If M [inaudible] accepts the
input adds, then M Prime enters an accepting state. If M [inaudible] never
accepts ads, now it is M Prime. Does M-Prime ever get the stage where it
simulates an MC-bell? An M-Prime accepts the same language as MC-bell does, that is
L. But if M does not accept W then M-Prime never gets to the stage as where it
simulates MC-bell and therefore M-Prime accept nothing. Here's a picture to help
us remember what M prime does. It first simulates M on input W. So far M prime's
own input, X is ignored. But if M accepts W, then M prime simulates M sub L on its
own input X. And N prime accepts X if and only if X is in L. So to summarize what we
know about M prime. First, suppose M accepts W. Then M prime simulates M
[inaudible] on X and accepts X if and only if X is in L. That is, if M excepts W,
then the language of M prime is L. We know L has property P, so M prime is an LP. Now
look at the opposite case where N does not accept W. An M prime never even starts the
simulation of ML and therefore M prime cannot accepts input x. That is, in this
case, the language of M prime is the empty language. We know the empty language does
not have property P. Thus if M does not accept W, M prime is not in the language
LP. We concluded the out rhythm we described for converting m and w to m
prime is reduction of l sub u to l p. And therefore, that l p is undecidable. That
is rises theorem. This is a picture that reveals the argument for why the existence
or reduction from l u to l p proves that l p is undecidable. We have a real reduction
out rhythm. I hope you're convinced that you can program this out rhythm if you are
paid enough. We then contradict the hypothesis that LP has an algorithm by
supposing that algorithm existed. Then you could put together the reduction plus the
hypothetical algorithm. To build an algorithm for LU. Since we already proved
that there's no such thing, we have to look at what of this story hasn't been
proved. The finger points at the hypothetical algorithm for LP. Since we
didn't prove it exists, we just assumed it did. Thus, the assumption must be
responsible for the false conclusion. And we can conclude instead, that there is no
algorithm for property P. Thanks to Rice's theorem, we suddenly have an infinite
collection of undecideable problems about the languages defined by Turing Machines.
Here is just a tiny sample of the questions that are undecideable about
Turing Machines M. Is M's language regular, or is it context free? Does this
language include at least one string that is a palindrome? That is, a string that is
the same as its reversal. Is the language empty? That is, does M accept any string
at all? Does the language contain at least 1000 strings? But Rice's theorem also
applies to programs since you can write a program to simulate a turning machine.
That tells us any nontrivial question about what a program does will also be
undecidable. I want to emphasize about what a program does. There are lots of
questions about what a program looks like that are decidable. For example, I can
tell whether a program uses more than twenty variable names, but that's not a
question about what the program does. An example of a question about what a program
does is, does the program eventually hall, halt on any input? That is undecidable.
Or, does the program correctly sort its input? That's undecidable. Or, does this
line of code ever get executed? That's undecidable. We're now going to take up
post correspondence problem, affectionately known as PCP. Pcp is the
first example of a problem that is undecidable, yet doesn't involve touring
machines or programs. Which are really the same thing. As we said, PCP is not really
important by itself since it's just the made up problem, but it leads us to proofs
that many other problems are undecidable. These problems are unrelated to touring
machines but are related to matters like context-free languages that were not
developed for the purpose of exposing undecidable problems. That is, we studied
grammars for their use in matters like describing the structure of programming
languages. We had no intent to describe problems that turn out to be undecidable.
It just turned out that there were undecidable problems lurking in the theory
of context-free grammars. An instance of PCP is a list of corresponding strings.
That is, a list of pairs of strings over some particular alphabet sigma. The, the
incident has some number of pairs, say N. The first pair is W1X1; the second is W2X2
and so on. None of these strings can be the empty string. The PCP question is,
given a list of corresponding pairs, whether we can find a list of one or more
[inaudible] I1 thought IK that we can treat as the sequence of pairs that we
choose. There can be repetitions in this list, the property of the list that makes
the answer to this instance of PCP be yes, is that when we take the first component
from each pair on the list, that is. Wi1 is actually the first component of the.
Pair that we indexed as I sub one I can't draw on the slide two levels of subscripts
then a W, the second W I two is the... That W from this list that has in the... I
that is from the I two pair on that list and so on. Then we get the same string if
we take the Ws from the pairs as if we took the second component with the Xs from
the pairs. Okay, such a list of integers is called the solution to the instance of
PCP. Here is a simple example instance of PCP. The alphabet will be zero and one.
There are two pairs; the first pair is zero and 01. The second pair Is 100 and
001. Okay. Every time a list of integers has one, it refers to this pair and every
time it has a two, it refers to that pair. Okay. In this case, it turns out; there is
no solution to this instance of PCP. The analysis of this simple instance is not so
easy. The easy part is that no solution can start with the second pair. Why? The
reason is that if we choose two as the first integer in the so-called solution
list, then the first string made from the Ws that are first component will begin
with this one. But the second string, the one made from the corresponding X's that
are the second components, begins with a zero. I don't care how you continue a
string that begins with one can never equal a string that begins with zero.
However, it is possible that the solution list begins with index one because for
pair one the two strings are not inconsistent, that is, one is a prefix of
the other. So let's see if we can build a solution starting with the first pair.
Since the two strings are not equal, we have to add another pair. We can't choose
pair one because the first string would then begin 00 and the second string would
begin 01. That could never lead to a solution. So the second index in the
solution must be two. Now both strings begin with 0100 and the second string has
an additional one. We're back where we were at the previous choice. We can't pick
one as the third index but we can pick two and we get a match up to a point with the
second string again having an additional one. If you think about it, we can never
make the two strings be the same because to do so we'd eventually have to use a
pair of the second string was shorter than the first. But there is no such pair in
this instance. We conclude that this instance has answer no. On the other hand,
let's change the instance a little by adding a third pair, 110 and ten. Now the
list of indexes thirteen is the solution. From the first strings of the pair is we
get zero followed by 110 which is. 0110 i.e. 0110 is a zero followed by a 110.
From the corresponding second strings we get 01 which is this followed by ten
that's that, and that also is 0110. In fact there's an infinitive solutions for
this instance, any string of events that exist in the language of regular
expression one to star two. That is after the one, we can use pair two any number of
times, including zero obviously, and finally use the pair three. So here's the
plan for proving PCPs undesirable. We're gonna start by introducing a modified
version of the problem called MPCP, or the modified post correspondence problem. The
modification is that a solution to MPCP must begin with the first pair. But
otherwise the modified and original PCP problems are the same. We'll show how to
reduce L sub U, the universal Turing machine language, to MPCP. And then we'll
show how to reduce MPCP to P sub P. In fact, this part is easier so we'll do it
first. Just to get the distinction between PCP and MPCP, observe that if we treat the
list of three pairs from our previous example of PCP as an instance of MPCP,
then the answer is yes. The reason is that there is a sequence within the Xs,
beginning with one. Namely, 1-3, that produces equal strings from the first and
second components of the pairs. But we can reorder the pairs; say by putting 110 and
eleven first. As an instance of PCP the order of the pairs doesn't matter, there's
still a solution. But as an instance of mpcp, there is now no solution. Any
solution would have to begin with the index one. But then the first of the two
strings would begin one, one zero. And the second would begin one zero. No matter how
we extend these strings. They're going to disagree in their second positions. Before
we can talk about reductions, we need to express pcp and mpcp as languages. The
instances of these problems can have any alphabet. So it is not im- immediately
obvious how to express the set of all PCP instances that have a solution. Again the
problem is, is that there no finite alphabet for this set, and languages just
need a finite alphabet. So we need to code symbols in a finite alphabet. We'll
represent the odd symbol of an alphabet by the symbol A, followed by I and binary.
Thus, we only need three symbols to represent any number of symbols. The order
of symbols, the alphabet, is not important. For example, if we have an
instance over alphabet, A through Z, we could represent A by A1, B by A10, and so
on. But we could also represent. Z by A1 and Y by A10, and so on. It should be
clear that the particular symbols used for the alphabet of the PCP instance does not
affect the outcome. And the only other symbols we need to represent instances is
the comma and left and right parentheses. Thus the alphabet for the language of PCP
instances will have an alphabet of six symbols the A, zero, one. Comma, left
paren and right paren. [sound], [sound] Now that we have a finite alphabet for
coding instances we can define two languages. L sub PCP, the language of
coded instances of PCP that have a solution, and L sub MPCP is the same for
the modified problem. Now we can do the reduction of MPCP to PCP. We'll describe
the transformation only but you should be able to visualize the process being
performed by a touring machine transducer. Our input is an instance of MPCP. The
output instance of PCP will use the same alphabet as the input instance plus two
new symbols, the star and the dollar sign. Of course all symbols new ones and the
symbols of the input instance of MPCP will be coded using A, zeroes and ones as we
just described. For each pair. W, X in the input instance. There's a pair in the
output instance based on W and X. For every first string W of the pair, we add
star after every symbol. So for example. Zero, one, Becomes zero star, one star.
And for X, the second string of the pair, we instead, add a star before every
character. So, for example, 1-1 becomes star one, star one. The output instance
also has a new pair unrelated to any input pair. This pair is dollar sign paired with
star dollar sign. And the output also has a second pair based on the first input
pair. This pair has stars placed after the symbols with the first string, and before
the symbols with the second string. Just like in rules one and two on the slide.
But the first string also has a star at the beginning. So, for example, the pair
01 paired with zero. Would become star zero star one star paired with star zero.
Here's an example. On the left is the instance of MPCP that is input to the
transducer. On the right are those pairs with the added stars. Notice that for each
pair, the stars come after the symbols on the first string and before the symbols on
the second string. And we always have this pair which will serve to make the strings
of the PCP instance match when there is a solution to the MPCP instance. Its job is
to add the missing start of the second string. And this pair also comes from the
first pair. It is just like the first pair of the PCP instance. That is this. And
this pair also comes from the first pair. It is just like the first pair of the PCP
instance. Except for the star at the beginning of the first string. Notice that
this is the only pair in the entire PCP instance where both strings start with the
same symbol. For example, this pair, has zero. As the first symbol of the first
string and star as the first symbol of the second string. Okay, all these pairs have
second strings that begin with star and the first string that begins with zero or
one. Suppose the MPCP instance has a solution, a sequence of indexes that yield
string W when we use the first strings in the pairs and the same string W when we
use the second string. Then we can get a solution to the constructive PCP instance.
In this case, the solution string will be W patterned with stars before each symbol
of W and also at the end followed by the dollar sign. For example. If W is one zero
one. In a PCP instances solution is star one, star zero, star one Star, dollar
sign. To get the PCP solution, we use the same sequence of indexes as in the
solution to the MPCP instance, with two exceptions. First, we use the index with
the special pair as the first index. Recall, this pair was constructed from the
first pair of the MPCP instance with the extra star. And we also add to the
solution of the PC instance. The index of the ender pair, star, dollar and dollar,
to the end of the list of indexes. Thus the solution to the input MPCP instance
means that the output PCP instance also has a solution. But the other direction
also holds. If the PCP instance has a solution we can modify to get a solution
to the input MPCP instance. The first index in the PCP solution must be the
special pair because that's the only pair in the PCP instance where both strings
start with the same symbol. Change this index to one, the index of the first pair
of the NPCP index. Leave all the other indexes unchanged but remove from the PCP
solution the last index which must be the index of the ender pair. Why? That's the
only pair where both strings end with the same symbol. Thus we've shown that the
answer to the questions, does the input MPCP instance have a solution, and does
the output PCP instance have a solution, are the same. That means we have a valid
reduction from MPCP to PCP. If we can prove MPCP is undecidable, which we'll do
next, then we have a proof that PCP is also undecidable. So our next task is to
show how to reduce L sub U to NPCP. Given an instance M and W, of L sub U, will
convert this to an instance of, of MPCP whose only possible solutions yield
strings that represent the sequence of ID's that N enters when its input is W.
More precisely, suppose this sequence is a sequence of IDs that M enters starting
with the initial ID with input W. Then any solution to the constructed NPCP instance
will yield a pair of strings that begin a sequence of IDs, separated by pound signs.
However, until M enters an accepting state, when we look at the two strings of
the partial solution, one form from the first strings of the indexed pairs, and
the second from the second strings of the indexed pairs. The second string will
always be a full ID ahead of the first string. Only if M accepts, will we be ab-,
will we be able to choose pairs that make the first string grow faster than the
second. And eventually make the two strings become identical. We're going to
assume as we can that the turning machine M from the input to L's of U has a
semi-infinite tape and never moves left from the initial head position, that's is
given the actual binary string representing M we can modify the
represented machine to mark its left end of tape. As we did when we described the
construction of a turning machine with semi-infinite tape from one that had a too
infinite tape. Then we can perform the reduction on the new Turing Machine that
we know does the same as M, rather than on M itself. However in what follows, we will
continue to refer to the input machine as M. The MPCP instance we construct will
have an alphabet that consists of all the states and tapes, and [inaudible] of M or
rather, the modified M plus the special marker pound sign. We assume that the
symbols used for states and tapes and [inaudible] of this joint, so we can tell
one from another in the ID. Here's the beginning of the construction of the MPCP
instance from M and W. The first pair has a first string that is just the pound sign
but a second string that is the entire first ID with input W surrounded by pound
signs. Note that the transducer gets the CW on its input so it can generate this
pair. We'll add the pair ##. It lets us add markers to the end of one ID in the
first string at the same time we add it to the following ID in the second string. Add
pair XX for every tape symbol X. This pair lets us add an X to the ID we're forming
in the first string at the same time we add an X to the next ID which is being
formed on the second string. Of course in order to make sure that the strings match,
it must be the case that the X appears as the first unmatched symbol of the second
string. They call the second string as one id as heads that these paired in effect.
Let's copy the tape of one id to the next id but prevents it from any changes that
are not just [inaudible] by the move of them. Here's a picture of copying id's.
Suppose we have just reached a point in the sequence of indexes when the second
string has a complete ID more than the first string but otherwise the strings
match. We can add to the solution we're constructing the pair A, A. That has the
effect of putting the first symbol of the new ID at the end of the first string. And
also extending the second string by the same symbol. That's what we want; since
there's no way this A could change in the next ID. We can also then add the index of
the pair, to the solution, extending the new ID one symbol further. This might or
might not be the right thing to do. The problem is that, if the move of M in state
Q with symbol C is to move left, then the second symbol of the new ID is the new
state, and B will be the third symbol. But just because we can choose the pair
doesn't mean we have to. If M is going to move left, there will be another choice of
next index that simulates the move correctly and the sequence where is chosen
instead will fail to yield the solution to the NBCB instance we're constructing. Now
we need to add the pairs that reflect the moves of M. For every straight Q and
[inaudible] symbol X, if the move of M is to the right, say PYR, we have. A pair in
which Q to the left of X, that's this, can be replaced by a P to the right of Y. That
correctly reflects the change in ID that occurs at the rightward move and if the
move is to the left, then we have a family of pairs, one for each symbol Z which
could appear to the left of the state. Note that we arranged that M can never
move left from its initial position, so there is no possibility that the state is
at the left end of the ID if M moves left. [sound] So if the leftward move has state
Q and symbol X replaced by state P and symbol Y, then for every Z, there is. A
pair that puts P to the left of the Z, and replaces the X, by the Y. One other
possibility is that in the current ID the state is at the right end of the ID
scanning a blank we've never visited before. If so, the state will actually be
to the left of the pound sign. And the pairs are almost the same but when
constructing the second string we should imagine an extra blank in front of the
pound sign. The blank is replaced by the new symbol Y of course. Following a
previous example, suppose that in state Q, scanning C, M does indeed move right,
going to state P and writing E in place of C. Had M moved left in that situation, the
sequence of pair choices would be dead in the water, unable to continue. However, in
that case, we could have chosen not to use the pair but instead, use a pair that
incorporated the left move, and handled the B properly. In this case, we have a
pair with QC as the first string. So we can match the string on the bottom. It
also extends the bottom string with EP, reflecting a move of M. Once the move has
been handled we can just match symbol against symbol here the pair dd is used.
And once we are at the end of the ID we use the pair of pound signs to separate
the IDs. And we're now ready to continue the sequence of pair choices to copy the
new ID, which is abed. And make it change by another move. But we need some more
pairs in the MPCP instance so that in case M accepts we can find a solution. Note
that if M never accepts then only the rules given so far can ever be used and
these can never lead to a solution because the second string is always one id longer
than the first. However, if M answers the final state F. Then it is possible for the
F to let's say, eat the neighboring symbols of an ID. We no longer have real
IDs of M but it doesn't matter. We simulated M enough to know that M accepts
W and our only concern then is to make sure that there's a solution to the MPC
instance based on M and W. Thus we add to the instance of MPCP pairs XFYF. Fyf and
XF, F for all tape symbols. X and Y. Using these pairs, together with pairs of the
form XX, the copy products of IDs as we have done. We eventually get to an ID that
is only the state of F. Of course, that isn't an actual ID of M, but it doesn't
matter anymore. And one more pair, F pound, pound, paired with the pound sign,
will end the two string being formed, making them the same, and yielding a
solution to the MCPC instance. So, here's an example where M has entered the final
state F, And the sequence of choice. Is either copying a symbol, or allowing f to
eat the adjacent symbol or symbols. Eventually leads to identical strings. So
here's what it looks like. Well we just have to copy that a. But now, the f can in
effect eat the b and c adjacent to it. We've got to copy the d. We got to copy
the e. We have to copy the pound sign. Now, the f can eat the a and the d. But we
have to copy the E. Have to copy the pound sign. Now F doesn't have anything that it
can eat to its left but it still will eat the E. And finally, Copy the pound sign
and now, F pound, pound pay with pound makes everything evened up, and we have
our solution. Now we know that PCP is undecidable because we successfully
reduced L sub too, it's O language and some PCP. And we're going to reduce PCP to
the problem is a context free grammar ambiguous. Then, for the first time, we'll
have an undecideable problem that arose naturally. That is, not because we were
looking for undecideable problems. Before we can talk about any problem involving
grammars, we need to find a code for grammars using a finite alphabet, just as
we did for PCP. So to start the encoding of grammars, let's represent the
[inaudible] terminal by symbol A followed by I and binary. That may look. Like with
us forgetting what the actual terminal symbols are, but since were interested in
ambiguity we can rename the terminals any way we like as long as we don't name two
terminals the same, and the ambiguity or un-ambiguity of the grammar will not
change. Then we'll represent the I-theorem by capital A followed by I in binary, we
will assume that A-1 is always the start symbol. The right arrow between the head
and body of a production will be represented by itself. Likewise, the c,
commas separating productions and the symbol epsilon will represent themselves.
For example, this grammar is represented by this string right here. The bar
connecting alternative bodies for S has been expanded so that there are two
separate productions. Okay, this. Right here, represents, this represents S goes
to 0S1. And this word wrap presents S goes to capital A. Finally this represents
capital A goes to little c. Suppose we have a PCP instance with k pairs and let
the ith pair be wixi. We need k index symbols to represent the numbers of pairs
and we'll use A1 through Ak which we may choose to symbols that do not appear in
the PCP instance itself. Notice that we are going to talk about reducing an
unquoted instance of PCP. So it could have any alphabet to an uncoded grammar which
could also have any symbols. However, the process we describe really takes place
with all the symbols coded in the manners we have described. It is easier to follow
the construction in the uncoded form so that's what we'll do. The list language
for the first half of each pair, the strings W1 through WK, has a context-free
grammar with productions. A goes to WIAaI. It also has the same sort of production
that, but with A omitted from the body. The latter kind of productions, these, are
used in the derivations. All the strings in this language which are some sequence
of the w I's with repetitions allowed and in any order with the corresponding index
symbols following but in reverse for example here's a derivation, okay, a could
derive in one step, let's say w1a, little a1. And then, in one more step, we could
use, let's say the terminal production for W2s. We get W1, W2, and then A2, A1.
Notice that the sequence of A's is the reverse of the sequence of W's. And we can
do the same thing with the second string from each pair. We'll use variable B, and
XIs in place of WIs. But the idea is the same. The language of strings generated
from A and B each consists concatenation of strings either from the WIs of its A,
or the XIs of its B, and these are the first or second components of the pairs.
They are followed by the reverses of the sequence of indexes of the pairs from
which these strings came. Here's an example of a PCP instance over alphabet
AB. We'll use one, two, and three as the index symbols. So the grammar for a start
symbol A is this, for example the second pair whose first string is BAA, gives rise
to these two productions. Here's BAA with the variable A in the middle and then two
which is the index, and then there's another production that's the same but
without the capital A. And here is the grammar for the second strings in the pair
with start symbol B. As an example if we choose the three pairs in order one, two,
three then there is a derivation from A that looks like this. So A, use the first
Choice. That's this production. Then we'll use the second choice which is this
production and that gives us A, B, A, A capital A the two and the one. And then
we'll use the third pair but we wanna end it and so we'll use that production and
that gives us A, B, A, A, B, A, A sorry B, B, A [sound]. It?s that. And then three,
two, one. We're now ready to show how to reduce PCP to the ambiguity problem. Given
the PCP instance, construct the two list languages with variable A for the first
strings of the pairs and B, for the second strings of the pairs. Then, add the
productions S goes to A and S goes to B. Of course, S is the start symbol of the
grammar. 'Kay, we'll show the resulting grammar is ambiguous if and only if
there's a solution to this instance of PCP. But first let's look at an example
that should actually expose how the proof in general works. 'Kay, here's the grammar
constructed from the PCP instance that we saw earlier. It is the sets of
A-productions and B-productions we saw plus the two productions for S. 'Kay,
notice there is a solution one, three. That is, the first pair was A, A, B. And
the third pair was BBA with BA. When we take the first strings of each pair, we
get ABBA, this followed by that. And when we take the second strings of each pair,
AB and BA, we also get ABBA. And this common string followed by the index string
in reverse, which is that. You have two left most derivations. One starting with a
and the other starting with b. Here is the derivation starting with a. [sound]. And
here's the derivation starting with B. So here's the proof this construction is a
correct reduction from PCP to ambiguity. First, suppose the PCP instance has a
solution say represented by the sequence of index symbols A1 to Ak. Note there can
be repeats on this, in this sequence. And W1 to Wk is the same string as X1 through
XK, that's what it means for this, for this index sequence to be a solution. Then
the two left most derivations with the string that is W1 through WK or
prevalently it's X1 through XK and is followed by AK down to A1. One starts with
S it goes to A and the other starts with S and goes to B. For the converse, we're
going to show that if there are two leftmost derivations of the string of
terminals, then one must begin. S goes to A, the other must begin, S goes to B.
Suppose there are two leftmost derivations that begin with S goes to A. Then we can
look at the sequence if index symbols, and the resulting terminal string, in reverse,
and learn exactly the sequence that productions used. Except for the last
production used, each should be the unique A production that generates the index
symbol, and has an A in the body. And the final production would be the one wi, with
the last, that is left most index symbol, and no a in the body. The same idea w
works for derivations that start with s goes to d. There can be only one with a
given sequence of index symbols. Here's an example. If a derivation starts with S
goes to A and produces a terminal string with index sequence 2321 and here's look
at derivation [inaudible] has to look like, okay. First of all we start with A.
The first production used must generate the one at the right end. And we need to
keep the A, so this is the only choice. So we've generated W1 off to the left of the
A. The next index symbol from the right end is a two. So we have to use this
production. Again, we still need to keep that A there, because we have more index
symbols to go. Then, the third from left index symbol is three, so this is the
production we have to use. And then the last index symbol is two, that is the
left-most index symbol. Is two. So we're gonna get rid of that A, and use this
production. That's the only way we could generate a string with 2321 at the end,
and no other index symbols. We can prove many things about context free grammars to
be undecideable as well. But to do so, we need to show that the complement of a list
language is also context free. Remember that the compliment of a context free
language need to not be context free, but fortunately these are. For the proof, we
find it easy to construct the push down automaton, in fact the deterministic push
down automaton, for the compliment. The PDA reconstruct will start with the bottom
marker on its stack. At first, some symbols from the PCP instance, not indexed
symbols, will appear. The PDA simply pushes them onto the stack. After the
first index symbol arrives, start checking that the proper strings appear on the
stack. That is, if we see an index symbol AI, then check that the proper WI appears
on the stack with the right end of WI at the top. The PDA pops all the symbols of
WI if so. Note that we're assuming this is the complement of the list language based
on the first components. If it is for the second components, we'll check that XI
appears on the top of the stack. Again, with the right end at the top. What we
seem to be doing is accepting the list language itself, rather than the
complement. But I didn't tell you when the PDA accepts. In fact, it accepts every
input with only the exception of when it has found a string in the list language.
That is, if the input so far was some sequence of PCP symbols followed by some
sequence of index symbols. And these sequences are not empty and the bottom of
stack marker is now exposed then the PDA does not accept this string. It will
accept any other string that follows, which cannot then also be a solution to
the PCP instance. Now we can use the compliment language. Let LA and LB be the
list languages for the first and second components of an instance of PCP. And let,
LA complement and LB complement be their complements. Now all four of these
languages are context-free languages. Let's consider the union of the complement
languages. This is also a context-free language by the fact that context-free
languages are closed under complementation. I claim that this union
equals Sigma star, where Sigma is the alphabet consisting of all the symbols
used by the languages involved, if and only if there is no solution to the PCP
instance. Suppose there were a solution, say represented by the index symbols a one
through a n. Then this string, yes, is not in the complement of L a. And the equal
string, this, is not in the compliment to be. Thus if there is a solution there is a
string missing from the union. Conversely a suppose string, y and down to A1, let's
say this. [sound], [sound]. Is missing from the union. That means Y is the string
you get by using indexes A one through A N and taking the first strings from the
index pairs. And it's also the string you get by doing the same with the second
pairs. That means A1 through A N is the solution to the PCP instance. We have now
reduced PCP to the question, is the given context for language equal to all strings
over its terminal health event. Thus this problem is undecidable. Here's another
undecidable question about context free languages. Is the language also a regular
language? We do exactly the same reduction from PCP and one direction is easy, if
there's no solution then we just showed that the union of the compliment languages
is Sigma Star and that's surely a regular language. But we also need to show the
converse, that if L, the union of the complement languages, is something other
than Sigma star, then it's not a regular language. Suppose we have a solution to
the PCP instance. And, in particular, let X be the index symbols in reverse. That
gives you the solution, and let W be the string you get by using the first string
from each of the index pairs in order. Or obviously equivalently, the second string,
from the same, pairs. Now, let H by the homomorphism defined by, H of zero is W,
and H of one is X. We claim that H of the string zero to the N, one to the N is also
an L. Gotta, remember, remember, L is the union of the compliments for any N.
Because the repetition of a solution to a PCP instance is also a solution to that
instance. However, H of Y can't be an L for any other Y. This point requires a
little thought. First, if Y isn't 0's followed by 1's, then H of Y isn't to the
right form to be a solution to PCP. That is, it will not consist the PCP instance
and both followed by index symbols. But if Y consists of N 1s preceded by a different
number of zeroes, and it can?t possibly represent a solution either. H applied to
the N 1s gives a particular sequence of index symbols but we know that the PCP
instant symbols of the sequence of index symbols corresponds to is H applied to N
0s therefore it couldn't also be H applied to a different number of 0s. So, if, L,
again, the union of the complements, were regular, then H inverse of L would also be
regular, Because regular languages are closed under inverse homomorphism. And the
complement of H inverse L would be regular, because regular languages are
closed in their complementation. But this language we just argued is the set of zero
to the N1 to the N, such that N is at least one. Okay, and of course we know
this language [sound] not to be regular.