Now we are ready to show some particular
problems not that have algorithms. The
central ideas of this lecture are first,
that turn machines can be enumerated. So
we can talk about the [inaudible] Turing
machine that let's us diagonalize over
Turing machines the way we diagonalized
over languages, showing a particular
language that cannot be the language of
any Turing machine. Then we establish the
principal that a problem is really a
language And we show specific problems not
to have [inaudible] machines. To enumerate
[inaudible] machines we're going to
develop the specific representation of
[inaudible] machines as binary strings. It
is sufficient to provide a code for
touring machines who's input output is 01.
Although we could encode others if we
wanted to. The reason that it is
sufficient to assume only zero and one are
inputs is that touring machine codes will
be binary strings. So it can focus on
touring machines on input output 01 as
inputs to other touring machines with the
same alphabet. The first thing we need to
do is provide integer codes to the
components of the touring machine. We give
integers one, two, three and so on to the
states. We assume that Q1 is always the
starred state, and we also assume that Q2
is the one final state of the Turing
machine. Notice that once Turing machines
enter the final state, nothing further
matters. So we can always merge all final
states into one. Thus we can restrict our
attention to touring machines with a
single final state and know that we can
still define any recursively enumerable
language. The other states will be
numbered three, four and so on. The tape
symbols that are also numbers starting at
one. We'll assume X1 is always the input
symbol zero and X2 is always the input
symbol one. X3 will always be the blank
and any other tape symbols are numbered
four and above. They're two directions but
we need to number them. D-, D1 is left and
D2 is right. Consider a rule expressed
using the integer numbering of the
components, that is the state QI scanning
symbol XJ well suppose the touring machine
goes to state QK right symbol XL and moves
in the direction Ds of M. Represent this
rule with blocks of IJKLM0s separated by
single ones. Notice that all the integers
are positive so the representation for a
rule never has consecutive ones. With them
represented in entire tour machine by all
its rules concatenated and separated by
pairs of ones. Once we have Turing
machines represented by binary strings we
can convert these strings to unique
integers using the trick we explained a
while ago. Put a one in front of a binary
string and treat the result as a binary
integer. Thus, we can talk about the
[inaudible] Turing machine. And of course
we earlier learned we can talk about the
[inaudible] binary string Small matters
that some binary represent flawed turn
machines for example, it might have a pair
of double ones with other then four single
ones between them. That would not
represent five blocks of 0s and therefore
would not represent any [sound]. However
let's assume that any binary string that
is flawed represents a turn machine
excepts the empty language. Likewise, if I
is the integer we get from such a string
then the Ith turn machine accepts the
empty language. So here is a table we're
letting Turing machines to the strings
they accept. The value in row I and column
J is one of the [inaudible] Turing machine
accepts the [inaudible] string. And zero
if it does not. Notice that if the
[inaudible] Turing machine is one of the
flawed ones, then it's rows is all zeros.
Any matrix of zero and ones with rows and
columns corresponding to all the integers
can be diagonalized over. That is, we can
construct an infinite sequence of zeros
and ones and call it D. Such that the
[inaudible] of D is the compliment of the
bit in position [inaudible] along the
diagonal. We can argue that D is not a row
of the matrix and therefore does not
represent the language accepted by any
Turing machine. De cap your row J because
it disagrees with the Jth row in their Jth
entries. Thus D can not be a row and
therefore the language it describes, the
language that contains the Ith string, if
and only if, the Ith bit of D is one is
not the language of any Turing machine.
Notice that this language can be described
as the set that contains the Ith string,
if an only if, the Ith Turing machine does
not accept the Ith string. Let's give a
name to this language, L sub D with a
diagonalization language. Again L sub D is
the set of binary strings W. Such that W
is the [inaudible] string for some I. And
the [inaudible] Turing machine does not
accept W. We just argued that L sub D is
not a recursively re-numerable language,
that is it has no Turing machine. We early
approve that since there are more
languages than integers and since there
are no more turn machines than integers,
we already know that there were languages
with no turn machine but now we're much
better off. We have a particular language
L sub D and a description of this language
such that L sub D is one of the languages
without a turn machine. Note, however that
L sub D is a delicate language. We know
what it is but we can't, for example, tell
whether a given binary string W is in L
sub D. To do so, we can figure out the I's
such that W is the [inaudible] string.
That's the easy part. Now we can write
down the code for the [inaudible] Turing
machine. In fact, that code is W. If W is
the code for a flawed Turing machine, we
know it doesn't accept W. But some W's
give good codes for Turing machines, and
in fact every Turing machine with input
alphabet, zero, and one has at least one
code W. We can't always figure out whether
a Turing machine is gonna accept or run
forever without accepting. So for at least
some W's we've never learned whether or
not that W is an L sub D. Let us introduce
the formal concept of a problem. In
formally a problem is a yes/no question
about an infinite number of possible
instances of the problem. Here's an
example of a problem that is actually
quite famous. And we'll see why soon. The
instances of the Hamilton Cycle problem
are undirected graphs. There are an
infinite number of graphs of course. The
answer to the question implied by the
Hamilton Cycle problem is yes. If there is
a Hamilton Cycle in the graph That is a
cycle that passes through each node
exactly once. For example, For example,
here's a graph that happens to have a
Hamilton cycle. It is also got some other
edges here and there. But the important
thing is that it does have the Hamilton
cycle in which every node appears once. So
formally a problem is simply a language
over some alphabet sigma. Each string and
sigma star can be viewed as an instance of
the problem once we decide on an encoding
for instance as a strings. We'll see a
number of examples of these encodings, but
we already saw one when we encoded Turing
machines as binary strings. It should not
be hard for you to devise an encoding for
graphs in a similar spirit. In the
language associated with the problem, is
the set of strings that code instances to
which the answer is yes. Typically as we
did for turn machines our coding allows
certain strings that are flawed. They
don't really represent an instance. Well
always assume that flawed encodings
represent instances for which the answer
is no. For example as a problem, the
language LD can be stated. Does this turn
machine not accept its own code? When we
talk about problems, we use the term
decidable. It means that there is an
algorithm to answer its question. That is
a turn machine that accepts the encoded
instances for the problem for which the
answer is yes and also halts without
accepting the other instances. So a
decidable problem is really the same thing
as a recursive language if we think of the
language as encoding a problem. The
opposite of decidable is undecidable. So
here is what we know about languages so
far. In the center we see the recursive
languages or as problems, the decidable
problems. Then there is a super set of the
recursive language called the recursively
enumerable languages. These recall other
languages accepted by Turing machines with
no guarantee that they will halt on inputs
that they never accept. And then there is
outer space. The uncountably many
languages that are not recursively
enumerable. They have no Turing machine at
all. So far we have one example of a
language, L sub D, that lives in this
region. Remember that the undecidable
problems are all those in either the
second ring. Recursively enumerable but
not recursive languages. Or an outer space
that is everything that is not yellow in
this diagram and a big question we need to
answer, are there any languages in the
second ring? Those that are recursively
and enumerable but not recursive. And
remember, the real goal of our plan is to
show some real problems that are
undecidable. The fact that L sub D is
undecidable and in fact super-undecidable
because it is not even recurs-ably
enumerable is interesting but it doesn't
by itself tell us anything about the real
world. So here are some examples of real
problems that are undecidable. Will a
program ever reach a particular line of
code? Is the given context re grammar
ambiguous? Are two given grammar?s
equivalent in the sense that they generate
the same language? But still staying
within the world of Turing machines rather
than the real world, but a necessary way
station on our trek to the real world is
to show a particular language to be
recursively enumerable but not recursive.
This is the language we call L sub U, the
Universal Turing machine language. In more
detail, the Universal Turing machine takes
its input a binary string consisting of a
code of some Turing machine M and some
input W for M. Universal Turing machine
accepts the coded M and W, if and only if,
M accepts W. The idea of the universal
Turing machine should not seem strange if
you ever contemplated a Java virtual
machine. The JVM takes a coded Java
program and input for the program and
executes the program on the input. In
fact, the JVM is more general on the
capability than a Turing machine which can
only make a single except output. The JVM
can cause whatever output the program
calls to be made. So let's see how to
build an universal Turing machine. First
of all, inputs to the Universal Turing
machine are in the form: a code for the
machine M, three ones, and then the binary
string W. Since a valid code for M can
never have three consecutive ones, it is
never ambiguous what part of the input to
the Universal Turing machine is M and what
part is W. The Universal Turing machine
accepts it's input if and only if that
input has a valid code for some Turing
machine M and that Turing machine accepts
W. So for example, the Universal machine
never accepts a string that doesn't have
three consecutive ones. We'll design the
universal Turing machine as a multi-tape
machine. The first tape will hold the
input and we never change that. The second
tape is used to represent the current tape
of M during the simulation of M with input
W. We'll discuss this representation
shortly. The third tape of the Universal
machine simply represents the state of M.
The first thing that the Universal machine
needs to do is to examine its input and
particularly that portion that represents
M. As to check that between consecutive
double ones there are always five blocks
of zeros. There also has to check that a
block of three ones appears somewhere on
its input, and regards this as the end of
rules for M. Finally since M is assumed
deterministic, the universal machine needs
to check that there are never two rules
that agree on the first two components.
All this checking will require running
back and forth on the input quite a bit.
It can be facilitated by copying blocks of
0s onto one of the other tapes and
comparing these with the other
representation for M. If any flaws are
found with this code for M or the 111 is
not found then M is regarded as a Turing
machine that accepts nothing. So the
universal Turing machine immediately halts
and rejects its input. Assuming the code
for M is valid, the universal Turing
machine next examines the code for M to
determine how many squares of its own tape
its need to represent one simple events
tape. That is we discover the longest
block of 0s representing a tape symbol and
add one to that for a marker between
symbols of Ms tape. Thus if say X7 is the
highest numbered symbol then we'll use
eight squares to represent one symbol of
M. Symbol XI will be represented I 0s and
seven minus I blanks followed by a marker
outside. For example, here's how we would
represent X5. Five 0s Two blanks and then
the pound sign. Now a [inaudible] is take
two to represent the input W. Remember 0s
are X1 and 1s are X2. Blanks on the second
tape of the universal machine all
represent X to X3, the blank of M. But we
won't initialize those squares until we
need to. Finally we initialize tape three
to hold the start state. That state is
always Q1 so it is represented by a single
zero. Now we're ready to simulate M. We
have the current state on tape three and
the tape of M is represented on tape two.
We scan the moves the M on tape one until
we find a move that matches both the state
and this tape symbol. If we can't find one
then apparently M halts without accepting
W so the universal machine does so as well
but if we find a match, we'll find right
after that on tape one, the new state
which we install on tape three replacing
the old state. We also find a new tape
symbol for which to replace the old tape
symbol under the head of tape two. And we
also move the tape head one simulated
square of M's tape left or right,
whichever the move says. And most
important, if MM enters an accepting state
then the universal machine stops
simulating and accepts zone input which,
remember, is the pair machine M plus input
string W. We claim that the language L sub
U is recursively enumerable but not
recursive. We just show that there is a
turn machine for the language L sub U so
surely LU is enumerable. But suppose L sub
U were recursive. That means there's a
turn machine that always halts and who's
language is L sub U. If that were the case
then L sub D the diagonalization language
would also be recursive. We're going to
explain why on the next slide. But we
already know that L sub D isn't
recursively enumerable, let alone
recursive. So let's assume that L sub U is
recursive. We construct an algorithm for L
sub D as follows. We're given an input W.
Let's suppose that W is the Ith string.
The first thing to do is to check whether
or not W is a valid code for a turn
machine. For example that it doesn't have
three consecutive 1s. If the code is not a
valid string, Then the Ith Turing machine
defines the empty language. That means W,
the Ith string, is not in the language of
the Ith Turing machine. Therefore, W is
[inaudible] D. Now suppose W is a valid
code for a turn machine. Then simulate the
hypothetical algorithm for L sub U on the
input W111W. That bit string represents
the Ith turn machine processing the input
that is the Ith string. Eventually this
algorithm will halt and tell us whether or
not the Ith machine accepts the Ith
string. If the algorithm says yes, the Ith
machine accepts the Ith string then we say
no because that means W is not in L sub D.
However if the hypothetical algorithm says
no, then we accept W because W is in L sub
D. With proof that there is no algorithm
or any kind of turn machine for L sub D
therefore we must blame our assumption.
The only thing we assume without proof was
that there was an algorithm for L sub U.
That means that there really isn't an
algorithm for L sub U. Put this facts
together and we conclude that L sub U is
really recursively enumerable but not
recursive. So here is our improved version
of the universe of languages. We still
have the decidable problems of
equivalently recursive languages in the
center. Outside there are two kinds of
undecidable problems. The second ring is
the languages that are recursively
enumerable but not recursive. We now have
a concrete example of such a problem L sub
U, the universal turn machine language.
And beyond that is the not recursively
enumerable languages of which we have one
concrete example, L sub D.