We're not changing the subject matter
considerably. Until now, I've been talking
about simple models, such as finite
automata, or context free grammars, that
let us model mechanisms like communication
protocols, or processes like the parsing
of programming languages. Today we begin
to study the other side of automata
theory, the part that lets us show certain
tasks are impossible, or in some cases,
possible but intractable. That is, they
can be solved but only by very slow
algorithms. It might not be obvious but
just because we can state a problem
doesn't mean there is any algorithm at all
that can solve it. For example, can you
devise an algorithm to tell whether the
complement of a context free language is
empty? That is, does a grammar generate
all strings over its terminal alphabet? It
turns out you can't. And we're going to
learn the theory that lets us prove facts
of this kind. We begin with the central
theme of the study. Of what can be solved
by computer algorithms. The idea that all
data can be represented by integers. The
idea of countable sets. Those whose
members can be assigned integers one, two,
three, and so on, is essential here. We're
going to meet the touring machine which in
some sense the ultimate automaton. It is a
formal computing model that can, can
compute anything we can do with the
computer or with any other realistic model
that we might think of as computing.
Turing machines define the class of
recursively innumerable languages which is
thus the largest class of languages about
which we can compute anything. There's
another smaller class called the recursive
languages that can be thought of as
modeling algorithms. Computer programs
that answer a particular question and then
finish. I realize the concepts are vague
at this point, but we'll get to it all in
good time. If you took a modern course on
programming you're undoubtedly introduced
to the importance of data types or
classes. >> But when you look under the
hood, how these types are represented
inside the computer. You see that there is
only one type. Strings of bits. We could
base our whole theory on strings of bits,
but it is more convenient to convert
binary strings to integers. We can almost
see how to do that since integers can be
represented in binary notation, but there
is a small glitch we'll get to. And to
make the idea that all the world is
integers even more pervasive, remember
that programs that computers execute are
also, under the hood, just strings of 0's
and 1's, they therefore can be regarded as
integers. That lets up talk about the
hundredth program and things like that. As
we shall see, the fact that programs and
data are at heart the same thing is what
let's us build a powerful theory about
what is not computable. As a simple
example of a type that is really integers,
let's look at character strings. Strings
of ASCII characters can be thought of as
binary strings, eight bits to a character.
Or if you use Unicode, you need sixteen
bits per character, but the idea is the
same. Strings in any alphabet can be
represented by binary strings. And binary
strings are really integers. Does it make
sense to talk about the ith string in any
i. However, we have to be careful how we
do the conversion from binary strings to
integers. Because binary strings can have
leading zeroes, there is not a unique
representation of an integer as a binary
string. More to the point, if you do the
obvious conversion, then strings like the
ones shown, all seem to be the integers
five. But we can't call two or more
different strings by the same integer.
However, there is a correspondence between
binary strings and integers that is one to
one, and almost as simple. Put a one in
front of any binary string, and then treat
it as an integer. This way, no two strings
can correspond to the same integer. For
example, if we're given string 1-0-1. Then
put a one in front of it, and treat 1101
as a binary integer. And you'll get
thirteen, by the way. If you put a one in
front of 0101, then this integer is 21,
and so on. For a wilder example consider
images as a data type. There are many
representations of images. Let's talk
about gift for a [inaudible] example. A
gift file is just an ASCII string. So we
know how to convert ASCII to binary. And
then cover the binary string into an
integer in the way we just discussed. And
bingo, you have a notion of the
[inaudible] image. Here's another wild
example of proofs. A proof can be viewed
as a sequence of expressions or assertions
in mathematical form, each of which is,
are the given or follow some previous
statements in the sequence per certain
logical rules. We can encode mathematical
expressions in Unicode, it has pretty much
any symbol you use in mathematics. But we
can convert any expression to a binary
string, and hence to an integer. There is,
again, a small glitch. A proof is a
sequence of expressions, not a single
expression. So we need to fix on a way to
separate a sequence of expressions. We
also need to indicate whether an
expression is given, or follows from
previous expressions. We thus need to
introduce two new symbols into our
strings. One is a comma to separate
expressions. We can't just use the Unicode
comma, because the expression themselves
may use this symbol. The other is a marker
that says this is a given expression. The
following technique is useful not only
here but in general as a way to introduce
new symbols with any meaning into binary
strings while still keeping the strings
binary. First, given a binary string,
expand it by inserting a zero in front of
every byte of the string. For example. 101
becomes 01 that's the first one, 00 that's
the zero in the middle, and then 01. Now
as a consequence of this change strings
have no consecutive 1s. Use strings of two
or more 1s as the new symbols, for example
we'll use 111 to mark a given expression.
And one, one, as the marker for the end of
an expression. Here's an example of what a
proof as a binary string could look like.
The initial one, one, one, can only mean
that expression to follow is a given
expression. Here is the expression itself.
It was originally one zero one but we
expanded it with a zero in front of each
symbol. Of course one zero one is too
short to really be an expression since
even one unit code character takes sixteen
bytes, but not let's, let's not worry
about that. This one, one marks the end of
the first expression. Notice that this one
cannot be part of a special marker since
all expressions without the special
markers have even length and this one is
the sixth symbol in the expression. Here's
another given marker and another
expression. This one was zero, zero one,
one with zeros embedded. And another
expression ender and so on. As we said,
programs in a language like C or Java are
also a data type and can be represented by
integers as if they were data. First,
represent the program as an ASCII
[inaudible], or in some other alphabet
like Unicode, if the language requires it.
And then convert the character string to a
binary string, and then to an integer. Now
we can talk about the [inaudible] program.
And this should worry, there really aren't
more programs than there are integers.
While that number is infinite, you may be
aware that there are different orders of
infinity, and the integers of the smallest
one. For example, there are more real
numbers than there are integers, so there
are more real numbers than there are
programs. That immediately tells you that
some real numbers cannot be computed by
programs. We'll get to more concrete
explanation of what the [inaudible]
program really means shortly. We have an
intuitive notion of what a set of
[inaudible] are intimate. It says a finite
if there is a particular integer that is
the count of numbers on the set. The term
for the count of the number of members is
cardinality. For example, a set containing
A, B, and C is a finite set, and its
cardinality is three. And the formal
definition of a finite set is one for
which it is impossible to find a one to
one correspondence between the members of
the set, and a proper subset of that set.
Well, actually, the formal definition of
an infinite set is one for which there is
a one to one correspondence between its
members and a proper subset. Then. Finite
sets are formally the sets that are not
infinite. For example, the positive
integers are an infinite set. We can let
the proper subset be the even integers.
And the one to one correspondence matches
one with two, two with four, three with
six, and so on. Every positive integer I
is matched with the unique even integer,
2I. A countable set has a one to one
correspondence with the positive integers.
For example, the set of all integers,
positive and negative, is countable. A
correspondence maps zero to one minus I to
plus 2I for all I equal to or greater than
one, and plus I to 2I plus one for all I
equal to or greater than one. As a
consequence, the positive and negative
integers get [inaudible] in the ordering
as 0-1, 1-2, two and so on. The binary
strings are also countable. We saw how to
assign a unique positive integer to each
binary string. By putting a one in front.
And treating the result as a binary
integer. Likewise, the Java programs can
be put in one-to-one correspondence with
binary strings, and then with integers.
Many of these integers represent flawed
Java programs, things that don't compile.
But that is not important. The important
thing is that every working Java program
has you, a unique integer. A rather
surprising point is that pairs of integers
can be put in one-to-one correspondence
with the integers themselves. A simple way
to see this is to explain the ordering of
the pair as first pair, second pair and so
on. The ordering we want is first by sum
and then for pairs with the same sum by
first component. Thus one, one comes
first. It is the only pair with a sum of a
two. There are two pairs with a sum of
three, these guys. And we put two one
ahead of one two because it has the higher
first component. Then come three pairs
with sum four. These three, again ordered
by the first component. You can, in fact,
figure out a function F of IJ, such as the
pair of IJ is the F of IJ in that order.
But the important point is that some such
function exists. And therefore, it makes
sense to talk about the [inaudible] pair
of integers. We call the one to one
correspondence between a countable set and
the positive integers and enumeration of
the set. Thus, strings, programs, proofs,
and pairs of integers, for example, have
enumerations. Now, let's look at the set
of all languages over some fixed alphabet,
say, 01. Could this set be countable? The
answer is no and we can prove it. Suppose
that we are possible to innumerate the
languages so every language over zero one.
Was the ith language for some i. We
already know how to enumerate binary
strings. So we can talk about the ith
binary string. Now, I'm going to define a
language L. L is the language containing
those binary strings W such that W is the
Ith binary string. That must be true for
some I. And W is not in the Ith language.
L is really a language over alphabet 01.
Since we assume that the languages over
zero one are innumerable. That means that
for some j. L is the j language. So let X
be the J string. Surely some string is the
J in the enumeration of binary strings.
Now we can ask is X in L? It turns out
that if it is, then it isn't and vice
versa. To see why, remember the definition
of L. L contains W if and only if W is
not. In the language that corresponds to
the same integer I that W corresponds to
as a string. So let's focus on the case
where W is X, the Jth string. In that
case, the value of I is J because we know
X is the Jth string. Further we know that
L is the Jth language so both L, the
language being defined, and the quote Ith
language mentioned in the definition of L.
Are all the same. And they are L J. Thus
when we read the definition of L as a
reply is to X, it says, that X as in L,
which is Ls of J. If and only if, X is not
in L, again, which is Ls of J. We have a
contradiction. X is neither in L nor not
in L. That's an impossible situation. We
conclude that our assumptions are wrong.
The only unproved assumption we made. Was
that we could innumerate the languages
over zero one. So that is false. We can't
enumerate such languages. As a result, we
see that there are more languages than
programs, since the programs can be
enumerated. A particularly bad consequence
of this fact is that there are languages
for which no program can tell whether or
not a given string is in the language. On
the bright side, none of these strange
languages are context free or therefore
not regular, Since the CYK algorithm gives
us a membership testing program for any
context-free language. The process of
coming up with the language L that can't
be in any enumeration is called
diagonilization. The reason should be
apparent from this picture. Imagine an
infinite matrix in which the rows
correspond to languages, and the columns
to binary strings. A one in the entry for
row I in column J means that the Jth
string is in the Ith language. Zero means
it is not. If we could innumerate
languages then we could create such a
table. Look at the entries along the
diagonal and complement each one. That is,
replace zero by one and vice versa. Here's
what it looks like. A complement in
diagonal rotated 45 degrees looks like a
language. It tells which strings are its
members. Here strings one and two are not
in the language, the third and fourth are
and so on. But this language cannot be any
row because it disagrees with each row in
at least one position. In particular it
disagrees with the ith row in the ith
position. We're now ready to look at the
theory of Turing Machines. One important
purpose of this theory is to prove certain
particular languages to have no membership
algorithm. The first step is to prove
certain languages about Turing Machines
themselves, not to have membership
algorithms. We're then going to introduce
the important notion of a reduction. From
one problem to another. These are proved
through the form. If there is an algorithm
for problem P than there is an algorithm
for problem Q. We'll draw this as Q is
reduced to P. If we already know that
there's no algorithm for q, then how could
there be a algorithm for p. Because, if
there were an algorithm for p, then this
reduction would give us an algorithm for
q. By use of reductions, we don't have to
resort to diagonalization or another trick
to prove that P has no algorithm. Here is
the picture of a Turning Machine which you
should keep in mind. There is a state
which like all other automata can only be
in one of a finite number of states. There
is a tape, this. Infinite in both
directions, and partitioned into squares,
each of which can hold a symbol of a
finite tape alphabet. There's a tape head.
And always points to one of the tape
squares. The touring machine makes move
just like the automaton or the push down
automaton. For the touring machine. The
move is determined by the state and by the
tape symbol under the [inaudible]. In one
move, the touring machine can change its
state. Write a new tape symbol over the
old one. In the square [inaudible] its
scanning. And move the head one square
left or right. We might ask why we
introduce the turn machine, rather than
representing computation by C programs.
While you can develop a theory around
programs without using turn machines, it
would be much harder. The thing that we'll
come to appreciate about turn machines is
that they are so simple in their operation
compared to programs in a programming
language or even real computers. That
wouldn't matter if touring machines could
not mimic real computers, but they can, as
we shall argue. And in fact, one could
argue that, because Turing Machines have
infinite storage capacity on their tape,
they are even more powerful than
computers, since computers always have a
finite amount of storage, however large
that may be. But the difference is not
essential, since, in principle, we could
always by more storage for a computer. One
good counter argument is the universe is
finite so where are you going to get the
atoms from which to build all of those
discs? But even if you accept that the
universe is finite the limitation doesn't
seem to be effecting what we can compute
in practice. So we're never going to argue
that a computer is weaker than a Turing
machine in a meaningful way. So here is
the formula [inaudible] use for Turing
machines. There's a finite set of states.
We follow our tradition in using q for
this set. There's a finite input alphabet
for which we use the traditional sigma.
There's a [unknown] alphabet, gamma, which
always includes the input output alphabet.
The transition function is as always
delta, and we'll talk about how that works
next. There is a start state Q0, a member
of the set of states Q. Again, this is as
before. There is a blank symbol which we
usually represent by capital B. This
symbol is in the tape alphabet, but is
never an output symbol. There is a set of
final states. F, as usual. There are
several conventions about letters we shall
use. They are consistent with our earlier
conventions about finite and push down
automata. Lower case letters at the
beginning of the alphabet are still
symbols of the input alphabet. Now capital
letters at the end of the alphabet are
tape symbols which might or might not be
input symbols. Lower case letters at the
end of the alphabet or strings of input
symbols, again, that's as usual. And Greek
letters at the beginning of the alphabet
or strings of tape symbols which again may
include some input symbols. Now let's see
the transition function delta for a turn
machine. A turn machine is deterministic
and moreover does not have to have a move
in any situation. Delta takes two
arguments, the state and the symbol scan
by the tape head. Delta of QZ for state Q
and tape symbol Z. Can be undefined. In
which case, the touring machine can make
no more moves. Scanning a z in state q.
And the touring machine is set to halt.
But if delta of Q and Z is defined. Then
it is a triple P Y D, where P is the new
state. Y is the symbol that replaces Z in
the square being scanned on the tape head.
And D is the direction for the tape head
to move. This direction is either L for
left or R for right. And the move is by
one square. Here is an example of a
touring machine. It's input symbols are
zero and one. The touring machine scans
right on it's input looking for a one If
it finds a wanted change is it's a zero,
and goes to a final state F and halts.
However if it sees the blank symbol before
seeing a one, it changes the blank to one
and, and moves one square left repeating
the process just described. There are two
states for the Arcturing machine, Q and F.
Q is the start state, and F is the final
state. As we mentioned, the input alphabet
is 01. The tape symbols are only 01 and
the blank B. One move of the turn machine
is given here. It says that in state Q,
scanning a zero. In state Q, scanning
zero, it stays in state Q. Leaves the zero
on the square it was scanning and it moves
right. Another rule says that if it is in
state Q and sees a one. It goes to final
state F. Replaces the one by a zero and
moves right. It doesn't matter which way
the head moves in this situation since it
has accepted its input, but it always has
to move left or right, so we'll say right.
The last move of the touring machine is
this. It says that in state Q, while
scanning a blank, it replaces the blank by
one and moves left, staying in state Q.
Here's the beginning of a moving picture
of this touring machine. The three moves
are shown in the upper right with the move
that. Is applicable in a given situation
shown in red. Here, the touring machine
has just started. It is in a start state
and the tape head is at the left end of
the input which is 00 in this case. That
is, here's the input. The rule in red says
that in state Q scouting zero, it moves
right and leaves the state and symbol
unchanged. So we'll see that on the next
slide. Here it's done that. And it is in
the same situation, again scanning a zero,
so it again moves right. Now it sees a
blank on its tape so another rule is
applicable. This rule says that stay in
state Q and replace the blank by one and
move left. So it's made those changes and
the first rule is applicable again. The
touring machine is going to move right
while leaving the state and symbol
unchanged. Here the second rule applies.
In state Q it is scanning a one so it goes
to the final state F, replaces the one by
zero and moves right. Here, we see the
effect of the last move. The Turing
Machine has no move for when it is in
state F scanning a blank, so it halts. It
has also accepted, since F is the, in a
final state. Moving pictures of a Turing
Machine can get a bit cumbersome, so we're
going to develop an instantaneous
description or ID notation for Turing
Machine, similar to what we use for push
down automata. But in a sense, the touring
machine I.D.s are even simpler because the
input and paved contents are combined into
one stream. Moreover, we represent the
state in the head position by imbedding
the state to the left of the symbol being
scanned. We'll always assume that state
symbols are chosen so they do not conflict
with tape symbols and thus we can always
tell which symbol is the state. As we
suggested in our little example, the
touring machine gets its input on the
tape. The input, which is always a string
of input symbols, is placed on the tape
surrounded by an infinity of blanks to the
left and to the right. The touring machine
begins in it's start state with the head
at the left most input symbol. If the
input string happens to be epsilon then
the touring machine's tape is entirely
blanks and the head is scanning one of
them. An idea is a string of the form
alpha Q beta. Here alpha beta is the
contents of the tape between the left most
and right most non-blank symbols. That is,
the tape consists of an infinity of
blanks. Alpha, beta, and another infinity
of blanks. We should observe that after
any finite number of moves, the Turing
machine has only visited a finite number
of tape squares. So they can only be a
finite number of non blanks. Thus, we
always have a finite representation for
the tape, even though it is infinite in
extent. The state is Q, and it is placed
immediately to the left of the symbol the
head is now scanning. Remember we assumed
state symbols were chosen, so none of them
are taped symbols. Therefore, we can
always identify Q. As a special case Q can
be at the right end of beta. If so, it
means that the symbol being scanned is a
blank. This can only occur if the Turing
machine has just moved to the right, and
there are only blanks to the right. We use
the turn-style notation, as this, to
represent one move. And we use the
turn-style star This to represent any
number of moves including zero moves.
These are exactly as for PDAs. Here's an
example which corresponds to the earlier
touring machine example but now using the
ID notation. We start off in the start
state with a state to the left of the
input. At the first move, the touring
machine moves right, here, and then right
again. Now it is scanning a blank, and
it's action was to replace the blank by a
one and move left. Notice. That the state
is now two symbols to the left of the end
and it's scanning what used to be the
right most zero, that is this guy. It, it
again moves right and when it sees the
one, it enters state AF and again moves
right, changing that one to a zero. Now
we'll discuss the turnstile relation
formally. We have to discuss what happens
on rightward moves separately from what
happens on leftward moves. So suppose
there is a right move where in state Q,
scanning the Z, the touring machine goes
to state P. Writes y and moves right. Then
in any I d with q z as a sub string. Which
means that the touring machines is in
state q. And the z is being scanned. We
can replace q z by y p. That has the
effect of moving the head right. As well
as making the state and simple changes.
Called for. There's a special case when Z
is blank. Then it is additionally possible
that from an ID with Q at the right end,
that is this, which means that the blank
is being scanned, for the next ID to
replace the Q by YP. That is, the blank
which we didn't see in alpha Q. Has been
replaced by Y, that's here, and the state
Q became P. P, of course, moving to the
right of the Y that it just wrote. Now
consider a left move, where again, we are
in state Q scanning Z. The new state will
be P. And the symbol Y will be written
over the Z. If there is any symbol X, to
the left of the state in the current id,
such as this, in the next, in the next id,
the Z is replaced by Y, and the XQ is
replaced by PX. That means that X is being
scanned in the next ID. And of course, we
have gone to state P from state Q. But we
also have to take care of the case where
the ID has nothing to the left of the
state. Which means that there is an
infinity of blanks to the left of the
present head position. Then we reflect the
move by replacing the z by y. That's that.
And introducing a blank to be the symbol
immediately to the right of the state.
It's okay if the ID represents a blank
explicitly, and this is one of several
situations where we have to do so.
However, it is important to note that the
length of the ID can only grow by one at
each move, so it remains finite after any
finite number of moves. There are actually
two ways to define the language of a turn
machine. Final state is one of these ways,
of course. Formally, L of M, our Turing
Machine M, is the set of strings of input
symbols W, such that started in the
initial ID, that's Q, not W. With W on the
tape, M gets to some ID with a final
state. The other way to define a language
is by halting. We define each of them to
be the setup of input strings W, such that
started in the initial I.D. Again. M gets
the sum I For which no move is possible.
The two methods defining languages define
the same class of languages, as we can
show by simple Turing Machine
constructions that are not too different
from how we show that PDA is accepting by
final state and by empty stack at the same
language defining power. Given a Turing
Machine M, we are going to modify M into a
new Turing Machine, M Prime. The language
M prime accepts by final state. M prime
will accept by halting. We can easily make
the final states of M be halting states by
removing the rule for delta of Q and X
whenever Q is a final state. But we have
to protect against the possibility that M
halts without accepting, because the M
prime would then accidentally accept. So
for M prime, we introduce a new state S,
whose job is to make sure M Prime never
halts. One M Prime is in state S, on any
tape symbol X, M Prime stays in state S,
leaves the X as it is, and moves right.
Thus N prime will always have an X move in
state S. Eventually it will get to the
infinity of blanks to the right on the
blank and look at them one at a time. And
to make sure N prime doesn't hold
accidentally. Whenever delta of Q and X is
undefined for M, and Q is not a final
state, we'll have M prime enter the state
S. The construction in the other direction
is also pretty easy. Now we assume M
accepts some language L by halting, and we
want to modify it to become M double prime
which accepts L by final state. We
introduce a new state F, which is the
final state of M double prime. F has no
moves, so in fact, M double prime will
also halt when it accepts, but it doesn't
matter. Once a touring machine enters the
final state, if acceptance is by final
state then nothing it does in the future
will negate the fact that the input was
accepted. If M halts in any situation,
that is delta of Q in X is undefined, then
define it and make the next state be F. We
now have a proof that the class of
languages accepted by touring machines
using final state is the same as the class
of languages accepted by touring machines
using halting. The name for this, class of
language is, is the recursively
innumerable languages. You might rightly
wonder where this name came from. It
actually predates Alan Turing's paper
describing Turing machines. And it refers
to an earlier notion of anything we can
compute. I'm not gonna say more about
that. But there's another important class
related to touring machines. There are
called the recursive languages. These we
shall see are proper subset of the
recursively innumerable languages. An
algorithm formally is a touring machine
accepting by final state that halts on any
input regardless of whether that input is
accepted. This notion of an algorithm is
consistent with the information notions
you may have learned. However, it is
limited to accept and to reject
[inaudible] input. That is, all algorithms
in this sense render a yes no decision but
do not compute an output. We can extend
the notion of what a turn machine does to
allow it to produce output and then halt
in which case we have exactly the same
notion of algorithm that is taught in
freshman computing. The language that is
excepted by final state by some algorithm
is called a recursive language. This term
too comes from the history of attempts to
answer the question, "what can a
[inaudible] compute, prior to Turing's
insights?" For example, every context free
language is a recursive language. You can
implement the CY K algorithm for any
context free language on a Turing machine.
That Turning machine will halt once it has
computed the triangle of sets of
variables, and checked whether the start
symbol of the grammar is in the final set.
But the recursive languages go way beyond
the context free. In fact it is very hard
to come up with a language that is not
recursive. Except by using tricks like the
diagonalization that we discussed earlier.