Welcome to Exploring Computing.
Today's video is computer theory undecidable problems.
So one question we might ask ourselves is, are there
limits to what we can actually use a computer
program to compute?
And the answer is yes.
Some problems are undecidable and we cannot write a computer
program that can solve these problems.
One famous example of an undecidable problem
is a halting problem.
Now, one thing that we often use when we're developing computer
programs is we use computer programs to help
us write computer programs.
So you think of if you use an editor with syntax
highlighting.
What we're doing is we're taking the computer program
that you're writing and we are using a second computer
program that is analyzing that program,
and figuring out how to do the syntax highlighting on it.
So similarly, a compiler analyzes computer programs
to determine if they follow the rules of that computer
programming language.
So one question is it would be pretty useful
if we could write a program that determines whether or not
a program will actually stop running for a given input.
So if I write a program, can I say, hey,
if I have the following types of inputs
will I ever run into a situation where I don't have an infinite
loop?
Can I analyze the program and determine that the situation
will never occur?
And so that's the halting problem.
So we're going to prove that you can't actually
write a program that will be able to determine
whether a program halts for giving input.
And we're going to prove that this does not
exist by contradiction to the way
these proofs by contradiction works
is we're going to assume that the solution to this problem
actually does exist.
And then at some point, we're going
to see that there's a contradiction
and that our original premise that the program existed
must, in fact, be false.
So OK so here's our little program here that does actually
work, or claim it works.
We're claiming it could exist.
So you can see that our program takes a couple of inputs.
One of the inputs is the program that we want to analyze.
And the second input is the data that I
want to run on that program, which we're analyzing
until I tell the program--
the halting program, hey, here's a program I want you to analyze
and here's some data that I want to feed to that program.
Can you look this over and tell me
whether, or not this program is actually
stopped for this output?
So this should output true, or false.
So I'm going to claim that this program does exist.
And now what we're going to do is
we're going to modify this program by adding a little bit
of extra code here.
So we'll say if that original program which
tests for halting returns true, I'm
going to send the program into an infinite loop.
I mean, that's easy enough to like while true go do nothing
and that's an infinite loop right there.
OK, so if that original program testing for halting
returns true, go into an infinite loop.
Otherwise, if that program that deters one
that the input will halt for giving data input
then I'm going to go ahead and stop.
Now, what happens when we run the program on itself?
So I'm going to go ahead and take
my extended halting program with the extra infinite
loop testing it as input.
So that's a program we want to analyze.
And then I'm going to say I'm going to ask that program
to analyze and then as the data, I
expect that program to analyze.
I'm also going to use the exact same program going to say,
I was going to analyze this halting program
with the infinite loop added to it as data.
And then we're going to go ahead and carry out this analysis.
So let's look at what happens here.
If the original analysis program concludes
that the extent halting program halted its own code.
Then that original program is going
to return true because it says, oh, this will in fact halt.
But then we added in that extra code that tosses it
into an infinite loop.
So that's kind of a problem because we just said
that it was supposed to stop.
But, in fact it's entering an infinite loop.
On the other hand, if the halting program--
original analysis program concludes
that the extended program does not hold on its own code
then that in our original test program returns false.
And this extra code we added says
if it returns true, [? you got an ?] if loop.
Otherwise, if it doesn't return true, stop.
And so, in fact, the program stops.
But our analysis concluded that, in fact, the program
doesn't halt. It goes in an infinite loop.
So you can see we've got a contradiction here.
Either we're wrong because it goes an infinite loop,
or we're wrong because it halts.
Either way, our halting program analysis--
our original halting program analysis is not working.
And so therefore, we can see that we cannot, in fact,
write a halting program.
So this is just probably the most famous example
but undecidable program.
But the main reason why I wanted to cover this was just
to emphasize that, I'm sad to report that computers cannot do
everything.
And that actually seems like a good place to end our lecture.
So I hope you enjoyed the class and you all learned a lot.
Good luck with your future endeavors.