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.