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.