So, let's take a look now at implications of the undecidability of the halting problem.

I think the main thing that

people should take away is that if you know that a problem is undecidable,

don't try to solve it.

Here's Alice and Bob.

Say, Alice, we came up with an idea at our hackathon.

We're going to go for startup. So what's the idea?

Well, we're going to have an app that you can use to

make sure that any app you download won't hang your phone?

Alice who has taken a few computer science courses says,

well, I think that's undecidable.

Bob really doesn't know quite what that means so maybe a better way to phrase it is,

what happens if you give your app itself?

That's the self reference part that really

characterizes not computer ability or undecidability.

And let's take a look at some implications.

If you really think about it,

this idea is the reason that it's difficult to

debug programs because all the following things are undecidable.

Halting problem is something that every beginning programmer would like to solve.

As soon as you learn about loops and as soon as you

have your first program go into an infinite loop,

you wonder why doesn't my instructor have a program that takes

my program as input and checks whether or not it's got an infinite loop?

You can't, because the undecidability of the halting problem.

What would that program do if it was given itself as input?

And so forth and so on without much trouble you get back to Turing's proof.

And then there's lots of similar problems that

with similar types of constructions can be proved to be undecidable.

The idea is to assume that you can

solve the halting problem then you can solve this problem.

But since the halting problems

undecidable that would mean that this problem is undecidable.

So, these types of things.

Given a function does it halt on every input X?

Given a function with no input, does it halt?

Do two functions always return the same value?

That's another one that every programmer would like to have.

I have a new version of an old program and I want to know if it does the same thing.

And you might go and get a job in the software industry and have

a manager ask you to write up something like this and you can say,

no, I can't do it.

It's undecidable.

And all kinds of things and programming systems.

So, did I declare a variable and then use it without initializing it?

Again, undecidable.

I have a huge programming system,

there's lots of code in there,

does every line of code going to get executed?

Been proven equivalent to the halting problem.

So, each one of these people prove by showing that if you

solved it that would be a solution to the halting problem which is undecidable.

So, we're going to stamp these undecidable methods.

Undecidable problems this way.

So, the question is,

why are program development environments complicated?

They're programs that manipulate programs and

therefore they are susceptible to this self-reference idea.

But it goes way beyond programming systems.

Well, here's another example that's remember

Hilbert's Entscheidungsproblem which is the decision problem, is mathematics decidable.

Given a first-order logic of

mathematical system with a finite number of additional axioms.

Is it provable from the axioms using the rules of objects?

Or Church had a different formal system called

Lambda calculus that he developed in order to try to address this.

It's also the basis of modern functional programming languages,

that's programming languages based on functions operating on functions.

So, if you use Haskell or Java and what Church and Turing

showed through equivalence of

the lambda calculus and Turing machines in the halting problem is that,

Hilbert's Entscheidungsproblem is undecidable.

There's many others.

The Post's correspondence problem that we gave at the beginning.

Can you write a program that takes different kinds of cards is

input and tells you whether or

not there's an arrangement that has matching top and bottom spring.

That was another model of computation and another

decade or more later Posts proved that that undecidable.

And it's not just Turing problems,

computational mathematics is a fine area of

important application and nowadays people use systems like

a mathematical and sage and MATLAB and other systems.

In this that's functions that manipulate functions.

So, there's a famous one known as Hilbert's tenth problem,

given again around 1900 Hilbert asked,

so given the multivariate polynomial,

does it have integral roots?

That is either integers such that evaluating

the polynomial of those integers is equal to zero.

So, here's an example,

say it's 6X cubed YZ squared plus 3X YZ squared minus X cubed minus 10.

Other values of X, Y and Z that make that zero or not.

In this case there is,

five, three and zero does it.

But in this case X squared plus Y squared minus three, there's no way.

So, can we have as part of

our mathematical manipulation systems facility that you

give it a polynomial and it tells you whether or not it has integral roots or not?

No, it's undecidable.

Well, that was a difficult result that was proved

more than 100 years after or around 100 years after Hilbert formulated it.

Definite integration, that's something that we'd like to have in

our mathematical symbolic manipulation system.

So, if you have a rational function that's

composed of polynomials and trigonometric functions,

you want to know does the definite integral

from minus infinity to infinity of that function exist?

So, like cosine X over one plus X squared.

Yeah, that's pi over here but cosine X over one minus X squared.

No. So, if a user types in a rational functional like that,

that arises in an application you'd like to,

if you can't provide the answer you'd like to at least say that no such thing exists.

I can't do it. It's undecidable.

From computer science, there's all kinds of different ones.

So, data compression.

We have a movie, you want to compress it to make it smaller.

So, I want to make it as small as I can with the one way to formulate that

is given a string find the shortest program that can produce it or given a picture,

find the shortest program that can produce it.

Remember, we did the Mandelbrot Set.

That's a pretty complicated picture reproduced there with a 34-line program,

but if some data compression method gets that picture

can it figure out a short program to predict it?

No, that's undecidable.

Virus identification.

So, there is a virus out on the web that

you load into your computer would be nice to have

a program that can analyze the code that you bring into

a computer and tell you whether or not it's a virus,

it can't, that's undecidable.

So, all of those practical applications are extremely important.

You should know whether or not the problem's undecidable or not.

But really let's review the key ideas in Turing's paper.

This is a single paper called

Uncomputable Numbers with application to the Entscheidungsproblem.

It's been called one of the most impactful scientific papers of the 20th century.

In that paper, he introduced the Turing Machine,

a formal model of computation.

The equivalence of programs and data we encode both programs and their data

as strings and we compute with them both the idea of universality.

A concept that we can have one device

that can compute anything that we know how to compute.

The third Church-Turing thesis that says,

if you can compute it at all you can computer with the Turing machine."

Therefore anything in this universe that computes is equivalent to a Turing machine.

The idea that there are limits to

computation and there are things that we cannot compute,

all of these things were published in this paper in 1936 which is

ten years before the earliest computers and we'll talk later

about the ENIAC that was worked on in the 40s.

All of these things were thought about abstractly before we even had computers.

Now, John von Neumann who was a scientist at Princeton,

read this paper and talked to Turing and we'll pick up the story later on.

But for now, let's talk about the importance of

theoretical computer science and Turing's ideas.

And he's sometimes called the father of computer science.

This is a quote from a famous biography of Turing called,

Alan Turing the Enigma written by John Hodges.

So he's saying, well,

it wasn't only a matter of abstract mathematics,

not just a play of symbols,

because it involved thinking about what people do in the physical world.

It was a play of imagination like that of Einstein or von Neumann,

doubting the axioms rather than measuring effects.

What he had done was to combine

such a naive mechanistic picture of the mind with precise logic of pure mathematics.

His machines, which were soon to be called Turing Machines offered a bridge,

a connection, between abstract symbols in the physical world.

And that's the true significance of this work and it has really

had important implications in

the development of the computational infrastructure that we now enjoy.

Turing showed that the biggest google data center in terms of power,

in terms of problems it can solve is no

different than the simple model of his universal Turing machine.

Quite a stunning result with long lasting implications.

Implications

Computer Science: Algorithms, Theory, and Machines

Meet the Instructors