Now, we're going to explore the Turing
Machine in some depth. We start off with
what I'd like to think of as programming
tricks for Turing Machines. It's not that
anyone is really going to program a Turing
Machine. But we need to argue about what a
Turing Machine could do, if we really
needed to have it do it. That is how we
argue about the capabilities of Turing
Machines. For example, we argue that it
can simulate a real computer. Then we
delve into the matter of Turing Machines
with less capability, but the same ability
to define exactly the recursively
innumerable languages. And we argue that
some natural extensions of the touring
machine idea. For example, make them non
deterministic. Do not add power. They
still accept only the recursively
innumerable languages. The conclusion I
want to draw from these restrictions and
extensions is that the classically
recursively innumerable languages is
really an important class with many
definitions and that it really does
represent what can be computed by any
realistic notion of what computation
means. And finally we'll look at some of
the closure properties of recursive and
recursively innumerable languages. The
first program we trick is thinking of the
tape as if it had multiple tracks. This
idea enables us to describe touring
machines that do things like leave markers
on their tape so they can find their way
back to an important place. We get tape
tracks if we think of each tape symbol as
a, as a vector with K components, each
component chosen from some finite
alphabet. We can think of the [inaudible]
components of each tapes in [inaudible]
forming the ith track. Input symbols will
have the blank symbols in all components
but one. Which then becomes the track of
where the input is placed. Here is how we
can visualize a turning machine with three
tracks. This symbol is viewed as the
vector of x y z. But it is really just one
tape symbol. Let's suppose the input is
written on track one. Then the input
symbol zero must be thought of as the
vector zero blank, blank. And the blank
symbol is thought of as the vector blank,
blank, blank. A good use of the idea of
tracks is to use one track for data and
another track for marks. In the marking
track, almost all the tape squares have a
blank value, but one or more have special
symbols, the marks, that indicate a place
on the tape that the turn machine needs to
find later. Here's an example. The bottom
track holds the data and the top track is
the marking track. This symbol XY
represents a marked Y. And these symbols
are unmarked of the U and Z respectively.
A similar trick is to think of the state
as a vector, with each component from some
finite alphabet. The first component is
used to control operation. What we
normally think of as the state. But other
components are used as, as a cache to hold
values the Turing Machine needs to
remember. Typically, these values are bits
or tape symbols. But they can be anything,
as long as they're chosen from a finite
alphabet. Here's an example that will
illustrate the three tricks we talked
about. The Turing Machine is not really
useful. All it does is copy its input over
and over again, moving right on the tape.
Here are the values that will appear on
the control component of this state along
with the intuition about what they're
supposed to be doing. In control state Q,
we mark the current position. Store the
current input symbol in the cache
component of the state and move right.
From Q, we also enter the control state P.
In state P we run to the right looking for
a blank. When we find it, we deposit the
symbol we have stored in the cache on the
data track, and then we move left. From
state P we also enter control state R in
which we run laps looking for the mark
that was left by state Q. When we find it,
we remove the mark, enter state ! and
repeat the process with another symbol.
The state is a vector. The form little X,
capital Y. Your little x is q, p, or r,
one of the control states and y is the
cache component. It's values are zero, one
or b. Incidentally, we shall see that the
only state, only state p uses zero or one
in the cache. The other two states just
have the blank of the cache thus there are
really only four states. Tape symbols will
be vectors u v. The first component
represents the marking tracks so U is
either X, the mark, or a B, which is no
mark. The second component is the data
track. So V can be either zero, one, or B.
We regard as the blind symbol, B0 as input
symbol zero, and B1 as input symbol one.
Well now describe the transition function
of this touring machine. But before we do,
let's understand that A and B, can each
have the values zero or one, but in a
rule, all occurrences of one of these
letters has the same value. Thus this is a
pair of rules, one for each value of A. It
says that if a controlled state is Q copy
whatever symbol A is on the data track
into the cache. That is this guy. Winds up
here in the cash. The position under the
head is marked X, as we see here. And the,
the head moves right and the control state
becomes P. There are two families of rules
for control state P. If the current tape
symbol does not have a blank in the data
track. Then stay in the same state, leave
the tape symbol as it is, and move right.
Note that A and little b, can represent
either zero or one independently. So there
are really four rules represented here.
When the blank symbol is reached, place
the symbol A. That is in the cache, in
the, in the data track of the square,
currently reached. That is, the guy in the
cache winds up in the data track. Go to
control state R, and move to the left. And
here are the rules for control state R. In
state R as long as we do not see the mark
in the first track, we simply move left
with no change in the state or the tape
symbol. When we find the square that has
the mark, we do three things: we remove
the mark, we go to control state Q. And we
move to the right. We'll be at the
position just to right of where the mark
was. We're back in state cue so the whole
cycle will repeat again with whichever
input zero or one is in the next square.
Here's a motion picture, we are in control
state cue with an empty or blank cash and
we're at the left end of the input 01.
We're going to pick up the zero for the
cash and mark the current square going to
control state P and moving right. We did
all that. Now we failed to see a blank in
the data track so we'll just move right
again. Now we see the blank. So we deposit
the zero in the cash. And go to state r
and move left. Bingo. We haven't found the
mark, so we'll move left again. Now here's
the mark. We remove the mark, go to
control state Q and move right. And here
we are in a situation similar to that. In
which we started. We'll pick up the one.
Mark the square we're at. And move right
in state p. Here we go, off on another
cycle. It never ends. We keep writing 01,
01, 01, so on, on the data track. We're
now going to start exploring restrictions
of the original Turing Machine model that
are powerful enough to simulate the
original model. And therefore, also define
exactly the recursively enumerable
languages. Our first restriction is a
minor one, compared with some of the
amazingly strong restrictions we're going
to mention later. But this restriction is
that we can assume the tape is infinite to
the right of the input only. Tape squares
to the left of where the input is placed
do not exist, and may not be used. The
Turing Machine halts if it tries to move
left into a non-existent square. But we
shall see that in the construction that
simulates a two way infinite tape by a one
way infinite tape, that it is also
possible to design a Turing Machine, so it
never makes that mistake, and never falls
off the tape. Suppose I have an ordinary
Turing Machine with a two way infinite
tape. We want to simulate it with a one
way infinite tape. So let's call the
initial position of the head square zero.
Positions to the left are -one, -two, and
so on, heading left. While positions to
the right are +one, +two and so on. The
new turning machine will have to tracks on
its tape, and never move left from
position zero. The top track holds the
positions 012 and, and so on of the
original Turing Machine. And in the bottom
track, paired with positions zero is a
special marker, a star. It is the presence
of this market that warns the new Turing
Machine never to go left from that point.
Also on the bottom track are all the
negative positions of the original touring
machine with position minus I paired with
position i. That is, the bottom track
holds the tape to the left of position
zero, but backward. Here's a picture of
the new Turing Machine. Its state holds
the state of the original Turing Machine,
plus s bit url that tells it whether to
look at the upper or lower track to
simulate a move of the original. When that
bit is U, the new Turing Machine moves its
head in the same direction as the
original. But if the bit is L, then it
moves in the direction opposite to that of
the original. At the first move, the
market star will be placed on the lower
track. However, there is no need to modify
the input symbols since the negative
positions of the original Turing machine
initially hold blank. And we can treat
each of the input symbols and the blank of
a new Turing machine as if they had a
second component that is blank. There are
several other restrictions that are
discussed in the text that we're not going
to cover here. It might be surprising, but
if you give a push down of automaton. Even
a [inaudible] push down automaton a second
stack. Then it can simulate a touring
machine. The idea is that one stack hold
whatever is to the left of the head.
Including the head position itself. Where
the top of the stack at the right end of
the string. The second stack holds what is
to the right of the head position, with
the top of the stack at the left end. The
two stack PDA can figure out a move for
the touring machine. The head moves left
and a symbol is popped off the first stack
and pushed on to the second. The head
moves right and the top symbols move to
the second stack to the first. Moreover an
even stronger restriction on the two stack
PDA can be made in addition to
determinism. The two stacks can each be a
counter that is a stack that has only two
stack symbols. One of these symbols, the
bottom marker can only appear as the
bottom symbol. Plus the stacks each act as
counters. You can add one or subtract one.
But you can only tell when the count is
zero. You can't tell one large count from
another. This comment speaks for itself.
The guy who discovered this construction
of Let's two counter simulated touring
machine was Patrick Fisher. He was one of
the really early computer science
professors and apparently attracted the
attention of the unibomber. Pat was sent
an exploding package which was opened by
his secretary, who was injured in the
blast, but fortunately survived. Now we're
going to look at several extensions to the
basic Turing machine that we've described.
These extensions have some use when we
talk about closure properties of the
recursively enumerable languages. But
mainly they are considered to convince you
that the basic Turing machine is good
enough. It captures all of what we might
think of as computing by any means. That
is our goal is to simulate each of the
extensions with the basic model and thus
to show that the extensions define only
the recursively numeral languages. Are
fist extension will allow any phonic
number of tapes. Then we add
nondeterminism. The last extension is
really a demonstration of how a touring
machine can simulate a name value store.
That is a storage system that let's us
associate any value with any name.
Recently, very large scale name value
stores have become a significant factor in
the big data world with systems like
Google's big table. However, our purpose
here is more mundane. A name value store
is the hardest part of a computer to
simulate. In essence, the memory
[inaudible] of a computer can be thought
of as a place where we store values and
locations, whether the location's in
memory addresses, cache addresses, or
block numbers on a disk. If we can show
how a truing machine simulates a general
name value store, then we should have a
good idea of how the truing machine can
simulate a real computer. A multi-tape
truing machine has k tapes for some fixed
k. There's one head for each tape. And
each head is positioned at one square of
its own tape. To determine a move of the
multi-tape turn machine you have to look
at the tape symbol under each head as well
as the state. And the action of the
multi-tape Turing machine consists of a
new state, a new symbol for each taped
square that is scanned, and a direction
for each of the heads. The heads move
independently and some heads may choose to
stay where they are rather than move it a
step. To simulate K tags we'll use a
Turing machine with a single tape but
we'll regard this tape as having two K
tracks. K of the tracks are used to
simulate each of the K tapes. While the
other K tracks are used to mark the head
position of each of the tapes. That is,
these tracks are blank except for a single
X in one of the squares. Here is a picture
of a one-tape turn machine simulating a
two-tape turn machine. There are four
tracks. Two of these tracks hold the
contents of the two tapes, while the other
two tracks hold only a single X each,
marking the positions of the two tape
heads. That is, the two-tape turn machine
has the head of its first tape scanning
this C. And the head of the second tape is
scanning this W. I hope it is clear that
the ordinary Turing Machine can, to
simulate one move of the two tape Turing
Machine, visit each of X marks. Store the
symbols that the two tape Turing Machine
sees in cache components of its own state.
And finally figure out the move that the
two tape machine would make. One tape
mission then visits each of the positions
with the x's again, changes symbols as the
two tape machine would. And moves the x's
to reflect the head moves of the two tape
machine. >> The one tape machine needs to
be careful to remember in a component of
its own state how many X's are to its
left. So, it can always find them all on
its own tape, but if we design the one
tape machine to do that correctly then it
is, it is possible for it to simulate the
due date machine. Although, it will
obviously take many of its own moves to do
so. Now let's look at the non
deterministic version of a touring
machine. We'll talk only about one tape
non deterministic machines but the
addition of several tapes along with non
determinism doesn't add power either. The
basic idea that the touring machine is
allowed to have more than one choice of
move for any state [inaudible] single
pair. Once a choice is made then the next
state, new symbol and head direction are
determined. That is you may have several
choices in a non deterministic touring
machine. But you can't pick a state from
one, a symbol from another, and a
direction from a third. As for the
non-deterministic finite automate and
[inaudible] automate, the non
deterministic Turing Machine said to
accept any sequence of choices, leads to
an ID with an accepting state. The basic
trick is to use the tape of the
deterministic machine to represent the Q
of IDs of the non deterministic machine.
The deterministic machine will make a
systematic search of all the IDs a non
deterministic machine can reach. If it
finds one with a final state, then the
deterministic machine accepts. But if it
never finds one, the simulation may go on
forever. But the deterministic machine
will never accept. Incidentally we should
start to become aware of a surprising
behavior of touring machines. Sometimes
they run forever without accepting or
halting. Moreover, we can't tell whether
the touring machine is going to do that or
whether it will eventually halt, either
accepting or not. That is, you can't tell
whether a touring machine is an algorithm.
Anyway, back to our description of how the
deterministic touring machine simulates
the nondeterministic. To determine the
[inaudible] machine needs a separate
track. In addition to the track that holds
the i.d.s of the none [inaudible] machine.
One purpose of this track is to mark the
I.D. That is currently at the head of the
queue of I.D.s. And we need another mark
whose job is to allow the deterministic
machine to make a copy of the ID at the Q
head, one symbol at a time. While it
changes this ID to reflect one of the
choices of moves of the un-deterministic
machine. Here is a picture of what the
tape of a deterministic machine looks
like. On the data track there is a
sequence of IDs separated by a special
symbol, pound sign. Which we assume is not
a symbol that can appear on the IDs
themselves. The mark X is at the pound
sign, just before the ID that is at the
head of the queue. The ID's to the left of
this point will never be useful again,
since they've already been processed. But
it is more trouble to erase them from the
tape than it is to just leave them there.
The mark Y indicates the last position of
the front ID that has been copied, with
one choice of move of the
non-deterministic machine. The
deterministic machine will run back and
forth between the Y and the first blank it
sees to its right. Storing the symbol
under the Y, in its state, and depositing
it at the first blank. When it returns to
the Y, it moves the Y one position right
until it has copied the entire ID.
However, making the changes that reflect
one move. The process is just a little
more complex than the simple Turing
machine we gave as our example in the use
of multiple tracks. Which ran back and
forth copying its input. Here's how the
deterministic machine processes the front
ID on the cue. First the deterministic
machine looks for the state within the
front id. By storing the state. And the
symbol to it's right on its own state. It
now knows all the choices of those the non
deterministic machine. Suppose there are m
choices of move. And the deterministic
machine will create m new ids at the rear
of the q. That is to the right of its
portion of its state currently holding
ids. The deterministic machine decides an
order for the m choice is. And creates an
idea reflecting each choice one at a time.
After creating all [inaudible] it finds
the x marker, and moves it to the pound
sign to the right. Thus moving to the next
id in the q. However, as an exception, if
the deterministic machine ever creates a
new ID with an accepting state, then it
accepts and halts its operation. [sound].
I described the workings of the
deterministic machine fairly informally.
But I hope you are convinced that the
determinist machine really could be
programmed to do what I suggested. That
is, you could write down a delta
transition function that did all the
things I talked about. However, there's an
additional concern that must be addressed.
Can we be sure that if any sequence of
choices by the nondeterministic machine
leads to a final state, then the
deterministic machine will eventually
follow each ID in the sequence and thus
will also accept. To prove that we first
observe that there's an upper bound, say
K, on the number of choices of move that
the nondeterministic machine has in any
situation. Thus, there most k id is
reachable after one move. K squared
reachable after two moves. K q after three
moves and so on. Suppose the final state
is reached after N moves for sum N. And
the number of IDs the determinist machine
might have to look at is at most this.
Which is the sum of the first N powers of
K before it sees the ID with the final
state. The exact formula is not important.
The point is that K is finite and N is
finite so the number of IDs examined is
finite. To see this point, notice that all
the IDs reachable after one move are put
on the cue before any ID that is reachable
by two moves. And all the IDs reachable by
two moves are placed there before we get
to any ID that take three moves to reach,
and so on. That is, the cue is organized
shortest distance first. To summarize, if
the non-deterministic machine accepts, it
does so in N moves for some finite end.
Therefore, the deterministic machine will
eventually construct the accepting idea of
the non-deterministic machine. Even though
it may take a number of its own moves that
is exponential in N. However, if no
sequence of non-deterministic choices
leads to acceptance. Then the
deterministic machine does not accept.
Thus the two machines define the same
language. All the constructions we just
showed will turn out to be quite useful in
the future. We're going to have to do
several important constructions involving
Turing machines. When we do that, we'll
assume the Turing machine that is input,
is as simple as possible. In particular we
will assume that it is a deterministic
machine with one tape infinite only to the
right. However, when we do the simulation
we're free to use a Turing machine that is
as powerful as we need. In particular, we
can allow it to be non-deterministic, and
to have as many tapes as we need. But
first let's take up how we simulate name
value stores by a touring machine. The
turning machine will have several tapes
that we'll describe later, but one of the
tapes is used to hold the sequence of name
value pairs. As suggested here. The format
we use is to separate pairs by pound
signs. And to separate the name from the
value by a star. We assumed neither a
pound or a star are symbols that can
appear in any name or value. A second
track of this tape will be used to mark
the left end of the, of the sequence. This
mark never moves. It's just there so we
can find the beginning of the sequence and
scan it, looking for a particular. A
second tape will be used to hold the name
that we want to look up. To look up the
value associated with a name, use the
marker to find the left end of the store.
Compare each name with a name on the
second tape. If we find a match, then the
associated value is between the star and
the next pound sign. However, one
operation we need to be able to perform on
a name value store is insertion. This
operation is like what happens when we
store into a computers memory. When we
insert name value pair NV there is no
value previously associated with name N
then V will now be associated with N.
However if there was an old value
associated with name N then that value by
V. Regardless of which case applies, the
first thing we need to do is to look up
the name N, using the second tape to hold
N, as we just discussed. If we scan the
entire store, and we never find N, then
append N star, the pound sign, to the
right end of the store. That is a true
insertion rather than the rewriting of a
value. But if we find some nv prime in the
store. We have to replace the prime by v.
If V is shorter than V prime, then you can
leave blanks to fill out the value. But
the hard case is, when v is longer than v
prime. Here, we have to shift the entire
portions of store that follows. Far enough
to the right to make room for v. Here's
how we'll do it. We use a third tape and
we copy the entire portion of the first
tape that is added to the right of V
prime, but make sure to mark the position
on the first tape that holds the star to
the left of the V prime. Remember this
tape has a second track for marks. Now
write v on the first tape where v prime
was. It's okay to over write any square as
to the right of where v prime was. Then we
restore the first tape by copying from the
third tape everything that was copied
there. The net effect is that the portion
of the first tape that held that to the
right of V prime, has been moved right as
many squares as was necessary to fit V in
place of V prime. Here's a picture of the
sequence of moves. First, we copy
everything to the right of the prime onto
tape three. Then we overwrite V on tape
one, covering anything we have to. And
then we copy tape three onto tape one
positioning it to the right of whatever
space V has taken. Okay, now we're going
to see something of the closure properties
for both the recursively innumerable
languages. That is, those that are defined
by Turing Machines that may run forever if
they don't accept. And the recursive
languages. Those defined by Turing
Machines that will eventually halt without
accepting, if they choose not to accept
the input. Each of these languages is
closed under the regular expression
operations union, concatenation, and star.
They're also closed under reversal
intersection and inverse homomorphism. The
recurs of languages. Not the recurs of the
innumerable languages are closed under
difference and therefore [inaudible].
Recursively newer of a languages, but not
recursive languages. They're closed and
they are homomorphoses languages. Let's
first look at closure [inaudible] union.
That l one and l two b language is
accepted by final state by touring
machines m one and m two respectively. To
make things simple we're going to assume
that M1 and M2 are one tape machines with
a semi-infinite tape. For the language L1,
union L2, the constructor Turing Machine M
with two tapes. First thing M does is to
copy its input from the first tape to the
second. Then, M uses one tape to simulate
M1, and the other tape to simulate M2. M
accepts if either accepts. To show that
the recursive languages are closed in the
union, observe that both M1 and M2 will
eventually halt whether or not they
accept. M will accept if either does, but
if neither accepts then M will eventually
halt without accepting so M is also an
algorithm. The closure of the [inaudible]
enumerable languages under union. We don't
know that [inaudible] two may run forever
if they do not accept. If either accepts
than [inaudible] will surely accept.
However, if neither accepts then
[inaudible] may run forever, but that is
okay since we only want to prove the L1
union L2 is [inaudible] enumerable in this
case not necessarily recursive. We're
going to use picture proofs for touring
machines quite a bit. Here's how we
represent an algorithm. A touring machine
that always halts. It's just a box with
two output symbols, accept and reject. We
should understand that reject just means
that the machine halts without accepting.
We know that an algorithm will eventually
make one of these signals and of course,
not both. Then the design of M can be
expressed by this diagram. It gets its
input W from the outside. And it feeds it
to M1 and M2, which it then simulates. M
produces the accept signal. If either M1
or M2 accept. If neither producers accept
then they eventually both produce rejects
and M produces the reject signal when they
both do. Because M will make one of these
signals but not both and of course it
makes the right signal to accept the union
of the languages. And here's how we
represent a turn machine that is not
necessarily an algorithm. It makes an
accept signal if it accepts, but we cannot
expect it to make a reject symbol. It may
just keeping making moves, but never
accept. This diagram is the design of M
for the case where M1 and M2 are general
Turing machines. Again, M feeds both the
input W. If either rays are the accept
signal then M does too. We have no idea
what M does if neither accepts but it
doesn't matter. M has the form needed to
show that the union of the languages of M1
and M2 is a recursively innumerable
language. Here's a picture proof of the
fact that recursive languages are closed
under [inaudible] section. M1 and M2 are
algorithms. We design M to feed its input
to the simulated M1 and M2. And M accepts
if both accept. And "m" rejects, if either
rejects. And here's a picture proof of the
intersection of recursively innumerable
languages. Again "m" feeds it's input into
"m1" and "m2" and it accepts, if both
accept. No, difference in compliment gives
us very different story for the two
classes of languages, recursive and
recursively enumerable. If you want to
accept the difference of the languages of
algorithms M1 and M2, simulate them both
until they halt. Except if M1 accepts and
M2 rejects and otherwise reject. The
picture is much like what we saw for union
and intersection of recursive languages,
only the logic combining the signals is
different. An important consequence is
that the complement with respect to some
alphabet sigma of a recursive language is
recursive. Surely sigma-star, the set of
all strings over sigma is recursive. So
the difference of sigma-star and a
recursive language is the complement of
that language. Unfortunately, this
[inaudible] does not work in the
in-cursively innumerable languages. They
are in fact not closed under [inaudible]
contemplation. We'll see a particular re
cursively innumerable languages.
[inaudible] Is not currently innumerable
soon. But just to see why the construction
for recursive languages doesn't work,
remember that M2 may never halt. So if M1
accepts, you may never know that the input
is in the difference. Now let's show the,
the recursively innumerable languages are
closed under concatenation. Like L1 and
L2, we define by Turing Machines, M1 and
M2. Assume M1 and M2 have one semi
infinite tape each. And, for
concatenation, we're going to construct M
a two tape non deterministic Turing
Machine. Given input W, M guess is a
prefix X of W that is in L1. Then let Y be
the remainder of W which then must be in
L2. If, that is, if W is to be in, the
concatenation of the languages L1 and L2.
M moves Y to its second tape and simulates
M1 on input X and M2 on Y. If both accept
then M accepts, since it is
non-deterministic, it will guess every
possible way to break W into two pieces.
So it always accepts W is in L1
concatenated with L2. Next, the claim the
recursive languages are also close in
their concatenation, we can't use the
non-deterministic trick, or at least it's
rather hard to do so. However, m will
systematically try each possible break
point for w into x y. On m one on x and m
two on y. M1 and M2 always halt on each x
and y. If for any break point, both accept
their pieces, then an accept. But if all
break points lead to rejection. By one or
both of them one in m two. Then M
eventually runs out of things to try and
rejects. For closure on this star, the
same ideas work for, as for concatenation.
Suppose M1 is a touring machine for some
language L and we want a touring machine
for L star. For the recursively
innumerable languages, guess how many
pieces to break input W into and guess
where the points of separation are, except
if M1 accepts each piece. For the
recursive languages, don't guess, but
enumerate the break systematically. Since
M1 is guaranteed to halt any time it is
given a piece of the input W to examine,
we'll eventually get through testing each
of the possible ways to break the input.
Reversal is easy for both classes of
languages. First, reverse the input, and
then simulate the Turing machine for
language L, on the reversed input. We'll
not say anything more about this simple
idea. Inverse homomorphism is also quite
simple. Suppose L is a language, either
recursive or recursively enumerable, let M
be a Turing machine for L. Let H be a
homomorphism. Well the zonic [inaudible]
machine for h inverse of l. Start by
applying h to the given, input w. Simulate
m on h of w. Except w if h of w is an l.
If L is recursively innumerable and we've
got a touring machine which it may not
always halt for H inverse of L. But if L
is recursive then we know M will always
halt and thus so will the machine we just
designed. Last, let's show that the
recursively innumerable languages are
closed in their homomorphism. So supposed
L has a turning machine M1. We'll
construct a non deterministic turning
machine M for HL. Given input W, M guess a
string X and checks the H of X is W. If so
M simulates M1 on input X. If M1 accepts
X, then M accepts W. Thus, M accepts H
inverse of L. This construction won't work
for the recursive languages. The reason is
that if H maps some symbols to epsilon,
then the string X that M1 accepts may be
arbitrarily long. And M may have to
simulate an infinite number of possible
Xs. It can never be sure that there is no
X in L for which [inaudible] equals W.