Today, I'm going to make a few comments
that I hope you will find interesting.
I'll start with one of
the challenge problems,
because I think the construction
is interesting.
But unlike the hint I gave,
this construction uses
a non-deterministic automaton.
I'm then going to address a question
that came up in one of the early
discussion threads, but
that really wasn't appropriate until now.
It concerns whether there are things that
can do what a Turing Machine cannot do.
And finally, there have been
several threads doubting one or
another form of proof that
I have used in class.
These doubts are much more
reasonable than some might imagine.
And so I'm going to try to sort
out what needs to be assumed and
what needs to be proved.
I'm also going to touch on what it
really means to offer a proof, and
have that proof believed.
And I definitely don't mean,
the instructor is always right.
Recall that half of language L is the set
of first halves of the strings in L.
So if L, is, the two strings,
say, 0110 and 010,
then half of L,
is just the set containing 01.
The reason is, that for this string,
0110, the first half is the 01, and
for the other string, 010,
it's a odd length so it has no first half.
We want to prove that if L is regular,
then so is Half of L.
And we're going to start with
a DFA called A for L, and
we're going to construct an epsilon NFA
called B whose language is Half of L.
So here's how we're going
to construct B from A.
First, the states of B
are pairs of states of A,
plus an additional state s0
which is the start state of B.
B starts out, in s0,
makes one epsilon transition, and
from then on never returns to s0.
And after that, B will always be in
a state that is a pair p,q of A states.
And furthermore,
it will make no more epsilon transitions.
Here's what we intend to be true,
whenever B can be in state p,q
after reading the input w.
Now, remember, B is non-deterministic, so
it can be in many such states as once.
But first of all,
the first state of the pair,
p, is the state that A enters,
after reading input W.
So, although B can be in several
different states after reading W,
they all have the same first component.
And B simulates A using the first
component of A's state.
The second component, q,
is a state such that A can go from that
state q to an accepting state of A.
While reading some input x,
whose length is the same as that of w.
B will be in all states p,q such that
q satisfies the condition I just said.
It can get to a final state of A and
some input whose length, is the same as
that of the input that B has read so far.
Notice that B doesn't know how
long an input string it has read,
finite automata can't count.
But, we'll work out
the transitions of B so
that what we want to be true about
the second component will indeed be true.
The accepting states of B are those
pairs that have the same state in
both components.
The reason this choice makes sense,
is that if B is in a state, say, q,q,
then B has read some input w that takes
the DFA A from its start state to state q.
And there's also some input x,
of the same length as w,
that takes A from the state
q to an accepting state.
Thus, if B is in state
q,q after reading w,
that means there is some w x in L
where w and x are of the same length.
That in turn means that w is in Half of L.
Now let's design the transitions of B.
From its initial state s0,
B goes on epsilon to all pairs of
A states where the first state is
the start state of A, and the second
is one of the accepting states of A.
As we shall see, B never returns to s0.
And this first move guarantees, that
the empty string is handled correctly.
B accepts the empty string if and only if
q0, the start state of A, is accepting.
But that means A accepts epsilon,
and half of epsilon is epsilon.
Thus, B accepts epsilon if and
only if epsilon is in Half of L.
Now we need to design
the transitions of B, so that,
after the initial epsilon move, it is only
in the states we said it should be in,
given the interpretation we
put on a pair of A states p,q.
So the transition from state p,q of B,
on an input symbol a,
will be to those pairs of states
r,s that satisfy two conditions.
First, as we wanted, the first component
of B's state just tracks A's state.
That is, r is where DFA A goes on input a,
when it is in state p.
The second condition concerns
the second component.
There must be some input symbol b,
such that A goes from s to q on input b.
Notice the transition is from
the new second component to
the old second component, so
the new second component has a path to
acceptance that is one longer than before.
Thus, if x takes A to state p,
then x a takes A to state r.
That's this, we could prove by
simple induction on the length of w,
that the first component of B's state,
after reading w is always the state
A would be in after reading w.
But we won't do the proof.
We can also prove by induction
on the length of the input that
the second component of B's state,
can be all and only the states of A,
that reach an accepting state by following
a path whose length is exactly the same,
as the length of the input b has read so
far.
As I said, we're not going to
do the inductive proof that this
construction works, but
I'll set it up for you.
Okay, the inductive hypothesis
which we prove by induction on
the length of input w, is that B goes
on input w from one of its states q0,
f where q0 is the start state of A and
f is one of A's accepting states,
to all those states p,q such that,
A goes from q0 to p on input w and
A also goes from q to f on some input
x of length equal to that of w.
Once we have the inductive proof, we
have only to observe how B makes epsilon
transitions from its own start state
to each of the states q0, f, and that
B's accepting states are the ones, with
the same state of A for both components.
Here's a little example, I'm not going
to go over every transition of B,
on the right, but I invite you to pause
the video and study it if you like.
First, A is this two state,
DFA on the left in orange, and
B is the epsilon NFA in
purple on the right.
From the initial state, s0 of B,
there's only one epsilon transition,
since A has only one accepting state p.
This epsilon transition,
here, goes to the state q,p,
because q is the start state of A and
p is an accepting state.
Notice that because A has
only one accepting state,
we could have dropped state s0, and
simply made q,p be the start state of B.
[SOUND] Now let's consider
where q,p goes on input zero.
Since A goes from q to p on input zero,
that says the first component
of the new state must be p.
But we also have to look a the second
state of q,p, namely p, and ask,
from what states of A, are there
transitions, to p on any input symbol.
We see there are transitions to p on,
from both p, which is this, and
from q, that's that, thus q,p
goes to p,p and to p,q on input zero.
That's these two transitions here.
Next, let's see where
p,q goes on input zero.
First we consult A and
we see that on input zero, A takes p to p,
that's this, so the first component
of the new state must be p.
Then we ask, from what states
of A are there transitions to q?
Here we see the only transition,
to q in A is, this one from p.
As a result, the second component
can only be p in the new state.
Thus, the only transition of B from state
p,q on input zero is this, is to p, p.
We'll leave the rest of the transitions
to you, but notice that the,
the two accepting states of B are p,p and
q,q.
Those with identical states
in the two components.
Now that we know about Turing Machines,
we can address a question that I recall
from one of the first posts on the forum.
The questioner was evidently impressed
by something called aspect systems.
I think I remember reading
about them a generation ago.
They were supposed to the next big thing
after object-oriented programming.
I guess they weren't.
But it doesn't matter what they are.
Because, presumably,
they are some software system,
which means they are ultimately
executed on a computer.
And as we saw,
a Turing Machine can simulate a computer.
We really only dived into the matter
of how the storage units of
a computer are simulated,
but the rest is easy.
The arithmetic units,
the control logic, and such.
The bottom line, no programming system
can do what a Turing Machine cannot.
Real programming systems
can do things much faster,
because the Turing Machine is designed
to be the simplest possible device that
computes, but it's only a matter
of speed and not of capability.
But another attack on the use of
the Turing Machine as the definition of
what can be done by a computer comes
from a entirely different direction.
There are those who think,
we'll be eventually be able to build
computers that use quantum physics to do
things that appear impossible in
the world of Newtonian mechanics.
In particular, these hypothetical
devices behave something like
nondeterministic automata,
always appearing to guess right.
One of the most interesting
conclusions is Shor's algorithm for
factoring numbers in polynomial time
on a hypothetical, quantum computer,
which is something we doubt can be
done on a conventional computer.
There have been some interesting
experiments in which particles are somehow
linked by their spins and
carried far apart.
A change in one manifests itself
as a change in the other,
allowing communication over vast
distances without any perceptible link.
That means, for example, you could not
eavesdrop on the communication, so
it is more secure,
than conventional Newtonian communication.
I really don't believe there will
ever be practical, quantum computers.
The problem, is that a physical device
that is needed to represent a single bit
in a quantum computer,
called a q-bit, is huge.
I've heard it has to be roughly the size
of a refrigerator in order to isolate it
from other q-bits adequately.
But even if we can make really tiny
q-bits, we are still faced with the fact
that a nondeterministic Turing machine is
no more powerful than a deterministic one.
You should have seen that
video explaining why by now.
To be fair, proponents of quantum
computing claim that while they may
not be able to solve anything that
a conventional computer can not.
They can do certain things faster.
The one big example they point to is
Shore's algorithm for factoring numbers.
It looks to me like this case is
the exception rather than the rule.
Rule and
the advantages of a quantum computer,
if we can ever build one of
useful capacity, is small.
There are a number of questions,
about the mysteries of proofs and
the logical rules one can use, and
a number of these questions arose in
the thread about why I claim that one
stack as in a push down tom a ton.
Could not simulate two such stacks.
I didn't prove that point.
And, in fact,
it is more than a little vague.
What does it mean for
one stack to simulate two stacks?
If you make a reasonable attempt to
combine the action of two stacks into one,
you will find you're okay as long as the
two stacks push and pop at the same time.
Then you can keep in one stack,
symbols that represent pairs of symbols.
One from each of the stacks
you're simulating.
But two stacks need not push and
pop at the same time, and when one pushes
while the other pops, you get stuck.
There's no sensible thing to do
that will represent both moves.
Well if the difference between the lengths
of the two stacks is two, or any.
Constant.
Then you can remember the top symbols
of the longer stack in the state and
only keep the shorter stack on the bottom
portion of the longer stack on
the single stack you're trying to use.
But that's not good enough because as
time goes on there may be no limit on
the difference between the lengths of
the two stacks you're trying to simulate.
But the failure to prove something
is not proof that it can't be done.
So the first thing I need to do
is give a precise definition of
what would be considered a successful
simulation of two stacks by one.
I propose that as a minimum, if I had such
a construction, I would be able to use it
to design one PDA P that could simulate
two others between, P1 and P2.
And in particular,
to accept if any only if both accept it.
That is I would have a PDA
construction that showed CFLs were
closed under intersection.
But we already know that CFLs
are not closed under intersection.
So, let's assume that a construction
to build p from P1 and
P2 as on the previous slide exists.
Then in particular I could apply
the construction to PDAs that
accept the two context three languages
that we showed in the lecture.
Have a non-context free intersection.
That is that P1's language with a set
of strings of zero was followed by one,
was followed by twos, such that the
numbers of zeros and ones are the same.
That P2's language would be
the same except the constraint is
that the numbers of ones and
twos are the same.
Let P be a PDA accepting
the intersection of these languages.
The language of P is the set
of zeros followed by
an equal number of 1's followed
by an equal number of 2's.
Since we assume we can construct
P from P1 and P2, P exists and
therefore it's language is
context free as we know.
Are all languages accepted by PDAs.
But we know this language
is not context-free.
We have reached a false conclusion so
we know that our assumptions are wrong.
We have made only one assumption.
That P can be constructed from P1 and P2.
Since we drew a false
conclusion from our assumption.
Assumption, that assumption must be false,
that is we have proved that there is
no way to simulate two stacks by one in
a manner that is sufficient for us to
figure out whether the PDA is using these
two stacks, both accept a given input.
We might be able to simulate
hem in some weaker sense but
that sense would have
to be very weak indeed.
And I would not want to think of it as
a true simulation, since I couldn't tell
from the one stack what both of
the quote simulated stacks were doing.
This proof used a number of
logical tools that are sound but
which we might be tempted to question.
First, we use proof by contradiction,
that is,.
You, if we assume some statement S,
and we use correct logic and
true statements to derive something false,
then the statement S itself is false.
Here S was,
you can simulate two stacks with one,
in the formal sense of being able
to compute the intersection.
This is a generally accepted
form of logical reasoning, and
I don't want to suggest
that we should doubt it.
Proof by contradiction appears
to work in the real world.
However it doesn;t really follow
from anymore basic principles.
You need to take it or something
equivalent to it as an axiom of logic.
If you try to prove that
proof by contradiction works.
You will have to start
with something like.
well assume the rule doesn't hold that is.
You need to assume proof by contradiction
works in order to prove that it works.
An amusing sidelight is
that proof by induction,
another staple of this course, is also
something that needs to be assumed.
If you try to prove that
proof by induction works,
you wind either using
a proof by induction or
what is equivalent,
a proof by least counter example.
That is, you say that if
you can prove the basis and
induction step of some statement,
say S of I, and
yet S is not true for all I, then consider
the least I for which it is false.
S of I can't be the basis
because you proved that.
And if S, if I is not the basis.
This, then you know it is true for i minus
one and you prove the inductive steps.
That is, you know S of i minus one is
true and you prove the inductive step,
which implies in particular that S
of i minus one applies to S of i.
So again, S of i could not be false.
But the idea of least counter example
is equivalent to proof by induction.
And it is an assumption.
There does not have to be
a least counter example.
For example, consider the statement about
real numbers, is not greater than zero.
There's no least counter example because
if x is a counter example, that is,
x is greater than zero.
Then X over two is
a smaller counter example.
It is smaller than X but
also greater than zero.
Of course, we never suppose that
induction works for real numbers.
It doesn't.
Er, it only works for
things like intergers, trees and
other discreet things that
can be ordered like integer.
For these domains, inductive proofs
appear to reflect how the world works.
So we're okay assuming inductive
proofs are valid in those domains.
But there's a more worrisome point and
the fact that we have to
accept some axioms of logic.
When I derive something false,
I immediately pointed my
finger at the assumption you can
simulate two stacks with one.
This reasoning is important.
We use it heavily,
especially when we justify the idea of
reductions from one problem to another.
Definitely I never proved that
assumption about two stacks, so
it might be the cause
of a false conclusion.
But could there be any other
assumptions that I used without proof.
And could one of those be the cause
of the false conclusion instead?
I don't think so.
I believe everything I used was either
proved or I could prove it if challenged.
But I could be wrong couldn't I?
No proof is complete and
undisputable unless it is written
in a very very formal system.
But interesting proof such as my claim
about two stacks being better than one,
are just too complicated
to be written that way.
In practice mathematical proofs
are accepted by a community using
a social process.
That is interested people look at
the proof and if they doubt one or another
point they can challenge it and drill down
into the details of why the point is true.
Either they will be convinced or
the person who claimed it was
true will withdraw the claim.
That's how mathematics
arrives at the truth.
I'm going to conclude a discussion
of something that has nothing to
do with atometer theory per say but
rather applies our understanding of what
makes a proof believable to the question
of whether we can prove programs correct.
Theer was a paper written on this subject
about 40 years ago by three computer
scientists of serious note, Alan Perlis
was the first winner of the Turing award,
Rich DeMillo later became chief
technical officer at Hewlett Packard and
was also dean of computer
science at Georgia Tech.
Dick Lipton was the guy that
replaced my in Princeton in 1979.
He also has a number of
important ideas to his credit.
Including the one I
want to talk about now.
If papers started by making the points
I just made, that you can only believe
a proof if good mathematicians
have looked at it critically and
attempted to challenge any
questionable points in the reasoning.
In fact the title of the paper is,
Social Processes and
Proofs of Theorems in Programs.
They then went on to draw
a significant conclusion.
Proofs of correctness of a program need
to be subjected to the same scrutiny, or
they can't be believed.
But proofs of program
correctness are boring, and
no one is going to
participate in the social.
Process needed.
Thus they argued it was not realistic
to suppose that programs of
any significance would
ever be proved correct.
Interestingly, that reasoning
has pretty much held up.
40 years later, we still write code
hope it works, fix it if it doesn't, and
do not suppose that we can
prove it correct formally.
There are a few exceptions.
First there has been much more progress
than the three authors might have
expected in automated theorem proving.
Computers don't get bored so to the extent
that we could get them to do the checking,
we can avoid the social process problem.
A second, oddly,
is that if you pay people enough,
they will do the checking
even if they do get bored.
So there have been a few
instances where a lot of money and
time was spent doing a proof of.
Correctness for
a non trivial piece of software.
With that thought I'll leave you folks to
finish up the study of touring machines.
And then will go on in week six to
the matter of NP completeness and
intractable problems.